【LOJ#3146】[APIO2019]路灯（树套树）

题面

题解

考场上因为\(\text{bridge}\)某个\(\text{subtask}\)没有判\(n=1\)的情况导致我卡了\(3.5h\)左右，然后这题就只能匆匆\(rush\)了一个\(60\)分暴力......

---

考虑维护出每一个时刻的亮的灯的连续段，那么对于连续段\([l,r]\)，显然此时刻在区间内的任意一组询问都会被产生贡献。

因为维护连续段非常不好处理，所以考虑每一个未开灯的地方的影响。

假设\(x\)位置未开灯，上一个没有开的位置是\(lt\)，那么对于左区间在\([lt+1,i]\)，右区间在\([lt+1,i]\)的范围内就会产生贡献，那么我们可以把区间换成点，于是贡献变成了二维数点。

那么直接拿树套树维护就行了。（或者\(CDQ\)之类也行）

这里统计答案用类似差分的方法，我们一开始把所有位置都给上\(+Q\)的贡献，对于依次修改操作，把影响的区间的贡献给补上就好了。

举个例子，还是\(x\)和\(lt\)两个位置，那么左区间在\([lt+1,i]\)，右区间在\([i+1,n+1]\)的区间没有贡献。

那么给\((lt+1,i+1)\)位置加上一个\(-Q\)，\((i+1,i+1)\)位置加上一个\(Q\)就可以维护出这个贡献了。

最后统计答案的时候要记得如果答案当前恰好还是一个完整区间，就要把剩下不要统计时间的\(Q\)个时间给去掉。。。

#include
    
     #include
     
      #include
      
       using namespace std;#define MAX 300300inline int read(){    int x=0;bool t=false;char ch=getchar();    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();    if(ch=='-')t=true,ch=getchar();    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();    return t?-x:x;}int n,Q;struct Node{int ls,rs,v;}t[MAX<<6];int tot,rt[MAX];void Modify(int &x,int l,int r,int p,int w){    if(!x)x=++tot;t[x].v+=w;    if(l==r)return;    int mid=(l+r)>>1;    if(p<=mid)Modify(t[x].ls,l,mid,p,w);    else Modify(t[x].rs,mid+1,r,p,w);}int Query(int x,int l,int r,int L,int R){    if(!x)return 0;    if(L<=l&&r<=R)return t[x].v;    int mid=(l+r)>>1,ret=0;    if(L<=mid)ret+=Query(t[x].ls,l,mid,L,R);    if(R>mid)ret+=Query(t[x].rs,mid+1,r,L,R);    return ret;}int lb(int x){return x&(-x);}void Modify(int x,int y,int v){while(x<=n+1)Modify(rt[x],1,n+1,y,v),x+=lb(x);}int Query(int x,int y){int s=0;while(x)s+=Query(rt[x],1,n+1,1,y),x-=lb(x);return s;}set
       
         S;set
        
         ::iterator it,pr,nt;char ch[MAX];int main(){    n=read();Q=read();scanf("%s",ch+1);    S.insert(0);S.insert(n+1);Modify(1,1,Q);        for(int i=1,j=0;i<=n;++i)    {        if(ch[i]=='1')continue;        S.insert(i);        Modify(j+1,i+1,-Q);        Modify(i+1,i+1,Q);        j=i;    }    while(Q--)    {        char opt[8];scanf("%s",opt);        if(opt[0]=='t')        {            int x=read(),zt=(ch[x]=='0')?1:-1;            if(ch[x]=='1')S.insert(x);            it=S.find(x);            pr=nt=it;--pr;++nt;            Modify(*pr+1,x+1,Q*zt);Modify(x+1,x+1,-Q*zt);                       if(*nt!=n+1)Modify(*pr+1,*nt+1,-Q*zt),Modify(x+1,*nt+1,Q*zt);            if(ch[x]=='0')S.erase(x);            ch[x]^=1;        }        else        {            int x=read(),y=read();            printf("%d\n",Query(x,y)-Q*(S.lower_bound(x)==S.lower_bound(y)));        }    }    return 0;   }