【Luogu】 P5445 [APIO2019] 路灯

题目链接

点击打开链接

题目解法

转化很妙

考虑关路灯 $x$ 的操作
令左边第一个未关的路灯为 $L$，右边第一个未关的路灯为 $R$，那么这一次会影响的区间即为 $l\in [L+1,x],r\in [x,R-1]$，既然有 2 个限制，那么我们把限制变成二维平面上的矩阵，即把左上为 $(L+1,x)$，右下为 $(x,R-1)$ 的矩阵变为 0
开路灯的操作类似

考虑询问的是什么？
即 $1$ 到 $q-1$ 次每个版本 $(x,y)$ 位置的和
考虑给矩阵定义一个增加（或减少）值，使查询变成只要查询第 $i$ 个版本的 $(x,y)$ 值
这里直接给出：对于第 $i$ 个操作，加上或减去值为 $i-q$
考虑先开路灯，再关路灯的操作，即为 $T-i-(T-j)=j-i$，恰好为答案，这可以拓展到多个开关路灯的操作
这里需要一个特判，如果查询第 $i$ 个版本从 $x$ 可以到 $y$，那么答案需要 $-(q-i)$

可以把矩形变成 4 个区域的加减，然后不难发现，这就是一个三维偏序，可以考虑离线 $cdq$
时间复杂度 $O(nlo{g}^{2}n)$

#include <bits/stdc++.h>
#define lowbit(x) x&-x
using namespace std;
const int N=300100;
struct Node{ int x1,x2,v,op,id;}q[N*10],t[N*10];
int idx,n,m,state[N],ans[N],tr[N];
char str[N];
set<int> se;
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void ADD(int x,int y,int v){ q[++idx]={x,y,v,0,0};}
void add_square(int x1,int x2,int y1,int y2,int v){ADD(x2,y2,v);if(x1>1) ADD(x1-1,y2,-v);if(y1>1) ADD(x2,y1-1,-v);if(x1>1&&y1>1) ADD(x1-1,y1-1,v);
}
void work(int x,int t){if(!state[x]){auto it=se.upper_bound(x);int R=*it,L=*(--it);se.insert(x);add_square(L+1,x,x,R-1,-(m-t));}else{se.erase(x);auto it=se.upper_bound(x);int R=*it,L=*(--it);add_square(L+1,x,x,R-1,m-t);}
}
void add(int x,int y){ for(;x<=n;x+=lowbit(x)) tr[x]+=y;}
int ask(int x){if(!x) return 0;int res=0;for(;x;x-=lowbit(x)) res+=tr[x];return res;
}
void cdq(int l,int r){if(l==r) return;int mid=(l+r)>>1;cdq(l,mid),cdq(mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid||j<=r){if(j>r||(i<=mid&&q[i].x1>=q[j].x1)){if(!q[i].op) add(q[i].x2,q[i].v);t[++k]=q[i],i++;}else{if(q[j].op) ans[q[j].id]+=ask(n)-ask(q[j].x2-1);t[++k]=q[j],j++;}}for(i=l;i<=mid;i++) if(!q[i].op) add(q[i].x2,-q[i].v);for(int i=1,j=l;i<=k;i++,j++) q[j]=t[i];
}
bool con(int x,int y){ return ask(y)-ask(x-1)==y-x+1;}
int main(){n=read(),m=read();scanf("%s",str+1);for(int i=1;i<=n;i++) state[i]=str[i]-48;add_square(1,n,1,n,m);se.insert(0),se.insert(n+1);for(int i=1;i<=n;i++) if(state[i]) add(i,1);for(int i=1;i<=n;i++) if(!state[i]) work(i,0);for(int i=1;i<=m;i++){char op[10];scanf("%s",op);if(op[0]=='t'){int x=read();state[x]^=1,work(x,i);ans[i]=-1e9;if(state[x]) add(x,1);else add(x,-1);}else{int x=read(),y=read();y--;if(con(x,y)) ans[i]=-(m-i);q[++idx]={x,y,0,1,i};}}memset(tr,0,sizeof(tr));cdq(1,idx);for(int i=1;i<=m;i++) if(ans[i]!=-1e9) printf("%d\n",ans[i]);return 0;
}