题目大意
在 \(n+1\) 个站点之间有 \(n\) 盏路灯，给定 \(0\) 时刻所有路灯的亮灭情况，在接下来的 \(q\) 个时刻，每时刻会发生以下两种事件之一：
-
切换某一盏路灯的亮灭。
-
询问两点之间存在多少时刻使得两点之间的路灯全部亮起。
思路分析
一道不错的数据结构。
首先分析题目，发现这是一个和点对连通性相关的问题，要查询点对之间连通的时间。点对不好处理，考虑扩充一维，将一维的点对变成二维的点。
具体的说，设点对 \((x,y)\) 表示二维平面上的一个点 \((x,y)\)，其点权为在没有后续修改的情况下在所有时刻中两点连通的时间。
那么询问操作就变成了裸的单点查询，不过值得注意的是，如果查询时这两点依然连通，那么还需要将得到的答案减去 \(q-t\)。（\(t\) 为该操作的时刻）
接着考虑修改操作，设 \(l_x,r_x\) 分别为点 \(x\) 所在的极长连通段的左端点和右端点。
容易发现，当 \(x\) 灭时，相当于将连通段 \((l_x,r_x)\) 分裂成 \((l_x,x)\) 和 \((x+1,r_x)\)，同时以 \((l_x,x)\) 为左下端点，\((x+1,r_x)\) 为右上端点的矩形减 \(q-t\)。这代表着如果不考虑接下来的修改，那么从 \(l_x\) 到 \(x\) 中的所有点在接下来的时间中都会与 \(x+1\) 到 \(r_x\) 中的所有点连通。
类似的，当 \(x\) 亮时，相当于将连通段 \((l_x,x)\) 和 \((x+1,r_{x+1})\) 合并成 \((l_x,r_{x+1})\)，同时以 \((l_x,x)\) 为左下端点，\((x+1,r_{x+1})\) 为右上端点的矩形加 \(q-t\)。
那么这就变成了一个单点查区间加的二维数点问题，可以将一次矩形加差分成四个单点修改，这就是一个一般的区间查单点加的二维数点问题。
- 如何维护 \(l_x,r_x\)。
可以用类似于 ODT 的方法，用 set 进行维护。
具体的说，在 set 中储存所有的极长连通段的左右端点，合并时 lower_bound 一下，然后删除左右两个，再插入一个新的就可以了，分裂类似。
代码
这里使用树状数组套线段树实现二维数点。
时间复杂度 \(O(n\log^2n)\)，但常数较大，不吸氧会 T 一个点。（set 常数大，树套树常数也大，合在一起就这样了）
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N=300100;
int n,q,in1,in2;
int light[N<<2];
char ch[N],inp[10];
namespace DCP_2{//普通的二维数点树套树
#define mid (l+r>>1)
#define lowbit(x) ((x)&(-(x)))
int rt[N<<1],tot;
struct STn{
int l,r,sum;
}a[N<<7];
void change(int &p,int l,int r,int x,int k){
if(!p) p=++tot;a[p].sum+=k;
if(l==r) return ;
if(x<=mid) change(a[p].l,l,mid,x,k);
else change(a[p].r,mid+1,r,x,k);
}
int ask(int p,int l,int r,int x,int y){
if(!p||x>y||l>y||r<x) return 0;
if(x<=l&&r<=y) return a[p].sum;
return ask(a[p].l,l,mid,x,y)+ask(a[p].r,mid+1,r,x,y);
}
void add(int x,int y,int k){
for(;x<=n+1;x+=lowbit(x)) change(rt[x],1,n+1,y,k);
}
int query(int x,int y){
int ans=0;
for(;x;x-=lowbit(x)) ans+=ask(rt[x],1,n+1,1,y);
return ans;
}
}
namespace SET{//维护极长颜色段
#define SNI set<Node>::iterator
struct Node{
int l,r;
bool operator < (const Node &b) const{
return r<b.r;
}
};
set<Node> s;
void init(){
for(int i=1;i<=n;i++) s.insert(Node{i,i});
}
void merge(int x1,int x2,int y1,int y2){//将(x1,x2) 和 (y1,y2) 合并成 (x1,y2)
s.erase(Node{x1,x2});
s.erase(Node{y1,y2});
s.insert(Node{x1,y2});
}
void split(int x1,int x2,int y1,int y2){//将(x1,y2) 分裂成 (x1,x2) 和 (y1,y2)
s.erase(Node{x1,y2});
s.insert(Node{x1,x2});
s.insert(Node{y1,y2});
}
bool same(int x,int y){//判断是否在同一个极长连通块
return s.lower_bound(Node{0,x})->l==s.lower_bound(Node{0,y})->l;
}
}
using namespace DCP_2;
using namespace SET;
void ADD(int x1,int y1,int x2,int y2,int k){//差分成四个单点修改
add(x1,y1,k);add(x2+1,y2+1,k);
add(x1,y2+1,-k);add(x2+1,y1,-k);
}
int main(){
scanf("%d%d",&n,&q);n++;
scanf("%s",ch+1);
init();
for(int i=1;i<=n-1;i++){
light[i]=ch[i]-'0';
if(light[i]) merge(s.lower_bound(Node{0,i})->l,i,i+1,i+1);
//合并初始块
}
for(SNI it=s.begin();it!=s.end();it++)
ADD(it->l,it->l,it->r,it->r,q);//更新初始时间
for(int i=1;i<=q;i++){
scanf("%s",inp+1);
if(inp[1]=='q'){
scanf("%d%d",&in1,&in2);
int ans=query(in1,in2);
if(same(in1,in2)) ans-=q-i;//特判
cout<<ans<<'\n';
}
if(inp[1]=='t'){
scanf("%d",&in1);
SNI it=s.lower_bound(Node{0,in1});
int x1=it->l,x2=in1,y1=in1+1;//找到 lx,x,x+1,rx,r(x+1)
if(light[in1]){
int y2=it->r;
ADD(x1,y1,x2,y2,i-q);
split(x1,x2,y1,y2);
}
else{
int y2=(++it)->r;
ADD(x1,y1,x2,y2,q-i);
merge(x1,x2,y1,y2);
}
light[in1]^=1;//更新状态
}
}
return 0;
}