线段树维护为最长的连续为空的子段
#include<cstdio> #include<iostream> #include<cstring> #include<map> #include<set> using namespace std; const int N=64e5+10; #define ll son[o][0] #define rr son[o][1] #define mid (l+r)/2 int id[N],len[N],len1[N],len2[N],tot,son[N][2],sum[N]; int init(int l,int r){ son[tot][0]=son[tot][1]=-1; len1[tot]=len2[tot]=len[tot]=r-l+1; id[tot]=l; sum[tot]=r-l+1; return tot++; } void pushup(int l,int r,int o){ // len1[o]=len1[ll]; // len2[o]=len2[rr]; if(len1[ll]==mid-l+1){ len1[o]=len1[ll]+len1[rr]; } else len1[o]=len1[ll]; if(len2[rr]==r-mid){ len2[o]=len2[rr]+len2[ll]; } else len2[o]=len2[rr]; len[o]=len[rr];id[o]=id[rr]; if(len2[ll]+len1[rr]>len[o]){ len[o]=len2[ll]+len1[rr]; id[o]=mid-len2[ll]+1; } if(len[ll]>len[o]){ len[o]=len[ll]; id[o]=id[ll]; } sum[o]=sum[ll]+sum[rr]; } void pushdown(int l,int r,int o){ if(son[o][0]==-1)son[o][0]=init(l,mid); if(son[o][1]==-1)son[o][1]=init(mid+1,r); } void update(int l,int r,int o,int x,int v){ if(l==r){ sum[o]=len1[o]=len2[o]=len[o]=v; id[o]=l; return ; } pushdown(l,r,o); if(x<=mid){ update(l,mid,ll,x,v); } else { update(mid+1,r,rr,x,v); } pushup(l,r,o); } int ans=0,L,R; void query(int l,int r,int o){ if(L<=l&&r<=R){ ans+=sum[o];return ; } if(L<=mid){ if(ll!=-1)query(l,mid,ll); else ans+=min(mid,R)-max(L,l)+1; } if(R>mid){ if(rr!=-1)query(mid+1,r,rr); else ans+=min(r,R)-max(L,mid+1)+1; } } map<int,int> id_mp,num_mp; int main(){ #ifdef DouBi freopen("in.cpp","r",stdin); #endif // DouBi int n,q; //printf("%d\n",N); while(scanf("%d%d",&n,&q)!=EOF){ id_mp.clear(); num_mp.clear(); tot=0; init(1,n); for(int i=0;i<q;i++){ //printf("len%d len1%d len2%d id%d sum%d\n",len[0],len1[0],len2[0],id[0],sum[0]); int op,l,r;scanf("%d",&op); if(!op){ scanf("%d%d",&L,&R); ans=0; query(1,n,0); printf("%d\n",R-L+1-ans); } else { int x=num_mp[op]; x++; if(x%2==1){ id_mp[op]=id[0]+len[0]/2; update(1,n,0,id_mp[op],0); //printf("add%d %d\n",op,id_mp[op]); } else { //printf("del%d %d\n",op,id_mp[op]); update(1,n,0,id_mp[op],1); } num_mp[op]=x; } //printf("asdlen%d len1%d len2%d id%d sum%d\n\n",len[0],len1[0],len2[0],id[0],sum[0]); } } return 0; }