题解 P5445 【[APIO2019]路灯】

· · 题解

P5445 APIO2019 路灯

一道清新的数据结构题...

将连续一段亮着的灯所连接的站点称为一个连通块，考虑点亮/熄灭一盏灯对于答案的贡献。

若点亮了一盏灯，相当于沟通了左右两个连通块，因此我们找出左右两个连通块的左右端点，将它们标记为连通即可。

若熄灭了一盏灯，相当于将一个连通块拆成两个，将两边之间的联系标记成中断即可。

考虑如何实现这个问题。

首先是找到一个点所在的连通块的左右端点，这个可以用两棵线段树来维护（另一篇题解貌似直接set了），点亮的操作相当于是区间赋值（右部连通块中点的左端点修改成左连通块中点的左端点，左连通块中点的右端点修改成右连通块中点的右端点），熄灭同理（左连通块中点的右端点修改成这个路灯左侧的站点，右连通块中点的左端点修改成这个路灯右侧的站点）。

接下来考虑如何统计答案。

构造一个(n+1)\times (n+1)的矩阵M，M_{ij}表示i与j站点的连通性，我们采用代价提前计算的方法，考虑点亮的操作，若操作在t时刻进行，左右连通块区间分别为[l,x],[x+1,r]，那么将矩阵中左上角为(l,x+1)，右下角为(x,r)的子矩阵中所有元素的值增加q-t，表示接下来的所有时刻，它们都将连通。

同理，如果要熄灭一盏灯，将那个子矩阵中的所有元素减少q-t即可，表示接下来的所有时刻，它们都不连通。

需要注意的就是，t时刻询问时如果x,y依然连通，由于我们采用代价提前计算，所以需要减掉当前时刻之后的代价，即q-t。若x,y现在不连通，那么之后的代价已经在曾经的某个时候减掉了，不需要再处理。

于是现在我们要解决子矩阵加，单点求值。

什么？CDQ？如果在线呢？

通过差分将子矩阵加转化成四个点的加减，单点求值转化成前缀矩阵求和。然后就是常规的树状数组套权值线段树问题。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=400010;
int tot,cnt,n,q,x,y,ans,rt[MAXN],val[MAXN<<5],ch[MAXN<<5][2],lp[2][4*MAXN];    //rt,val,ch为BIT套权值线段树用，lp为维护连通块左右端点用
char s[MAXN];
void upd (int p) {
    val[p]=val[ch[p][0]]+val[ch[p][1]];
    return;
}
void modify_t (int &rt,int l,int r,int pos,int v) {
    if (!rt) {rt=++tot;}
    if (l==r) {val[rt]+=v;return;}
    int mid=(l+r)>>1;
    if (pos<=mid) {modify_t(ch[rt][0],l,mid,pos,v);}
    else {modify_t(ch[rt][1],mid+1,r,pos,v);}
    upd(rt);
    return;
}
int query_t (int rt,int l,int r,int xl,int xr) {
    if (xr<l||r<xl) {return 0;}
    if (xl<=l&&r<=xr) {return val[rt];}
    int mid=(l+r)>>1;
    return query_t(ch[rt][0],l,mid,xl,xr)+query_t(ch[rt][1],mid+1,r,xl,xr);
}
void modify (int x,int y,int v) {
    if (y>n+1) {return;}
    for (int i=x;i<=n+1;i+=(i&(-i))) {modify_t(rt[i],1,n+1,y,v);}
    return;
}    //差分后的单点修改
int query (int x,int y) {
    int res=0;
    for (int i=x;i;i-=(i&(-i))) {res+=query_t(rt[i],1,n+1,1,y);}
    return res;
}    //前缀矩阵和
void pd (int p) {
    if (lp[0][p]) {
        lp[0][p*2]=lp[0][p*2+1]=lp[0][p];
        lp[0][p]=0;
    }
    if (lp[1][p]) {
        lp[1][p*2]=lp[1][p*2+1]=lp[1][p];
        lp[1][p]=0;
    }
    return;
}    //区间覆盖的标记下传
void buildt (int p,int l,int r) {
    if (l==r) {lp[0][p]=lp[1][p]=l;return;}
    int mid=(l+r)>>1;
    buildt(p*2,l,mid),buildt(p*2+1,mid+1,r);
    return;
}
void modify2 (int k,int p,int l,int r,int xl,int xr,int v) {
    if (xr<l||r<xl) {return;}
    if (xl<=l&&r<=xr) {lp[k][p]=v;return;}
    pd(p);
    int mid=(l+r)>>1;
    modify2(k,p*2,l,mid,xl,xr,v),modify2(k,p*2+1,mid+1,r,xl,xr,v);
}    //区间覆盖
int query2 (int k,int p,int l,int r,int pos) {
    if (l==r) {return lp[k][p];}
    pd(p);
    int mid=(l+r)>>1;
    if (pos<=mid) {return query2(k,p*2,l,mid,pos);}
    else {return query2(k,p*2+1,mid+1,r,pos);} 
}    //单点查询
bool chk (int x,int y) {
    return (query2(0,1,1,n+1,x)==query2(0,1,1,n+1,y));
}    //判断两点是否连通，只要看所在连通块左端点是否相等
void con (int x,int v) {
    int l=query2(0,1,1,n+1,x),r=query2(1,1,1,n+1,x+1);
    modify2(1,1,1,n+1,l,x,r),modify2(0,1,1,n+1,x+1,r,l);
    modify(l,x+1,q-v),modify(l,r+1,v-q),modify(x+1,x+1,v-q),modify(x+1,r+1,q-v);
    return;
}
void del (int x,int v) {
    int l=query2(0,1,1,n+1,x),r=query2(1,1,1,n+1,x+1);
    modify2(1,1,1,n+1,l,x,x),modify2(0,1,1,n+1,x+1,r,x+1);
    modify(l,x+1,v-q),modify(l,r+1,q-v),modify(x+1,x+1,q-v),modify(x+1,r+1,v-q);
    return;
}
int main () {
    scanf("%d%d%s",&n,&q,s+1);
    buildt(1,1,n+1); 
    for (int i=1;i<=n;i++) {
        if (s[i]=='1') {con(i,0);}
    }
    for (int i=1;i<=q;i++) {
        scanf("%s%d",s+1,&x);
        if (s[1]=='q') {
            scanf("%d",&y);
            ans=query(x,y);
            if (chk(x,y)) {ans-=q-i;}
            printf("%d\n",ans);
        } else {
            if (chk(x,x+1)) {del(x,i);}
            else {con(x,i);}
        }
    }
    return 0;
}