看看这个标签列表长度就知道这三天做的题有多杂。
D. 字符串
https://www.becoder.com.cn/contest/5169/problem/4
和 SA 的做法一样，先二分 \(s_{c\sim d}\) 的前缀长度 \(mid\)，只需 check \(s_{c \sim c + mid - 1}\) 是否在 \(s_{a\sim b}\) 中出现过。
考虑怎么快速 check。从 \(c\) 一步一步跳到 \(c+mid-1\) 显然会起飞，考虑到查询是静态的，我们事先预处理一下然后倍增地跳即可。
此时只需看当前状态的 \(\text {endpos}\) 是否在 \([a + mid - 1, b]\) 出现过。
因为这个不能用最大最小简单代替，所以就到了我们喜闻乐见的线段树合并环节。将插入后的每个单点 \(\text {endpos}\) 在权值线段树上更新，在 parent tree 上暴力线段树合并即可。
之前一直有一个误区，就是觉得线段树合并是一次性的，比如用 A 树和 B 树并出来了 C 树之后，A 树和 B 树的数据就无效了。
但这显然是很荒谬的，同样因为我们的查询是静态的，所以完全可以用一种类似于可持久化的方式，建立一些新的点表示合并后的信息状态点，一些可以保留的点就保留作儿子。
在对应的状态上查询即可。
#include <bits/stdc++.h>
const int maxm = 35;
const int maxn = 6e5 + 5;
const int maxk = 8e7 + 5;
struct _ {
int l, f;
int ne[maxm];
_() {}
_(int l1, int f1): l(l1), f(f1) {}
};
_ t[maxn << 1];
int vis[maxn << 1];
int fa[maxn][maxm];
int n, la, tot, siz;
struct { int l, r, u; } t1[maxk];
int tab[maxn << 1], cnt[maxn << 1];
void Init(void) {
la = tot = 1;
t[1] = _(0, 0);
return;
}
void ext(int c) {
int p = la, np = ++tot;
la = tot;
t[np] = _(t[p].l + 1, 0);
while (p && !t[p].ne[c])
t[p].ne[c] = np, p = t[p].f;
if (!p)
t[np].f = 1;
else {
int q = t[p].ne[c];
if (t[q].l == t[p].l + 1)
t[np].f = q;
else {
int nq = ++tot;
t[nq] = _(t[p].l + 1, t[q].f);
std::copy(t[q].ne, t[q].ne + 26, t[nq].ne);
while (p && t[p].ne[c] == q)
t[p].ne[c] = nq, p = t[p].f;
t[q].f = nq;
t[np].f = nq;
}
}
return;
}
int now = 0;
void ins(int &p, int l, int r, int v) {
if (!p)
p = ++now;
++t1[p].u;
if (l == r)
return;
int mid = (l + r) >> 1;
if (v <= mid)
ins(t1[p].l, l, mid, v);
else
ins(t1[p].r, mid + 1, r, v);
return;
}
int ask(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr)
return t1[p].u;
int mid = (l + r) >> 1, res = 0;
if (ql <= mid)
res = ask(t1[p].l, l, mid, ql, qr);
if (qr > mid)
res += ask(t1[p].r, mid + 1, r, ql, qr);
return res;
}
int merge(int p, int q, int l, int r) {
if (!p || !q)
return p + q;
int np = ++now, mid = (l + r) >> 1;
t1[np].u = t1[p].u + t1[q].u;
if (l == r) return np;
t1[np].l = merge(t1[p].l, t1[q].l, l, mid);
t1[np].r = merge(t1[p].r, t1[q].r, mid + 1, r);
return np;
}
int pos[maxn], rt[maxn << 1];
bool check(int x, int a, int b, int c, int d) {
assert(c + x - 1 >= 0);
int p = pos[c + x - 1];
for (int i = siz; ~i; --i)
if (fa[p][i] && t[fa[p][i]].l >= x)
p = fa[p][i];
return ask(rt[p], 0, n - 1, a + x - 1, b) > 0;
}
int solve(int a, int b, int c, int d) {
int l = 1, r = std::min(d - c + 1, b - a + 1), res = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid, a, b, c, d))
l = mid + 1, res = mid;
else
r = mid - 1;
}
return res;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#endif
int m;
std::string s;
std::cin >> n >> m >> s;
Init();
for (int i = 0; i < n; ++i) {
ext(s[i] - 'a');
pos[i] = la;
ins(rt[la], 0, n - 1, i);
}
siz = log(tot) / log(2.0);
for (int i = 1; i <= tot; ++i)
++cnt[t[i].l];
std::partial_sum(cnt + 1, cnt + tot + 1, cnt + 1);
for (int i = 1; i <= tot; ++i)
tab[cnt[t[i].l]--] = i;
for (int i = 1; i <= tot; ++i) {
int u = tab[i];
fa[u][0] = t[u].f;
for (int j = 1; j <= siz; ++j)
fa[u][j] = fa[fa[u][j - 1]][j - 1];
}
for (int i = tot; i; --i) {
int u = tab[i];
if (t[u].f)
rt[t[u].f] = merge(rt[t[u].f], rt[u], 0, n - 1);
}
while (m--) {
int a, b, c, d;
std::cin >> a >> b >> c >> d;
std::cout << solve(a - 1, b - 1, c - 1, d - 1) << '\n';
}
return 0;
}F. Security
https://www.becoder.com.cn/contest/5169/problem/6
对我们来说应该是会 D 就会 F 的。所以只打了 10min。在此嘲讽一下打了很久很久很久很久很久很久很久很久很久很久的这个 zwb 同学。
首先考虑一个大家喜闻乐见的 DFS 求最小字典序。显然地，如果存在和当前位相等的字符，那么优先跳相等字符，进入下一层深搜；否则找到最小的更大字符，然后直接 out。
此时 SAM 就是我们用来判断 \(S_{l, r}\) 中是否存在某状态的工具了。甚至比上一题简单，因为不用写二分和倍增。
值得注意的是如果 \(S_{l, r}\) 包含 \(T\) 那么还要在后面随便加一个字符以字典序保证严格大于 \(T\)。
值得注意的是因为我写的太丑了以至于在 CF 上会光荣 MLE #46。然后分屏左半边看我代码右半边写的 rybp 却没有。啧。为什么呢。
#include <bits/stdc++.h>
const int maxm = 35;
const int maxn = 6e5 + 5;
const int maxk = 8e7 + 5;
struct _ {
int l, f;
int ne[maxm];
_() {}
_(int l1, int f1): l(l1), f(f1) {}
};
_ t[maxn << 1];
int vis[maxn << 1];
int fa[maxn][maxm];
int n, la, tot, siz;
struct { int l, r, u; } t1[maxk];
int tab[maxn << 1], cnt[maxn << 1];
void Init(void) {
la = tot = 1;
t[1] = _(0, 0);
return;
}
void ext(int c) {
int p = la, np = ++tot;
la = tot;
t[np] = _(t[p].l + 1, 0);
while (p && !t[p].ne[c])
t[p].ne[c] = np, p = t[p].f;
if (!p)
t[np].f = 1;
else {
int q = t[p].ne[c];
if (t[q].l == t[p].l + 1)
t[np].f = q;
else {
int nq = ++tot;
t[nq] = _(t[p].l + 1, t[q].f);
std::copy(t[q].ne, t[q].ne + 26, t[nq].ne);
while (p && t[p].ne[c] == q)
t[p].ne[c] = nq, p = t[p].f;
t[q].f = nq;
t[np].f = nq;
}
}
return;
}
int now = 0;
void ins(int &p, int l, int r, int v) {
if (!p)
p = ++now;
++t1[p].u;
if (l == r)
return;
int mid = (l + r) >> 1;
if (v <= mid)
ins(t1[p].l, l, mid, v);
else
ins(t1[p].r, mid + 1, r, v);
return;
}
int ask(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr)
return t1[p].u;
int mid = (l + r) >> 1, res = 0;
if (ql <= mid)
res = ask(t1[p].l, l, mid, ql, qr);
if (qr > mid)
res += ask(t1[p].r, mid + 1, r, ql, qr);
return res;
}
int merge(int p, int q, int l, int r) {
if (!p || !q)
return p + q;
int np = ++now, mid = (l + r) >> 1;
t1[np].u = t1[p].u + t1[q].u;
if (l == r) return np;
t1[np].l = merge(t1[p].l, t1[q].l, l, mid);
t1[np].r = merge(t1[p].r, t1[q].r, mid + 1, r);
return np;
}
int pos[maxn], rt[maxn << 1];
bool check(int p, int ch, int l, int r) {
return ask(rt[t[p].ne[ch]], 0, n - 1, l, r) > 0;
}
bool fun(std::string &res, std::string now, std::string &t, int x, int p, int l, int r) {
// std::cout << "x = " << x << ", now = \"" << now << "\";\n";
if (x != (int)t.length() && check(p, t[x] - 'a', l + x, r) && fun(res, now + t[x], t, x + 1, ::t[p].ne[t[x] - 'a'], l, r))
return 1;
for (int i = (x == (int)t.length()) ? 0 : t[x] - 'a' + 1; i < 26; ++i) {
if (check(p, i, l + x, r)) {
now += i + 'a';
res = now;
return 1;
}
}
return 0;
}
std::string solve(std::string &t, int l, int r) {
std::string res;
return fun(res, "", t, 0, 1, l, r) ? res : "-1";
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#endif
int q;
std::string s;
std::cin >> s >> q;
n = (int)s.length();
Init();
for (int i = 0; i < n; ++i) {
ext(s[i] - 'a');
pos[i] = la;
ins(rt[la], 0, n - 1, i);
}
siz = log(tot) / log(2.0);
for (int i = 1; i <= tot; ++i)
++cnt[t[i].l];
std::partial_sum(cnt + 1, cnt + tot + 1, cnt + 1);
for (int i = 1; i <= tot; ++i)
tab[cnt[t[i].l]--] = i;
for (int i = 1; i <= tot; ++i) {
int u = tab[i];
fa[u][0] = t[u].f;
for (int j = 1; j <= siz; ++j)
fa[u][j] = fa[fa[u][j - 1]][j - 1];
}
for (int i = tot; i; --i) {
int u = tab[i];
if (t[u].f)
rt[t[u].f] = merge(rt[t[u].f], rt[u], 0, n - 1);
}
while (q--) {
int l, r;
std::string t;
std::cin >> l >> r >> t;
std::cout << solve(t, l - 1, r - 1) << '\n';
}
return 0;
}A. 六出祁山
https://www.becoder.com.cn/contest/5170/problem/1
是能用贪心拿 60pts 的 DP 题 /tuu
需要先把暴力的式子写出来。设 \(f_{i, j}\) 为将 \(i\) 山修改高度为 \(j\) 的代价，则：
\[ f_{i, j} = \min\limits_{k\in [j-d, j+d]}\left\{f_{i-1, k}\right\} + |h_i - j| \]
注意到可以单调队列优化。但是这样做复杂度还是 \(\mathcal O(nV)\) 的，根本原因在于第二维这个 \(V\) 的状态数太多了。
根据直觉，最后 \(j\) 的值应为 \(k+d\) 或 \(k-d\) 或 \(a_i\)。也就是说，我们可以认为，合法的状态数为所有的 \(a_i+x\times d, x\in[-n, n]\)。
正确性证明……
考虑全部更改完后的结束状态，即最后的最优状态。
考虑所有山中最矮的山 \(i\)，此山的高度要么为 \(h_i\)，要么为前一座山的高度 \(-d\)，要么为后一座山的高度 \(-d\)。
考虑第二矮的山，以此类推即可。
将第二维的状态集大小减少为 \(\mathcal O(n^2)\)，总时间复杂度为 \(\mathcal O(n^3)\)。
需注意到因为 \(a_i+x\times d\) 中的 \(x\) 范围为 \([-n, n]\) 共 \(2\times n\)，所以 DP 数组第二维大小一定要开 \(2\times n^2\) 呀！！！
#include <bits/stdc++.h>
using ll = long long;
const int maxn = 305;
const int maxm = 18e4 + 5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll d;
int n;
ll h[maxn];
ll f[maxn][maxm];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
memset(f, 0x3f, sizeof (f));
std::cin >> n >> d;
std::vector<ll> st;
for (int i = 1; i <= n; ++i) {
std::cin >> h[i];
for (ll j = -n; j <= n; ++j)
st.push_back(h[i] + j * d);
}
std::sort(st.begin(), st.end());
st.erase(std::unique(st.begin(), st.end()), st.end());
auto abs = [&](ll x) -> ll { return x >= 0 ? x : -x; };
f[1][lower_bound(st.begin(), st.end(), h[1]) - st.begin()] = 0;
for (int i = 2; i <= n; ++i) {
int h(1), t(0), p(-1);
static int q[maxm];
for (int j = 0; j < (int)st.size(); ++j) {
while (p < (int)st.size() && st[p + 1] <= st[j] + d) {
++p;
while (h <= t && f[i - 1][p] <= f[i - 1][q[t]])
--t;
q[++t] = p;
}
while (h <= t && st[q[h]] < st[j] - d)
++h;
if (h <= t)
f[i][j] = std::min(inf, f[i - 1][q[h]] + abs(st[j] - ::h[i]));
}
}
ll res = f[n][std::lower_bound(st.begin(), st.end(), h[n]) - st.begin()];
std::cout << (res == inf ? -1 : res) << '\n';
return 0;
}B. 水淹七军
https://www.becoder.com.cn/contest/5170/problem/2
容易发现最后连出来一定是没有环的。所以一定是一个 DAG。
我们知道状态压缩是会遍历到每一种情况的，所以我们可以假设当前的 DAG 就是该状态下的最优。
至于这个「最优」如何定义就要交给我们了。我们不妨强制认为这个 DAG 是按层序遍历得到的，也就是说连续遍历到的点属于同一层（这里的层是指某点到任意源点的最长路长度）。
显然只有一组相互之间没有任何连边的点才能组成同一层。不妨枚举点集然后暴力转移，转移时记录路径即可。
注意到在写这玩意儿的时候我还不会 状压枚举子集，所以枚举子集的部分可能打得比较抽象。
#include <bits/stdc++.h>
const int maxn = 25;
const int inf = 0x3f3f3f3f;
const int maxm = (1 << 16) + 5;
int n, res;
int tag[maxn][maxn];
int f[maxn], g[maxn];
int solve(std::vector<int>& a) {
static int g[maxn];
static int f[maxm], p[maxm];
int n(a.size()), siz(1 << n);
std::fill(g, g + n, 0);
std::fill(p, p + siz + 1, 0);
std::fill(f, f + siz + 1, inf);
std::vector<int> st;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (::g[a[i]] & (1 << a[j]))
g[i] |= 1 << j;
}
}
for (int i = 1; i < siz; ++i) {
int now = 0;
for (int j = 0; j < n; ++j) {
if (i & (1 << j))
now |= g[j];
}
if (!(now & i))
st.push_back(i), f[i] = 0, p[i] = i;
for (auto j : st) {
if (!(i & j)) {
if (f[i | j] > f[i] + 1)
f[i | j] = f[i] + 1, p[i | j] = j;
}
}
}
int now = siz - 1;
while (now) {
int fa = now ^ p[now];
for (int i = 0; i < n; ++i)
if (p[now] & (1 << i))
for (int j = 0; j < n; ++j)
if ((fa & (1 << j)) && tag[a[j]][a[i]] == 2)
tag[a[j]][a[i]] = 1, tag[a[i]][a[j]] = -1;
now = fa;
}
return f[siz - 1];
}
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int m;
std::cin >> n >> m;
std::vector<std::pair<int, int> > edge;
for (int i = 0; i < n; ++i)
f[i] = i;
while (m--) {
int x, y;
std::cin >> x >> y;
edge.emplace_back(--x, --y);
f[find(x)] = find(y);
g[x] |= 1 << y;
g[y] |= 1 << x;
tag[x][y] = tag[y][x] = 2;
}
std::vector<int> ver[maxn];
for (int i = 0; i < n; ++i) {
ver[find(i)].push_back(i);
}
for (int i = 0; i < n; ++i) {
if (f[i] == i)
res = std::max(res, solve(ver[i]));
}
std::cout << res << '\n';
for (auto i : edge) {
if (tag[i.first][i.second] == 1)
std::cout << i.first + 1 << ' ' << i.second + 1 << '\n';
else std::cout << i.second + 1 << ' ' << i.first + 1 << '\n';
}
return 0;
}C. 煮酒论英雄
https://www.becoder.com.cn/contest/5170/problem/3
注意到如果存在串被其他串包含那么直接将其毙掉就可以了。
对于相互不完全包含的串，我们令 \(mx_{i, j, 0/1, 0/1}\) 表示将正序 / 逆序的 \(i\) 串拼到正序 / 逆序的 \(j\) 串之前，两者共用相接公共部分的串长。这个可以用字符串哈希暴力求。
用状压枚举拼接顺序，求得最小总串长即可。
注意如果去掉被包含串后 \(n=1\) 时需直接输出串的 border；以及答案需和 \(2\) 取 \(\max\)。
实现起来又臭又长，但实际上思路确实非常简单。
#include <bits/stdc++.h>
using ll = long long;
const int p = 131;
const int maxn = 25;
const int lim = 2e4;
const int maxl = 2e4 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
const int maxm = (1 << 16) + 5;
int n;
std::vector<std::string> s;
std::vector<std::vector<ll> > h[2];
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#endif
std::cin >> n;
s.resize(n);
h[0].resize(n);
h[1].resize(n);
static ll base[maxl];
static bool del[maxn];
base[0] = 1;
for (int i = 1; i <= lim; ++i)
base[i] = base[i - 1] * p % mod;
for (int i = 0; i < n; ++i) {
std::cin >> s[i];
h[0][i].resize((int)s[i].length());
h[1][i].resize((int)s[i].length());
ll x = 0;
for (int j = 0; j < (int)s[i].length(); ++j, (x *= p) %= mod)
h[0][i][j] = ((x += s[i][j]) %= mod);
std::reverse(s[i].begin(), s[i].end());
x = 0;
for (int j = 0; j < (int)s[i].length(); ++j, (x *= p) %= mod)
h[1][i][j] = ((x += s[i][j]) %= mod);
std::reverse(s[i].begin(), s[i].end());
}
std::vector<int> tab;
auto gethash = [&](int i, int l, int r, bool t) -> ll {
if (l > r) return 0;
ll res = (h[t][i][r] - (l ? h[t][i][l - 1] : 0) * base[r - l + 1] % mod);
return (res % mod + mod) % mod;
};
// ll now = 0;
// for (int i = 0; i <= 4; ++i)
// now = (now * p + s[1][i]) % mod;
// printf("now = %lld\n", now);
// now = 0;
// for (int i = 3; i <= 7; ++i)
// now = (now * p + s[0][i]) % mod;
// printf("now = %lld\n", now);
// printf("# %lld\n", h[0][0].back());
for (int i = 0; i < n; ++i) {
tab.push_back(i);
for (int j = 0; j < n; ++j)
if (!del[j] && i != j)
for (int k = 0; k <= ((int)s[j].length()) - ((int)s[i].length()); ++k) {
// printf("i = %d, j = %d, k = %d, %lld / %lld\n", i, j, k,
// gethash(i, 0, ((int)s[i].length()) - 1, 0), gethash(j, k, k + ((int)s[i].length()) - 1, 0));
if (h[0][i].back() == gethash(j, k, k + ((int)s[i].length()) - 1, 0)) {
tab.pop_back();
del[i] = 1;
goto outo;
}
}
outo: ;
}
n = (int)tab.size();
if (n == 1) {
int border;
for (border = ((int)s[tab[0]].length()) - 1; ~border; --border) {
if (gethash(tab[0], 0, border - 1, 0) == gethash(tab[0], ((int)s[tab[0]].length()) - border, ((int)s[tab[0]].length()) - 1, 0))
break;
}
std::cout << std::max(2, ((int)s[tab[0]].length()) - border) << '\n';
}
else {
static int mx[maxn][maxn][2][2];
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
for (int a = 0; a < 2; ++a)
for (int b = 0; b < 2; ++b)
for (int k = std::min((int)s[tab[i]].length(), (int)s[tab[j]].length()); ~k; --k) {
if (gethash(tab[i], ((int)s[tab[i]].length()) - k, ((int)s[tab[i]].length()) - 1, a) ==
gethash(tab[j], 0, k - 1, b)) {
mx[i][j][a][b] = (int)s[tab[j]].length() - k;
// printf("%d(%d) + %d(%d) = %d, k = %d\n", i, a, j, b, mx[i][j][a][b], k);
break;
}
}
static int f[maxm][maxn][2];
memset(f, 0x3f, sizeof (f));
int siz = 1 << n, res = inf;
f[1][0][0] = (int)s[tab[0]].length();
for (int i = 1; i < siz; ++i)
for (int j = 0; j < n; ++j)
if (i & (1 << j))
for (int a = 0; a < 2; ++a) {
// printf("f[%d][%d][%d] = %d\n", i, j, a, f[i][j][a]);
for (int k = 0; k < n; ++k)
if (!(i & (1 << k)))
for (int b = 0; b < 2; ++b)
f[i | (1 << k)][k][b] = std::min(f[i | (1 << k)][k][b], f[i][j][a] + mx[j][k][a][b]);
if (i == siz - 1)
res = std::min(res, f[i][j][a] - (int)s[tab[0]].length() + mx[j][0][a][0]);
}
std::cout << std::max(2, res) << '\n';
}
return 0;
}A. 捏斑马
https://www.becoder.com.cn/contest/5175/problem/1
王博王博博.jpg
我甚至不会（）甚至贺了一下王博儿的代码，发现我是 SB（）
翻转 + 拼接本质上就是首尾相接。我们把字符串整个拼到自己后边儿，然后任取一段长度为 \(n\) 的串就可以得到一个倒过来的操作后的字符串。
注意到可以操作很多次。但是既然我们操作后的串也可以在这个拼接后的串中找到了，那么其实多次操作后的也行。
所以呢我们在拼接后的串种枚举每一个长度为 \(n\) 的串计算答案即可。
具体怎么算呢？注意到只看开头，也就是在新串中只看离我们当前枚举的右端点最近的那一段，所以我们打一个双指针，看这一段是否在右移后仍然合法，如果非法就把答案区间左端点更新为右端点自己。以及注意到左右端点的距离不能超过 \(n\)。
#include <bits/stdc++.h>
int res;
std::string s;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#endif
std::cin >> s;
int l = 0, r = -1, n = (int)s.length();
char la = 0;
s += s;
while (++r < (int)s.length()) {
if (s[r] == la)
l = r;
while (r - l + 1 > n) ++l;
la = s[r];
res = std::max(res, r - l + 1);
}
std::cout << res << '\n';
return 0;
}D. 链状闪电
https://www.becoder.com.cn/contest/5175/problem/4
莫名其妙且又臭又长的根号做法。
容易发现一个怪被杀掉了序列就会裂开成两段连续子序列，以及最先被杀掉的怪物一定血量最少。在裂开来的两段连续子序列中也满足此规律，以此类推。
考虑对序列建立笛卡尔树。令树根为 \(rt\)，当前攻击力为 \(k\)，记 \(t_{x, k}=\left\lceil \dfrac {h_x}k \right\rceil\)，即不考虑其他条件时击倒 \(x\) 所需次数。
那么对于 \(rt\) 的左、右儿子 \(l,r\)，单考虑这三个怪物所需的总击倒次数，容易发现为 \(t_{rt,k}+(t_{l,k}-t_{rt,k})+(t_{r,k}-t_{rt,k})\)。
对于 \(l\) 引导的子树，此时的实际已攻击次数为 \(t_{l,k}\)；所以对于 \(l\) 的左右儿子 \(l',r'\)，击倒这两个怪物的所需次数为 \((t_{l',k} - t_{l,k})+(t_{r',k}-t_{l,k})\)。\(r\) 引导的子树同理。
所以我们就可以知道，如果存在树边 \(u\to v\)，那么击倒 \(v\) 的所需次数为 \(t_{v,k}-t_{u,k}\)；特别地，击倒 \(rt\) 的所需次数为 \(t_{rt,k}\)。
那么我们就可以通过一次 \(\mathcal O(n)\) 的树上 DFS 对于一个 \(k\) 找到答案了。
那么对于 \(2\times 10^4\) 范围内的所有 \(k\)，应该怎么办呢？这个时候就要利用 \(t\) 的性质进行根号分治了。
对于 \(k\le \sqrt {2\times 10^4}\)，我们大可以直接做这么多次 DFS 得到答案；
对于 \(k>\sqrt {2\times 10^4}\)：
我们容易发现最终的结果是若干个 \(t\) 的值相加减得到的，而每个 \(t\) 的权值 \(cnt\) 取决于其在笛卡尔树上的儿子个数，有多少就在 \(1\) 的基础上减去多少。
由于 \(t\) 实在过于特殊，考虑整除分块 / 数论分块。对于每个 \(x\)，对于任意 \(k'\in (\sqrt {2\times 10^4}, 2\times 10^4]\)，可能的 \(t\) 值只有 \(\sqrt {2\times 10^4 }\) 种。计算出对于每个 \(t'\)，满足 \(\left\lceil \dfrac {h_x}{k'} \right\rceil=t'\) 的 \(k'\) 范围，对该范围 \(k'\) 的答案区间加上 \(t'\times cnt\) 即可，可以使用差分。
至此，就可以在一次 DFS 内解决这种情况下的问题。
总时间复杂度为 \(\mathcal O(n\sqrt {2\times 10^4})\)。
值得注意的是，我在做这道题的时候并没有意识到自己用到了笛卡尔树，
所以代码中笛卡尔树的建树部分可能长得特别抽象（
这里是使用了下标上的 ST 表带 log 地求解了左右儿子。
#include <bits/stdc++.h>
const int maxm = 35;
const int maxn = 1e5 + 5;
using ll = long long;
ll res;
int n, k, l;
int g[maxn][2];
int f[maxn][maxm];
int a[maxn], t[maxn];
ll dif[maxn], cnt[maxn];
int ask(int l, int r) {
if (l > r) return 0;
int k = log(r - l + 1) / log(2.0);
return (a[f[l][k]] < a[f[r - (1 << k) + 1][k]]) ? f[l][k] : f[r - (1 << k) + 1][k];
}
void bld(int rt, int l, int r) {
if (rt != l) {
g[rt][0] = ask(l, rt - 1);
bld(g[rt][0], l, rt - 1);
}
if (rt != r) {
g[rt][1] = ask(rt + 1, r);
bld(g[rt][1], rt + 1, r);
}
return;
}
// k <= sqrt(lim)
void DFS(int x, int k, int fa) {
t[x] = (a[x] + k - 1) / k;
res += t[x] - t[fa];
for (int i = 0; i < 2; ++i) {
if (g[x][i])
DFS(g[x][i], k, x);
}
return;
}
// k > sqrt(lim)
void DFS(int x, int fa) {
++cnt[x];
--cnt[fa];
for (int i = 0; i < 2; ++i) {
if (g[x][i])
DFS(g[x][i], x);
}
int l = k + 1, r;
// 注意这里 i 的范围判定，如果直接写成 i * i <= k 会少计算一些情况
for (int i = 1; (i - 1) * (i - 1) < k; ++i) {
r = l - 1;
l = (a[x] + i - 1) / i;
// fprintf(stderr, "%d: [%d, %d] += %d * %d\n", a[x], l, r, cnt[x], i);
dif[l] += i * cnt[x], dif[r + 1] -= i * cnt[x];
}
return;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#endif
std::cin >> n;
for (int i = 1; i <= n; ++i) {
std::cin >> a[i];
f[i][0] = i;
k = std::max(k, a[i]);
}
for (int j = 1; (1 << j) <= n; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
f[i][j] = (a[f[i][j - 1]] < a[f[i + (1 << (j - 1))][j - 1]]) ? f[i][j - 1] : f[i + (1 << (j - 1))][j - 1];
int rt = ask(1, n);
bld(rt, 1, n);
for (int i = 1; i * i <= k; ++i) {
res = 0;
DFS(rt, i, 0);
std::cout << res << ' ';
l = i + 1;
}
// fputs("\n", stderr);
DFS(rt, 0);
std::partial_sum(dif + 1, dif + k + 1, dif + 1);
for (int i = l; i <= k; ++i)
std::cout << dif[i] << ' ';
std::cout << '\n';
return 0;
}F. 弹飞绵羊
https://www.becoder.com.cn/contest/5175/problem/6
很棒可持久化分块，使我 lxl 旋转。
笑话：赛后 5s 才交上去。然后 A 了。
我们猜大家都会普通的弹飞绵羊这道题。就是块间暴力跳嘛。
这里给一个我自己整的简单实现方法。
我们把分出来的块视作若干个无关联的散块并纳入块集合；对于每一个版本，用一个大小为 \(\sqrt n\) 的 \(id\) 数组记录每一位置的块在块集合中对应的位置。
然后该怎么搞怎么搞即可。
P.S. 有的死脑袋 zwb 坚定不移地信仰 lxl 神教于是决定用可持久化平衡树实现可持久化分块，结果当然是因为多了个 \(\log\) 被卡飞了，最后气急败坏慌不择路恼羞成怒抄起了我们的代码。
#include <bits/stdc++.h>
const int maxk = 320;
const int maxn = 2e5 + 5;
class devicer {
public:
int l, r;
std::vector<int> ne, u, a;
int &nex(int x);
int &val(int x);
};
int id[maxn][maxk];
std::vector<devicer> b;
int n, q, ty, siz, k, la;
int a[maxn], tab[maxn], blk[maxn];
void upd(int x, int a, devicer &p) {
if (x + a > n)
p.nex(x) = -1, p.val(x) = 1;
else if (x + a > p.r)
p.nex(x) = x + a, p.val(x) = 1;
else
p.nex(x) = p.nex(x + a), p.val(x) = p.val(x + a) + 1;
// printf("x = %d, a = %d, r = %d, upd ne[%d] to %d\n", x, a, p.r, x, p.nex(x));
return;
}
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
#endif
std::cin >> n >> q >> ty;
siz = sqrt(n);
k = (n + siz - 1) / siz;
b.resize(k);
int la = 0, now = k - 1;
for (auto &i : b)
i.l = la + 1, la = i.r = i.l + siz - 1;
b.back().r = n;
for (int i = 0; i < k; ++i) {
id[0][i] = i;
b[i].a.resize(b[i].r - b[i].l + 1);
b[i].u.resize(b[i].r - b[i].l + 1);
b[i].ne.resize(b[i].r - b[i].l + 1);
for (int j = b[i].l; j <= b[i].r; ++j)
tab[j] = j - b[i].l, blk[j] = i;
}
for (int i = 1; i <= n; ++i)
std::cin >> b[blk[i]].a[tab[i]];
for (int i = n; i; --i)
upd(i, b[blk[i]].a[tab[i]], b[blk[i]]);
int ver = 0;
while (q--) {
int op, pr, x;
static int res = 0;
std::cin >> op >> pr >> x;
if (!ty)
res = 0;
x ^= res;
if (op == 1) {
std::copy(id[pr], id[pr] + k, id[++ver]);
b.push_back(b[id[ver][blk[x]]]);
id[ver][blk[x]] = ++now;
std::cin >> b.back().a[tab[x]];
b.back().a[tab[x]] ^= res;
for (int i = x; i >= b.back().l; --i)
upd(i, b.back().a[tab[i]], b.back());
}
else {
int p = x;
res = 0;
while (~p) {
// printf("p = %d\n", p);
res += b[id[pr][blk[p]]].u[tab[p]];
p = b[id[pr][blk[p]]].ne[tab[p]];
}
std::cout << res << '\n';
}
}
return 0;
}
int& devicer::nex(int x) {
return ne[tab[x]];
}
int& devicer::val(int x) {
return u[tab[x]];
}