Description

Input

Output

Sample Input

7 10
1
2
3
0 1 2
0 4 7
0 2 5
20
0 6 6
99
0 4 6

Sample Output

1
2
2
1
3

Data Constraint

对于30%的数据，N<=10^5，Q<=1000 对于100%的数据，N<=10^9,Q<=10^5

分析

线段树显然

代码

#include #include #include #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; typedef long long LL; const int N=200500,M=8027413; int read(int &n) { char ch=' ';int q=0,w=1; for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar()); if(ch=='-')w=-1,ch=getchar(); for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n; } int m,n,b0; struct qqww { int co,lv,rv,mx,mxi,l,r; }b[N*10]; int Hx[M][2]; int HX(int q) { int i=q%M; while(Hx[i][0]&&Hx[i][0]!=q) { i=(i+1)%M; } return i; } void merge(qqww &s,qqww q,qqww w,int l,int r,int t) { if(q.co==0)q.lv=q.rv=t-l+1; if(w.co==0)w.lv=w.rv=r-t; if(q.mx>w.mx)s.mx=q.mx,s.mxi=q.mxi; else s.mx=w.mx,s.mxi=w.mxi; if(s.mx1>s.mxi))s.mx=q.rv+w.lv,s.mxi=t-q.rv+1; s.lv=q.lv,s.rv=w.rv; if(q.co==0)s.lv+=w.lv; if(w.co==0)s.rv+=q.rv; s.co=q.co+w.co; } void change(int l,int r,int &e,int l1,int l2) { if(!e)e=++b0; if(l==r) { b[e].lv=b[e].rv=b[e].mx=!(b[e].co=l2); if(!l2)b[e].mxi=l; return; } int t=(l+r)>>1; if(l1<=t)change(l,t,b[e].l,l1,l2); else change(t+1,r,b[e].r,l1,l2); merge(b[e],b[b[e].l],b[b[e].r],l,r,t); } int find(int l,int r,int e,int l1,int r1) { if(!e)return 0; if(l==l1&&r==r1)return b[e].co; int t=(l+r)>>1; if(r1<=t)return find(l,t,b[e].l,l1,r1); else if(treturn find(t+1,r,b[e].r,l1,r1); else return find(l,t,b[e].l,l1,t)+find(t+1,r,b[e].r,t+1,r1); } int main() { freopen("switch.in","r",stdin); freopen("switch.out","w",stdout); int q,w,YI=1; int TJ=0,TJ1=0; read(n),read(m); b[b0=1].mx=n,b[1].mxi=1; fo(i,1,m) { read(q); if(!q) { read(q),read(w); printf("%d ",find(1,n,1,q,w)); continue; } int t=HX(q); if(Hx[t][1]) { TJ++; change(1,n,YI,Hx[t][1],0); Hx[t][1]=0; }else { TJ1++; Hx[t][0]=q; q=((LL)b[1].mxi*2+(LL)b[1].mx)>>1; Hx[t][1]=q; change(1,n,YI,q,1); } } return 0; }