好久没来了。除个草吧。
m(m<=300,000)个操作。操作分2种:
1.A p,表示把编号最小的空着的长度为p的区间图上颜色。
2.L a b,表示把从a到b的区间(包括端点)全部擦干净(没颜色还是没颜色)。
Q:有多少个操作1不能实现?
USACO的GOLD题。喜闻乐见的数据结构题。
仔细YY一下就可以发现线段树即可。
每个节点维护左边开始连续空的个数,右边连续空的个数,整段里面连续空的个数。
up的时候合并一下就行。down的时候打标记。
具体实现操作一的时候,需要先递归查找一下操作的区间。自行脑补吧。
操作二就是打标记。
没了。
PS:顺利成为在bz上第6个A了这道题的棱,而且还r1了= =
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxt=2010000; int n,m; struct SegNode{ int l0,r0,s0,m0,m1,all; }t[maxt]; #define ls (x<<1) #define rs (x<<1|1) char buf[5120000],*pt=buf; inline int getint(){ int s=0; while(*pt<'0'||*pt>'9')pt++; while(*pt>='0'&&*pt<='9')s=s*10+*pt++-48;return s; }inline char getop(){ while(*pt!='A'&&*pt!='L') pt++; return *pt++; }void update(int l,int r,int x){ if(t[ls].all) t[x].l0=t[ls].l0+t[rs].l0; else t[x].l0=t[ls].l0; if(t[rs].all) t[x].r0=t[ls].r0+t[rs].r0; else t[x].r0=t[rs].r0; t[x].all=t[ls].all&t[rs].all; t[x].s0=t[x].l0; if(t[x].r0>t[x].s0) t[x].s0=t[x].r0; if(t[ls].s0>t[x].s0) t[x].s0=t[ls].s0; if(t[rs].s0>t[x].s0) t[x].s0=t[rs].s0; if(t[ls].r0+t[rs].l0>t[x].s0) t[x].s0=t[ls].r0+t[rs].l0; }void down(int l,int r,int x){ if(t[x].m1){ t[ls]=t[rs]=(SegNode){0,0,0,0,1,0}; t[x].m1=0; }if(t[x].m0){ int mid=(l+r)>>1; t[ls]=(SegNode){mid-l+1,mid-l+1,mid-l+1,1,0,1}; t[rs]=(SegNode){r-mid,r-mid,r-mid,1,0,1}; t[x].m0=0; } }void build(int l,int r,int x){ if(l==r){ t[x]=(SegNode){1,1,1,0,0,1}; return; }int mid=(l+r)>>1; build(l,mid,ls); build(mid+1,r,rs); update(l,r,x); }void modify1(int L,int R,int l,int r,int x){ if(L<=l && r<=R){ t[x]=(SegNode){0,0,0,0,1,0}; return; }down(l,r,x); int mid=(l+r)>>1; if(L<=mid) modify1(L,R,l,mid,ls); if(mid<R) modify1(L,R,mid+1,r,rs); update(l,r,x); }void modify0(int L,int R,int l,int r,int x){ if(L<=l && r<=R){ t[x]=(SegNode){r-l+1,r-l+1,r-l+1,1,0,1}; return; }down(l,r,x); int mid=(l+r)>>1; if(L<=mid) modify0(L,R,l,mid,ls); if(mid<R) modify0(L,R,mid+1,r,rs); update(l,r,x); }SegNode ask(int L,int R,int l,int r,int x){ if(L<=l && r<=R) return t[x]; down(l,r,x); int mid=(l+r)>>1; if(L>mid) return ask(L,R,l,mid,ls); if(mid>=R) return ask(L,R,mid+1,r,rs); SegNode a=ask(L,R,l,mid,ls),b=ask(L,R,mid+1,r,rs),c; if(a.all) c.l0=a.l0+b.l0; else c.l0=a.l0; if(b.all) c.r0=a.r0+b.r0; else c.r0=b.r0; c.all=a.all&b.all; c.s0=c.l0; if(c.r0>c.s0) c.s0=c.r0; if(a.s0>c.s0) c.s0=a.s0; if(b.s0>c.s0) c.s0=b.s0; if(a.r0+b.l0>c.s0) c.s0=a.r0+b.l0; return c; }int find(int l,int r,int x,int num){ if(t[x].l0>=num) return l; down(l,r,x); int mid=(l+r)>>1; if(t[ls].s0>=num) return find(l,mid,ls,num); if(t[ls].r0+t[rs].l0>=num) return mid-t[ls].r0+1; return find(mid+1,r,rs,num); }int main(){ fread(buf,1,5120000,stdin); n=getint(); m=getint(); build(1,n,1); char op[2]; int x,y,an=0; while(m--){ if(getop()=='A'){ x=getint(); if(ask(1,n,1,n,1).s0<x){ an++; continue; }y=find(1,n,1,x); modify1(y,y+x-1,1,n,1); }else{ x=getint();y=getint(); modify0(x,y,1,n,1); } }cout << an << endl; return 0; }