整合的时候发现有个别补题, 但是没有记录, 就新建了页面, 所以这个日期有点不对 QAQ
C.Cheating and Stealing
由 W 和 L 组成的长度为 $n$ 的字符串, 分别代表我赢和输. 定义局分 $k$, 当一个人(自己或对方)得分不低于 $k$ 且净胜 $2$ 分, 一局结束. 求局分 $k$ 取 $1, 2, \dots, n$ 能赢几局.
$1 \le n \le 10^6$
拿到题完全无从下手, 因为不会算复杂度觉得完全不可做.
首先对局分 $i$, 一共进行 $O(\farc{n}{i})$ 局, 如果能够 $O(1)$ 判断一局的输赢, 那么枚举 $i$ 并求和, 复杂度是 $O(\sum_{i=1}^n \frac{n}{i}) = O(n \log n)$. 这样复杂度就对了. 神奇, 第一次碰到这样猜复杂度的题.
然后考虑局分为 $k$ 的一局, 一个必要条件是, 有一个人胜 $k$, 在字符串里, 就是当前位置后的第 $k$ 个 W 或第 $k$ 个 L. 这里可以预处理. 以 W 为例, $posW_i$ 表示第 $i$ 个 W 的位置, 由于起点不固定, 所以要考虑前面的个数, 设 $sumW_i$ 为 W 的前缀和, 那么, 假设当前位置在 $i$, 之后第 $k$ 个 W 的位置就是 $posW(sumW_i + k)$.
然后考虑第二个条件, 即净胜两分. 先考虑一种情况, 第 $k$ 个 W 比第 $k$ 个 L 先出现. 如果第 $k$ 个 W 的位置为 $p_{wk}$, 那么先看看从开始到 $p_{wk}$ L 的个数, 如果少于 $k-1$ 个, 就结束了. 否则看看从开始到 $p_{wk}+1$ 这个位置, 是不是有 $k$ 个 L. 不是的话证明 $p_{wk} + 1$ 是 W, 到这个位置一共有 $k+1$ 个 W. 而前面最多 $k-1$ 个 L, W 比 L 多两个, 结束. 如果 $p_{wk} + 1$ 是 L, 那么到 $p_{wk} + 1$, W 和 L 的数量相等, 需要继续比赛. 很容易发现, 如果从这里往后两个两个看, 两个不一样, 那么比分相等, 继续比赛. 如果一样, 那么就结束了. 往后两个两个找是不是一样, 可以预处理, 从后往前算一个数组 $f_i$, 表示 $i$ 位置往后两个两个看, 第一次出现两个一样的位置(结束位置, 设到后面那个位置). L 考虑完全一样. 这样就 $O(1)$ 判断一局了.
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
|
int pls(LL a, LL b) {
a += a < 0 ? P : 0, b += b < 0 ? P : 0;
return a + b >= P ? a + b - P : a + b;
}
int mult(LL a, LL b) {
a += a < 0 ? P : 0, b += b < 0 ? P : 0;
return a * b >= P ? a * b % P : a * b;
}
int n, sumW[MAXN], sumL[MAXN], posW[MAXN], posL[MAXN], ans = 0, base = 0, f[MAXN];
char str[MAXN];
int main() {
scanf("%d%s", &n, str+1);
base = n+1;
memset(posW, INTINF, sizeof(posW));
memset(posL, INTINF, sizeof(posL));
for (int i = 1; i <= n; i++) {
sumW[i] = sumW[i-1] + (str[i] == 'W');
sumL[i] = sumL[i-1] + (str[i] == 'L');
posW[sumW[i]] = posW[sumW[i]] < INTINF ? posW[sumW[i]] : i;
posL[sumL[i]] = posL[sumL[i]] < INTINF ? posL[sumL[i]] : i;
}
f[n] = f[n+1] = INTINF;
f[n-1] = str[n-1] == str[n] ? n : INTINF;
for (int i = n-2; i > 0; i--)
f[i] = str[i] == str[i+1] ? i+1 : f[i+2];
int pw = 1;
for (int k = 1; k <= n; k++) {
int i = 1, res = 0;
while (i <= n) {
int pkw = sumW[i-1] + k <= n ? posW[sumW[i-1] + k] : INTINF;
int pkl = sumL[i-1] + k <= n ? posL[sumL[i-1] + k] : INTINF;
int p = min(pkw, pkl);
if (p > n)
break;
if (abs(sumW[p] - sumW[i-1] - (sumL[p] - sumL[i-1])) >= 2)
res += pkw < pkl;
else {
if (pkw < pkl) {
if (p < n) {
if (str[p+1] == 'W')
res++, p++;
else {
p = f[p+2];
if (p <= n)
res += (sumW[p] - sumW[i-1]) > (sumL[p] - sumL[i-1]);
}
}
}
else {
if (p < n) {
if (str[p+1] == 'L')
p++;
else {
p = f[p+2];
if (p <= n)
res += (sumW[p] - sumW[i-1]) > (sumL[p] - sumL[i-1]);
}
}
}
}
i = p+1;
}
ans = pls(ans, mult(res, pw));
pw = mult(pw, base);
}
printf("%d\n", ans);
return 0;
}
|
长度为 $n$ 的序列, $q$ 次查询, 每次询问 $l, r, k$, 对于 $i = 0 : k-1$, 将区间 $[l-i, r+i]$ 中的数去重排序, 最长连续段的长度, 乘以 $(n+1)^i$ 统计到答案中.
$1 \le n, q \le 10^5, 1 \le a_i \le n, 1 \le l - k + 1 \le l \le r \le r + k - 1 \le n, \sum k \le 10^7$
(一开始在想线段树区间合并怎么维护, 突然发现还有个枚举 $i$ 从 $0$ 到 $k$, 人就傻了)
正解是莫队! 作为一个反对莫队选手, 反正我是没看出来是莫队. 现在想想好像挺有道理? 首先是区间询问, 可以离线, 然后线段树做不了, 更多地, 因为一个询问就要拓展 $k$ 次, 而 $\sum k \le 10^7$. 正好如果全给他 $O(1)$ 暴力维护多出来的点 (如果是数据结构的话每次维护多出来的点就是 $O(\log n)$, 就T了), 综上, 莫队没跑了.
然后就是怎么维护连续段的问题了. 题解说用链表, 我不太会, 我这里用的并查集. 然后删除操作很麻烦, 并查集没法删除啊! 如果是链表, 确实可以删除, 但是不好维护删除以后两个链表的大小. 所以需要回滚莫队. 然后多出来的点可以当作临时信息, 就没了. 并查集回滚的话开个栈记录一下修改前的信息, 回滚直接改回去就行了. 链表应该也差不多? 不太清楚.
一点小细节, 回滚还是要注意临时信息一定不要写错(老把永久信息改掉,,,), 并查集在路径压缩的时候一些点的信息会边, 如果是临时信息, 注意记录. 长度小于 $\sqrt n$ 的询问可以直接暴力. 由于 $query_l$ 在不同块的时候, 指针 $r$ 会往回走, 前面说过了不好维护, 而且这里如果再开一个栈进行回滚永久信息的话, 不太方便(其实好像也可以), 所以直接清空所有信息重新开始做这一块的询问即可.
复杂度 $O(\alpha n \sqrt n + \alpha \sum k)$, $\alpha$ 是因为并查集路径压缩要记录回滚信息. 如果用链表应该不带 $\alpha$.
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
|
int n, q, block_size, id[MAXN], a[MAXN], cnt[MAXN], tmpcnt[MAXN], ans[MAXN], pw[MAXN];
int getBlockR(int block_id) { return min(block_id * block_size, n); }
int getBlockL(int block_id) { return getBlockR(block_id-1) + 1; }
struct Query {
int idx, l, r, k;
bool operator < (const Query &Q) const {
return id[l] == id[Q.l] ? r < Q.r : id[l] < id[Q.l];
}
};
vector<Query> query[MAXB];
struct Node {
int u, f, s;
};
vector<Node> stk;
int fa[MAXN], sz[MAXN];
void init(int n) {
for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
}
int find(int x, int flag_tmp = false) {
if (x == fa[x])
return x;
if (flag_tmp)
stk.push_back({x, fa[x], sz[x]});
return fa[x] = find(fa[x], flag_tmp);
}
// 返回合并后的大小
int uni(int x, int y, bool flag_tmp) {
int fx = find(x, flag_tmp), fy = find(y, flag_tmp);
if (fx == fy)
return 0;
if (flag_tmp) {
stk.push_back({fx, fa[fx], sz[fx]});
stk.push_back({fy, fa[fy], sz[fy]});
}
fa[fx] = fy;
sz[fy] += sz[fx];
return sz[fy];
}
bool vis[MAXN], tmpvis[MAXN];
int add(int c, bool flag_tmp = false) {
int mx = 1;
if (vis[c+1] || tmpvis[c+1])
mx = max(mx, uni(c, c+1, flag_tmp));
if (vis[c-1] || tmpvis[c-1])
mx = max(mx, uni(c, c-1, flag_tmp));
if (flag_tmp)
tmpvis[c] = 1;
else
vis[c] = 1;
return mx;
}
void rollback() {
memset(tmpvis, 0, sizeof(tmpvis));
while (stk.size()) {
auto[u, f, s] = stk.back();
stk.pop_back();
fa[u] = f, sz[u] = s;
}
}
void solve() {
init(n);
for (auto[idx, l, r, k] : query[0]) {
int mx = 1;
for (int p = l; p <= r; p++)
mx = max(mx, add(a[p]));
int res = mx;
for (int i = 1; i < k; i++) {
mx = max(mx, add(a[r+i]));
mx = max(mx, add(a[l-i]));
res = pls(res, mult(mx, pw[i]));
}
ans[idx] = res;
// 结束, 重置ufs
for (int i = l-k; i <= r+k; i++)
fa[a[i]] = a[i], sz[a[i]] = 1, vis[a[i]] = 0;
}
for (int i = 1; i <= MAXB-30; i++) if (query[i].size()) {
init(n);
memset(vis, 0, sizeof(vis));
sort(query[i].begin(), query[i].end());
int l = getBlockL(id[query[i][0].l]+1), r = l-1;
int mx = 1;
for (Query Q : query[i]) {
// 维护永久信息
while (r < Q.r)
mx = max(mx, add(a[++r]));
// 暴力维护临时信息
int tmpmx = mx;
for (int j = Q.l; j <= min(Q.r, getBlockR(id[Q.l])); j++)
tmpmx = max(tmpmx, add(a[j], 1));
int res = tmpmx;
for (int i = 1; i < Q.k; i++) {
tmpmx = max(tmpmx, add(a[Q.r+i], 1));
tmpmx = max(tmpmx, add(a[Q.l-i], 1));
res = pls(res, mult(tmpmx, pw[i]));
}
ans[Q.idx] = res;
// 回滚临时信息
rollback();
}
}
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
pw[0] = 1;
for (int i = 1; i <= n; i++)
pw[i] = mult(pw[i-1], n+1);
block_size = sqrt(n);
for (int i = 1; i <= n; i++)
id[i] = (i-1) / block_size + 1;
for (int i = 1; i <= q; i++) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
// 区间长度小于 sqrt n 的可以直接暴力, 存在 query[0] 里暴力
if (r - l + 1 <= block_size)
query[0].push_back({i, l, r, k});
// 其他莫队做, 由于回滚较麻烦, 所以每块重新开始做, 按块分
else
query[id[l]].push_back({i, l, r, k});
}
solve();
for (int i = 1; i <= q; i++)
printf("%d\n", ans[i]);
return 0;
}
|
大常数选手喜提用时 rk-5. 懒得截图了QAQ.
长度为 $n$ 的序列, $m$ 次询问, 求有多少个非空子区间, 满足区间极差严格大于 $k$.
$1 \le n \le 10^5, 1 \le m \le 200, 1 \le k \le 10^9$
这种题就是固定一端, 算另一端的取值有多少个. 如果是枚举 $r$, 然后用数据结构更新前面的 $l$, 那么复杂度将是 $O(nm\log n)$, 会T掉. 所以对每个询问, 要找一个 $O(n)$ 的做法. 那么数据结构这条路是行不通了. 另一个思路是尝试双指针, 如果考虑题目的反面, 算极差小于等于 $k$ 的区间, 那么会发现, 窗口缩短时, 极差一定会减小, 所以另一端就可能可以拓展. 于是两个指针都是单调的. 这样就找到了 $O(n)$ 的做法. 由于需要极差, 所以免不了维护区间的两个最值. 考虑枚举 $l$, 看 $r$ 最远能够到那儿. 移动 $r$, 同时维护两个最值. 当 $r$ 不能移动时, 记录当前 $l$ 的贡献. 然后让 $l$ 增加, 这样区间就减小了一个. 如果减小的这一个是最值, 那么最值需要重新更新. 这里就可以用st表做RMQ, 直接 $O(1)$ 查询. 然后再看看 $r$ 能到多远. 如果 $l = r$, $r$ 无法增, 这个区间就整体向下一个, 然后算 $r$ 能到多远. 预处理st表 $O(n \log n)$, 一次查询 $O(n)$, 总复杂度 $O(n \log n + nm)$.
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
|
int n, q, a[MAXN], lg[MAXN], pw[MAXN], st_min[MAXN][30], st_max[MAXN][30];
void init() {
lg[0] = -1, pw[0] = 1;
for (int i = 1; i <= n; i++) lg[i] = lg[i>>1] + 1;
for (int i = 1; i <= lg[n]; i++) pw[i] = pw[i-1] << 1;
}
void build(int data[]) {
for (int i = 1; i <= n; i++) st_min[i][0] = st_max[i][0] = data[i];
for (int j = 1; j <= lg[n]; j++)
for (int i = 1; i + pw[j] <= n + 1; i++)
st_min[i][j] = min(st_min[i][j-1], st_min[i+pw[j-1]][j-1]),
st_max[i][j] = max(st_max[i][j-1], st_max[i+pw[j-1]][j-1]);
}
int queryMin(int l, int r) {
int k = lg[r - l + 1];
return min(st_min[l][k], st_min[r+1-pw[k]][k]);
}
int queryMax(int l, int r) {
int k = lg[r - l + 1];
return max(st_max[l][k], st_max[r+1-pw[k]][k]);
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d", a + i);
init();
build(a);
while (q--) {
int k;
scanf("%d", &k);
LL invalid = 0;
int l = 1, r = 1;
int mn = a[1], mx = a[1];
for (int l = 1; l <= n; l++) {
if (l > r)
r = l;
if (l == 1 || a[l-1] == mx || a[l-1] == mn) {
mx = queryMax(l, r);
mn = queryMin(l, r);
for ( ; r <= n && max(mx, a[r]) - min(mn, a[r]) <= k; r++) {
mx = max(mx, a[r]);
mn = min(mn, a[r]);
}
r--;
}
invalid += r - l + 1;
}
printf("%lld\n", 1ll * n * (n+1) / 2 - invalid);
}
return 0;
}
|