Submission #76461708

---

Source Code Expand

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

#define int long long 

const int N=3e5+5;

bool st;
int n,q;
int temp1[N],temp2[N];
inline int lowbit(int x) {return x&(-x);}
struct bit{
	int a[N];
	inline void add(int pos,int x) {
		pos++;for(int i=pos;i<=q+1;i+=lowbit(i)) a[i]+=x;
	}
	inline int get_sum(int pos) {
		int res=0;pos++;
		for(int i=pos;i;i-=lowbit(i)) res+=a[i];
		return res;
	}
}t1,t2;
bool ed;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cerr<<(double)(&st-&ed)/1024/1024<<'\n';
	cin>>n>>q;int res=0;
	t1.add(0,n);t2.add(0,n);
	for(int i=1;i<=q;i++) {
		int op,x;
		cin>>op>>x;
		if(op==1) {
			res+=n-t2.get_sum(temp1[x]-1);
			t1.add(i,1);t1.add(temp1[x],-1);temp1[x]=i;
		}else {
			res-=n-t1.get_sum(temp2[x]);
			t2.add(i,1),t2.add(temp2[x],-1);temp2[x]=i;
		}cout<<res<<'\n';
	}
	return 0;
}

Submission Info

Judge Result