[APIO2019]路灯

Description

一辆自动驾驶的出租车正在 Innopolis 的街道上行驶。该街道上有 $n + 1$ 个停车站点,它们将街道划分成了 $n$ 条路段。每一路段都拥有一个路灯。当第 $i$ 个路灯亮起,它将照亮连接第 $i$ 与第 $i + 1$ 个站点的路段。否则这条路段将是黑暗的。

安全起见,出租车只能在被照亮的路段上行驶。换言之,出租车能从站点 $a$ 出发到达站点 $b(a < b)$ 的条件是:连接站点 $a$ 与 $a + 1$,$a + 1$ 与 $a + 2$,……,$b - 1$ 与 $b$ 的路段都被照亮。

在经过一些意外故障或修理之后,街道上的路灯可能是亮起的,也可能是熄灭的。

现在给定 $0$ 时刻时,街道上路灯的初始状态。之后 $1, 2, \dots, q$ 时刻,每时刻会发生下列两种事件之一:

  • $\texttt{toggle}\ i$:切换第 $i$ 个路灯的状态。具体地说,若路灯原来亮起,则现在将熄灭;若路灯原来熄灭,则现在将亮起。
  • $\texttt{query}\ a\ b$:出租车部门的负责人想知道,从 $0$ 时刻起到当前时刻,有多少个时刻满足:出租车能够从站点 $a$ 出发到达站点 $b$。

请你帮助出租车部门的负责人回答他们的问题。

$$
1 \le n, q \le 3 \times 10 ^5 \\
\texttt{Time Limit = 5000ms}
$$

Solution

考虑一个很麻烦的东西:将所有形如 $a, b$ 的询问抽象为二维平面上的点 $(a, b)$,其点权即为询问答案。

如果在时刻 $t$ 将第 $i$ 盏路灯点亮,设 $l$ 为第 $i$ 个站点向左能延伸到的最远站点,$r$ 为第 $i$ 个站点向右能延伸的最远站点,那么便将所有 $x, y(x \in [l, i], y \in [i + 1, r])$ 的询问的权值便加上 $q + 1 - t$,表示在 $[t, q]$ 这段时间区间上 $x, y$ 这两个站点连通。熄灭同理,减去即可。

之前对上面的处理方式感到奇怪:如果如此计算,如果在加之后没有减,那么统计出的答案不会错吗?后来发现这是单点询问,所以这个情况相当于这个时刻 $x, y$ 连通,直接判一下减去 $q + 1 - t$ 即可。若当前时刻 $x, y$ 未连通,点权即询问答案。

连通用 std::set 维护,矩形加单点查还能离线,$\texttt{CDQ}$ 是很好的选择。

注意树状数组下标应该到 $n + 1$,不要将矩形的端点传错了参数(之前传的是两维的坐标区间,而不是矩形端点)。

$O(n \log ^2 n)$。

Code

常数巨大…

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
/**********************************************************
* Author : EndSaH
* Email : hjxhb1@gmail.com
* Created Time : 2019-09-24 08:03
* FileName : wib.cpp
* Website : https://endsah.cf
* *******************************************************/

#include <cstdio>
#include <cctype>
#include <set>
#include <algorithm>

using ptr = struct Oper*;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The message in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define __bufsize (1 << 21 | 1)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[50];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__________;

inline int read()
{
register int x = 0;
register char ch;
while (!isdigit(ch = getchar()));
while (x = x * 10 + (ch & 15), isdigit(ch = getchar()));
return x;
}

inline void read(char* str)
{
while (isspace(*str = getchar()));
while (!isspace(*++str = getchar()))
if (*str == EOF)
break;
*str = '\0';
}

template<typename _INT>
inline void write(_INT x)
{
while (*++stkpos = x % 10 ^ 48, x /= 10, x);
while (stkpos != _stk)
putchar(*stkpos--);
}

template<typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template<typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

const int maxN = 3e5 + 5;

int n, q, cnt, anscnt;
int ans[maxN];
char start[maxN], opt[10];
std::set<int> pos;

struct Oper
{
int x, y, val, opt;

Oper() { }

Oper(int _x, int _y, int _val, int _opt = -1) : x(_x), y(_y), val(_val), opt(_opt) { }
} oper[maxN << 3];

inline void Add(int x1, int y1, int x2, int y2, int val)
{
oper[++cnt] = Oper(x2, y2, val);
if (x1 > 1)
oper[++cnt] = Oper(x1 - 1, y2, -val);
if (y1 > 1)
oper[++cnt] = Oper(x2, y1 - 1, -val);
if (x1 > 1 and y1 > 1)
oper[++cnt] = Oper(x1 - 1, y1 - 1, val);
}

inline bool Cmp(const ptr& a, const ptr& b)
{ return a->x == b->x ? a->y > b->y : a->x > b->x; }

namespace BIT
{
int sum[maxN];

inline void Add(int x, int addval)
{
while (x <= n + 1)
sum[x] += addval, x += x & -x;
}

inline int Query(int x)
{
int res = 0;
while (x)
res += sum[x], x -= x & -x;
return res;
}
}

void CDQ(int l, int r)
{
if (l == r)
return;
static ptr L[maxN << 2], R[maxN << 2];
int mid = (l + r) >> 1, i, j, lcnt = 0, rcnt = 0;

for (i = l; i <= mid; ++i)
if (oper[i].opt == -1)
L[lcnt++] = &oper[i];
for (i = mid + 1; i <= r; ++i)
if (~oper[i].opt)
R[rcnt++] = &oper[i];
if (rcnt == 0)
{
CDQ(l, mid);
return;
}
if (lcnt == 0)
{
CDQ(mid + 1, r);
return;
}
std::sort(L, L + lcnt, Cmp);
std::sort(R, R + rcnt, Cmp);
for (i = 0, j = 0; i < rcnt; ++i)
{
while (j < lcnt and L[j]->x >= R[i]->x)
BIT::Add(L[j]->y, L[j]->val), ++j;
ans[R[i]->opt] += BIT::Query(n + 1) - BIT::Query(R[i]->y - 1);
}
for (--j; ~j; --j)
BIT::Add(L[j]->y, -L[j]->val);
CDQ(l, mid), CDQ(mid + 1, r);
}

inline void Modify(int t, int i)
{
auto l = --pos.lower_bound(i), r = pos.upper_bound(i);
if (pos.count(i))
{
Add(*l + 1, i + 1, i, *r, q + 1 - t);
pos.erase(i);
}
else
{
Add(*l + 1, i + 1, i, *r, t - q - 1);
pos.insert(i);
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("wib.in", "r", stdin);
freopen("wib.out", "w", stdout);
#endif
n = read(), q = read();
read(start + 1);
for (int i = 0; i <= n + 1; ++i)
pos.insert(i);
for (int i = 1; i <= n; ++i)
if (start[i] == '1')
Modify(0, i);
for (int i = 1; i <= q; ++i)
{
read(opt);
int a = read();
if (opt[0] == 'q')
{
int b = read();
++anscnt;
if (!pos.count(a) and *pos.lower_bound(a) >= b)
ans[anscnt] = i - q - 1;
oper[++cnt] = Oper(a, b, 0, anscnt);
}
else
Modify(i, a);
}
CDQ(1, cnt);
for (int i = 1; i <= anscnt; ++i)
write(ans[i]), putchar('\n');
return 0;
}