2021 牛客多校第五场 补题
整合的时候发现有个别补题, 但是没有记录, 就新建了页面, 所以这个日期有点不对 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)$ 判断一局了.
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;
}I.Interval Queries
长度为 $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$.
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.
K.King of Range
长度为 $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)$.
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;
}