题目链接：cf 704A


这个题是一个很好的题，首先理解题意就比较费劲，然后看上去是一个模拟的题，是需要用数据结构来维护的，暴力写是超时的

分析题意：

题目中给定了三种操作

操作1：第x种应用增加一个未读消息

操作2：我把第x种应用的消息全部读完（标记为已读）

操作3：我把所有的应用的消息按照时间从先到后的顺序，读取x个

在读取的时候，是可能会有重复读取的。

n=1e5，q=1e5

然后，每个操作之后，我们需要输出的是，在每个操作之后，当前的消息库中总共还有多少个未读消息


学到了一个线段树来维护未读消息的姿势！

竟然这样写没有超时，我很诧异


首先，搞两个数组来标记，当前的第几个应用的第几个消息是什么（因为是vector的push_back（），所以会是按照时间顺序的）

这个标记为vector<int> dui【maxn】

然后，我们还需要一个对全局都进行记录的vector<int> his


然后，很有意思的方法来了

对于操作1：我们使用线段树来维护

就有update函数，让x这个位置的值加1就好

然后his和dui【t】中都标记好当前的值就好


对于操作2：我们用另外一个update来搞

把这个x的位置上的值全部清0

然后，his中的所有值标为-1（表示读过了）

然后dui【x】的值清空（已经全部读过了）


对于操作3：如果当前需要判断的值x不超过当期的最大插入数量，那么直接输出线段树的根节点

否则，我们需要进行修改


强调一下容易理解错的几行代码

his.push_back(-1);

int Max=1;

这两行代码，是为了防止直接查询3的时候出错用的（在里面放了个无用数据）


下面贴代码：

#include<bits/stdc++.h>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

const int maxn=3e5+500;
int sum[maxn<<2];
vector<int> dui[maxn];
vector<int> his;

void PushUp(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void Build(int l,int r,int rt){
    if (l==r){
        sum[rt]=0;
        return;
    }
    int m=(l+r)>>1;
    Build(lson);
    Build(rson);
    PushUp(rt);
}

void Update(int p,int x,int l,int r,int rt){
    if (l==r){
        sum[rt]=x;
        return;
    }
    int m=(l+r)>>1;
    if (p<=m) Update(p,x,lson);
    else Update(p,x,rson);
    PushUp(rt);
}

void Update1(int p,int x,int l,int r,int rt){
    if (l==r){
        sum[rt]+=x;
        return;
    }
    int m=(l+r)>>1;
    if (p<=m) Update1(p,x,lson);
    else Update1(p,x,rson);
    PushUp(rt);
}

int queryhe(int L,int R,int l,int r,int rt){
    if (L<=l&&R>=r) return sum[rt];
    int m=(l+r)>>1;
    int ret=0;
    if (L<=m) ret+=queryhe(L,R,lson);
    if (R>m) ret+=queryhe(L,R,rson);
    return ret;
}

int main(){
    //freopen("input.txt","r",stdin);
    int n,q;
    while(scanf("%d%d",&n,&q)!=EOF){
        memset(sum,0,sizeof(sum));
        for(int i=0;i<maxn;i++) dui[i].clear();
        his.clear();
        his.push_back(-1);
        Build(1,n,1);
        int Max=1,total=0,op,t;
        for(int i=1;i<=q;i++){
            scanf("%d%d",&op,&t);
            if (op==1){
                total++;
                Update1(t,1,1,n,1);
                cout<<queryhe(1,n,1,n,1)<<endl;
                his.push_back(t);
                dui[t].push_back(total);
            }
            else if (op==2){
                Update(t,0,1,n,1);
                cout<<queryhe(1,n,1,n,1)<<endl;
                int len=(int)dui[t].size();
                for(int j=0;j<len;j++) his[dui[t][j]]=-1;
                dui[t].clear();
            }
            else{
                if (t<Max){
                    cout<<queryhe(1,n,1,n,1)<<endl;
                }
                else{
                    for(int j=Max;j<=t;j++){
                        int cur=his[j];
                        if (cur==-1) continue;
                        Update1(cur,-1,1,n,1);
                        his[j]=-1;
                    }
                    Max=t+1;
                    cout<<queryhe(1,n,1,n,1)<<endl;
                }
            }
        }
    }
    return 0;
}