电源

bzoj5155 [Tjoi2014]电源插排（动态开点线段树）

2019-07-13 22:40发布

站内文章 / 电源技术
10500 0 1272
动态加点，维护区间最长连续空闲段即可。 #include #include #include #include using namespace std; #define ll long long #define inf 0x3f3f3f3f #define N 100010 inline char gc(){ static char buf[1<<16],*S,*T; if(S==T){T=(S=buf)+fread(buf,1,1<<16,stdin);if(T==S) return EOF;} return *S++; } inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=gc(); return x*f; } int n,Q,owo=0,rt=0; map<int,int>mp; struct node{ int lc,rc,sum,ls,rs,mxs; }tr[N*30]; inline void newnode(int p,int l,int r){ tr[p].sum=0;tr[p].ls=tr[p].rs=tr[p].mxs=r-l+1; } inline void pushup(int p,int x,int y,int mid){ int l=tr[p].lc,r=tr[p].rc,lenl=mid-x+1,lenr=y-mid; tr[p].ls=(l?tr[l].ls:lenl); if(tr[p].ls==lenl) tr[p].ls+=(r?tr[r].ls:lenr); tr[p].rs=r?tr[r].rs:lenr; if(tr[p].rs==lenr) tr[p].rs+=(l?tr[l].rs:lenl); tr[p].mxs=max(l?tr[l].mxs:lenl,r?tr[r].mxs:lenr); tr[p].mxs=max(tr[p].mxs,(l?tr[l].rs:lenl)+(r?tr[r].ls:lenr)); tr[p].sum=tr[l].sum+tr[r].sum; } inline int qsum(int p,int l,int r,int x,int y){ if(!p) return 0; if(x<=l&&r<=y) return tr[p].sum; int mid=l+r>>1,res=0; if(x<=mid) res+=qsum(tr[p].lc,l,mid,x,y); if(y>mid) res+=qsum(tr[p].rc,mid+1,r,x,y); return res; } inline void del(int p,int l,int r,int x){ if(l==r){ tr[p].ls=tr[p].rs=tr[p].mxs=1;tr[p].sum=0;return; }int mid=l+r>>1; if(x<=mid) del(tr[p].lc,l,mid,x); else del(tr[p].rc,mid+1,r,x); pushup(p,l,r,mid); } inline void ins(int &p,int l,int r,int x){ if(!p) p=++owo,newnode(p,l,r); if(l==r){ tr[p].ls=tr[p].rs=tr[p].mxs=0;tr[p].sum=1;return; }int mid=l+r>>1; if(x<=mid) ins(tr[p].lc,l,mid,x); else ins(tr[p].rc,mid+1,r,x); pushup(p,l,r,mid); } inline int ask(int p,int l,int r){ if(!p) return r+l+1>>1; int lc=tr[p].lc,rc=tr[p].rc,mid=l+r>>1,lenl=mid-l+1,lenr=r-mid; if(tr[p].mxs==(rc?tr[rc].mxs:lenr)) return ask(tr[p].rc,mid+1,r); if(tr[p].mxs==(lc?tr[lc].rs:lenl)+(rc?tr[rc].ls:lenr)) return mid-(lc?tr[lc].rs:lenl)+1+tr[p].mxs/2; return ask(tr[p].lc,l,mid); } int main(){ n=read();Q=read(); while(Q--){ int x=read(); if(!x){int l=read();printf("%d ",qsum(rt,1,n,l,read()));continue;} if(mp[x]) del(rt,1,n,mp[x]),mp[x]=0; else mp[x]=ask(rt,1,n),ins(rt,1,n,mp[x]); }return 0; }

热门文章