这个显然是要把询问维护成点对的答案。
考虑用 set 维护所谓连通的极大连续段，那么 \(\texttt{toggle}\) 操作显然只会连接两个段或是断开一个段。
同时在矩阵上更新下答案即可。
然后，由于询问问的是有多少个时刻而非当前是否可到达，所以考虑时间轴上差分。
即，若在 \(i\) 时刻新增 / 减少了段 \((l,r)\)，则令 \((l,l) \sim (r,r)\) 的矩阵都 \(\pm (q - i)\)，意即这个时刻及之后的贡献。
查询的时候，如果这两点还连通，要注意把答案减去 \((q - i)\)，\(i\) 表示当前时刻。
因为时间轴差分并没有考虑到这是在中途询问。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
using namespace std;
const int N = 3e5;
int n,q;
int a[N + 5];
struct note
{
int l,r;
inline bool operator<(const note &o) const
{
return l < o.l;
}
};
set<note> d;
struct node
{
long long val;
int ls,rs;
} seg[(N << 6) + 10];
int rt[N + 5];
void update(int l,int r,int k,int &p,int tl,int tr)
{
static int tot = 0;
if(!p)
p = ++tot;
if(l <= tl && tr <= r)
{
seg[p].val += k;
return ;
}
int mid = tl + tr >> 1;
l <= mid && (update(l,r,k,seg[p].ls,tl,mid),1);
r > mid && (update(l,r,k,seg[p].rs,mid + 1,tr),1);
}
long long query(int x,int p,int tl,int tr)
{
if(!p || tl == tr)
return seg[p].val;
int mid = tl + tr >> 1;
return seg[p].val + (x <= mid ? query(x,seg[p].ls,tl,mid) : query(x,seg[p].rs,mid + 1,tr));
}
inline void update(int x,int l,int r,int k)
{
for(;x <= n + 1;x += lowbit(x))
update(l,r,k,rt[x],1,n + 1);
}
inline long long query(int x,int y)
{
long long ret = 0;
for(;x;x -= lowbit(x))
ret += query(y,rt[x],1,n + 1);
return ret;
}
inline void update(int x,int y,int l,int r,int k)
{
update(x,l,r,k),update(y + 1,l,r,-k);
}
int main()
{
scanf("%d%d",&n,&q);
char ch;
for(register int i = 1;i <= n;++i)
scanf(" %c",&ch),a[i] = ch ^ '0';
for(register int i = 1,temp = 1;i <= n + 1;++i)
if(!a[i])
d.insert((note){temp,i}),update(temp,i,temp,i,q),temp = i + 1;
char op[7];
int x,y;
for(register int i = 1;i <= q;++i)
{
scanf("%s%d",op + 1,&x);
if(op[1] == 't')
{
if(!a[x])
{
set<note>::iterator itl = --d.upper_bound((note){x,0});
set<note>::iterator itr = d.lower_bound((note){x + 1,0});
int l = itl->l,r = itr->r;
update(l,x,l,x,i - q),update(x + 1,r,x + 1,r,i - q);
d.erase(itl),d.erase(itr);
d.insert((note){l,r});
update(l,r,l,r,q - i);
}
else
{
set<note>::iterator it = --d.upper_bound((note){x,0});
int l = it->l,r = it->r;
update(l,r,l,r,i - q);
d.erase(it);
d.insert((note){l,x}),d.insert((note){x + 1,r});
update(l,x,l,x,q - i),update(x + 1,r,x + 1,r,q - i);
}
a[x] ^= 1;
}
else
{
scanf("%d",&y);
set<note>::iterator itl = --d.upper_bound((note){x,0});
set<note>::iterator itr = --d.upper_bound((note){y,0});
if(itl == itr)
printf("%lld\n",query(x,y) - q + i);
else
printf("%lld\n",query(x,y));
}
}
}