【LOJ#3146】[APIO 2019]路灯(树套树)

【LOJ#3146】[APIO 2019]路灯(树套树)

题面

LOJ

题解

考场上因为\(\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<iostream>
#include<cstdio>
#include<set>
using namespace std;
#define MAX 300300
inline 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<int> S;set<int>::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;   
}

【LOJ#3146】[APIO 2019]路灯(树套树)

上一篇:winform批量更新数据_长时间的执行会导致界面卡死


下一篇:C# this 关键字