Submission #76484459

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define inf 1e18
#define eps 1e-9
#define endl "\n"
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=3e5+5,M=2505;
const int mod=1e9+7;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,q,Q;
int lstx[N],lsty[N];
struct BIT{
    int f[N];
    inline void add(int p,int v){
        for(;p<=q+1;p+=(p&-p)) f[p]+=v;
        return ;
    }
    inline int query(int p){
        int res=0;
        for(;p;p-=(p&-p)) res+=f[p];
        return res;
    }
}tr[3];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc=1;
    while(tc--){
        cin>>n>>q;
        int ans=0,cur=2;
        for(int i=1;i<=n;i++) lsty[i]=1;
        tr[2].add(1,n); 
        Q=q;
        for(;cur<=q+1;cur++)
        {
            int op,x;
            cin>>op>>x;
            if(op==1){
                int pre=lstx[x];
                int now=tr[2].query(q+1)-tr[2].query(pre);
                ans=ans+now,lstx[x]=cur;
                if(pre) tr[1].add(pre,-1);
                tr[1].add(cur,1);
            }
            else{
                int pre=lsty[x];
                int now=tr[1].query(cur)-tr[1].query(pre);
                ans=ans-now,lsty[x]=cur;
                if(pre) tr[2].add(pre,-1);
                tr[2].add(cur,1);
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}

Submission Info

Judge Result