class="markdown_views prism-github-gist">

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

Solution

• 这题显然是一道线段树的题啦！不过却有许多细节要注意。
• 首先，将一个人的占据视为阻隔，那么一个区间需要维护几个值：
  1. 此区间内最大区间的长度
  2. 此区间内最大区间的起始位置
  3. 从左向右扩展的最大长度
  4. 从右向左扩展的最大长度
  5. 此区间内被占据的个数
• 那么，合并区间的方法就显而易见了，人的进入就相当于单点修改。
• 但由于区间有 109 那么大，所以必须动态开点，以编号为下标储存。
• 另外每个人的坐标无序，用 Hash 处理即可。
• 一个人插入的位置就是当前根节点的②值、加上①值除以2，
• 同时用一个数组记录，以便其离开时查找。
• 那么总时间复杂度就是优美的 O(QlogN) 。

Code

#include using namespace std; const int N=100001,mo=1e6+7; struct data { int l,r,ls,rs,ml,mx,n; }f[N*33]; int tot,ans; int h[mo],g[mo]; bool b[mo]; inline int read() { int data=0; char ch=0; while(ch<'0' || ch>'9') ch=getchar(); while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar(); return data; } inline int hash(int x) { int y=x%mo; while(h[y] && h[y]!=x) y=(y+1)%mo; return y; } inline void add(int v,int l,int r) { f[v].ml=l; f[v].l=f[v].r=f[v].mx=r-l+1; } inline void find(int v,int l,int r,int x,int y) { if(l==x && r==y) { ans+=f[v].n; return; } int mid=(l+r)>>1; if(!f[v].ls) add(f[v].ls=++tot,l,mid); if(!f[v].rs) add(f[v].rs=++tot,mid+1,r); if(y<=mid) find(f[v].ls,l,mid,x,y); else if(x>mid) find(f[v].rs,mid+1,r,x,y); else { find(f[v].ls,l,mid,x,mid); find(f[v].rs,mid+1,r,mid+1,y); } } inline void change(int v,int l,int r,int x,int y) { if(l==r) { f[v].n+=y; if(y>0) f[v].l=f[v].r=f[v].ml=f[v].mx=0; else { f[v].ml=l; f[v].l=f[v].r=f[v].mx=1; } return; } int mid=(l+r)>>1; if(!f[v].ls) add(f[v].ls=++tot,l,mid); if(!f[v].rs) add(f[v].rs=++tot,mid+1,r); int ls=f[v].ls,rs=f[v].rs; if(x<=mid) change(ls,l,mid,x,y); else change(rs,mid+1,r,x,y); f[v].n=f[ls].n+f[rs].n; f[v].l=f[ls].l; if(f[v].l==mid-l+1) f[v].l+=f[rs].l; f[v].r=f[rs].r; if(f[v].r==r-mid) f[v].r+=f[ls].r; if(f[ls].mx>f[rs].mx) { f[v].mx=f[ls].mx; f[v].ml=f[ls].ml; }else { f[v].mx=f[rs].mx; f[v].ml=f[rs].ml; } if(f[ls].r+f[rs].l>f[v].mx || f[ls].r+f[rs].l==f[v].mx && mid-f[ls].r+1>f[v].ml) { f[v].mx=f[ls].r+f[rs].l; f[v].ml=mid-f[ls].r+1; } } int main() { int n=read(),q=read(); add(tot=1,1,n); while(q--) { int p=read(); if(!p) { int l=read(),r=read(); ans=0; find(1,1,n,l,r); printf("%d ",ans); continue; } int k=hash(p); if(!h[k]) h[k]=p; if(!b[k]) { b[k]=true; change(1,1,n,g[k]=f[1].ml+f[1].mx/2,1); }else { change(1,1,n,g[k],-1); b[k]=g[k]=0; } } return 0; }