题解 P5445 【[APIO2019]路灯】

Fading · 2019-07-07 13:10:09 · 题解

看到点对，什么思路？转化为平面问题。

显然点对连通性可以转化到平面上。

设点对(x,y)在平面上表示为坐标(x,y)。

就是把点对映射到坐标上。

我们用 set 来维护亮灯的连续段。

设当前时间为t，总时间为T。

对于一个点x,设x可以到达最左边的位置为lb，x+1可到达最右边的位置为rb。

修改

如果[x,x+1]之间的路灯开了，那么显然[lb,x]内的点与[x+1,rb]内的点就可以连通了！

正好相等！

注意：如果查询的两点依然连通，答案还需要减去(T-t)

我们成功把问题转化为了普通的矩形加，单点查问题。

这就是普普通通的二维数点问题。

由于有时间轴，所以等价于三维偏序问题。

所以就有两种解法：

算法1：CDQ分治+扫描线。

很显然这个可以用 CDQ 分治维护。

矩形加不好处理，先用扫描线把矩形差分成4个操作（和\texttt{[HNOI2015]接水果} 很像）。

第一维时间排序掉，第二维x坐标 CDQ ，第三维y坐标用差分+树状数组。

算法2：树套树+扫描线。

用树套树可以支持在线。

先把矩形加用扫描线差分成4个操作。

然后就是普普通通的单点修改，区间查询了。

这个不就是树套树可以维护的东西吗？

树状数组维护x坐标，动态开点线段树维护y坐标即可。

总结

两个算法复杂度都是O(n\log_2^2n)的。

而且有树状数组在，常数巨小。可以通过此题。

怎么开心怎么写吧。我写了算法2（因为我CDQ老写错）。

#include<bits/stdc++.h>
#define ll long long
#define ljc 998244353
using namespace std;
#define gc getchar
inline ll read(){
    register ll x=0,f=1;char ch=gc();
    while (!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
    while (isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=gc();}
    return (f==1)?x:-x;
}
int n,N,T,root[600001],cnt;
struct node{
    int l,r,sum;
}seg[15020001];
#define mid ((lb+rb)>>1)
void Update(int &rt,int lb,int rb,int pos,int w){
    if (!rt) rt=++cnt;seg[rt].sum+=w;
    if (lb==rb) return;
    (mid>=pos?Update(seg[rt].l,lb,mid,pos,w):Update(seg[rt].r,mid+1,rb,pos,w));
}
int Query(int rt,int lb,int rb,int l,int r){
    if (!rt||lb>r||rb<l) return 0;
    if (lb>=l&&rb<=r) return seg[rt].sum;
    return Query(seg[rt].l,lb,mid,l,r)+Query(seg[rt].r,mid+1,rb,l,r);
}
inline void update(int pos,int r,int w){
    for (;pos<=n+1;pos+=pos&-pos) Update(root[pos],1,n+1,r,w);
}
inline int query(int posx,int posy){
    int ans=0;
    for (;posx;posx-=posx&-posx) ans+=Query(root[posx],1,n+1,1,posy);
    return ans;
}
inline void Add(int x1,int y1,int x2,int y2,int W){
    update(x1,y1,W);update(x1,y2+1,-W);
    update(x2+1,y1,-W);update(x2+1,y2+1,W);
}
struct road{
    int l,r;
};
inline bool operator < (road a,road b){
    return a.r<b.r;
} 
set<road> S;
set<road>::iterator it;
bool zt[2000001];
signed main(){
    n=1+read(),T=read();N=n-1;
    for (int i=1;i<=n;i++){
        S.insert((road){i,i});
    }
    for (int i=1;i<=N;i++){
        char ch=gc();
        while (!isdigit(ch)) ch=gc();
        zt[i]=(ch-48);
        if (zt[i]){
            it=S.lower_bound((road){0,i+1});it--;
            int lb=(*it).l;
            S.erase(it);S.erase((road){i+1,i+1});
            S.insert((road){lb,i+1});
        }
    }
    for (it=S.begin();it!=S.end();++it){
        Add((*it).l,(*it).l,(*it).r,(*it).r,T);
    }
    for (int t=1;t<=T;t++){
        char s[11];scanf("%s",s+1);
        if (s[1]=='q'){
            int x=read(),y=read();
            int ans=query(x,y);
            int X=(*(S.lower_bound((road){0,x}))).l;
            int Y=(*(S.lower_bound((road){0,y}))).l;
            printf("%d\n",ans-(T-t)*(X==Y));
        }else if (s[1]=='t'){
            int x=read();
            if (zt[x]==1){
                it=S.lower_bound((road){0,x});
                int lb1=(*it).l,rb1=x;
                int lb2=x+1,rb2=(*it).r;
                Add(lb1,lb2,rb1,rb2,t-T);
                S.erase((road){lb1,rb2});
                S.insert((road){lb1,rb1});S.insert((road){lb2,rb2}); 
                zt[x]^=1;
            }else{
                it=S.lower_bound((road){0,x});
                int lb1=(*it).l,rb1=x;
                it++;
                int lb2=x+1,rb2=(*it).r;
                Add(lb1,lb2,rb1,rb2,T-t);
                S.erase((road){lb1,rb1});S.erase((road){lb2,rb2});
                S.insert((road){lb1,rb2}); 
                zt[x]^=1;
            }
        }
    }
    return 0;
}