「做题记录」分治选做
stripe_python · · 算法·理论
先写一些分治,然后做题。
二区间合并
考虑如下问题:
给你一个长为
n 的静态序列a_1,a_2,\cdots,a_n 。q 次询问给出[l,r] ,查询a_l \otimes a_{l+1} \cdots \otimes a_{r} 其中
\otimes 是具有结合律的运算,计算x \otimes y 的代价为O(k) 。
我们知道线段树可以在
二区间合并(也称为猫树分治)则可以在
猫树本身是一种对线段树结构进行魔改的数据结构。它的核心思想是:
- 对于每一个线段树上的节点,设其表示区间
[l,r] 。 - 计算出区间中点
m 后,预处理p_i 表示区间[i,m] 的答案,s_i 表示区间(m,i] 的答案。 - 查询时找到一组合适的
i,j 并计算p_i \otimes s_j 。
二区间合并 / 猫树分治使用了类似的思想。算法流程如下:
- 对于当前处理的区间
[l,r] ,计算中点m ,并预处理从m 向两侧扩展的答案。 - 对于跨过中线的询问,取当前左右两侧答案合并进行更新。
- 对于在
m 同侧的询问,下放到[l,m], (m,r] 再处理。
一张原理图:
下面分析处理长为
得
最值分治
最值分治是一种特殊的二区间合并。其处理的问题常常与最值结构相关,因此我们将二区间合并中的
笛卡尔树是一种典型的最值分治结构。它是一棵二叉树,每个节点有权值二元组
笛卡尔树可在
int n, a[N], l[N], r[N];
void build() {
stack<int> st;
for (int i = 1; i <= n; i++) {
while (!st.empty() && a[st.top()] > a[i]) l[i] = st.top(), st.pop();
if (!st.empty()) r[st.top()] = i;
st.emplace(i);
}
}
笛卡尔树可视为一种分治结构:找到当前区间最值,然后从最值两段劈开继续递归。因此最值分治也可以视作笛卡尔树上 DP。
网格图分治
网格图分治是在平面上的分治。网格图分治也可以叫做“二平面合并”,或者二维猫树分治。
P3350 [ZJOI2016] 旅行者:
给出一个
n \times m 的无向带权网格图。q 次询问从(x_1,y_1) 到(x_2,y_2) 的最短路。
类似于二区间合并,将所有询问离线后进行分治处理。对于当前考虑的子网格:
- 沿着较长的边分裂子网格,形成一条中线。
- 枚举中线上的每一个点,分别作为源点跑一次最短路。
- 用这些最短路结果,更新所有跨越中线的询问。
原理图:
这样一来:
- 所有跨过中线的询问,已经在当前层被正确更新。
- 对于完全位于中线同一侧的询问,递归进入对应的子网格继续处理。
下面简要分析网格图分治的复杂度。
根据均值不等式,上述算法的最劣时间复杂度在网格的长和宽同阶时取得。因此不妨将网格视为边长为
由主定理得
更一般地,设网格图的面积为
:::::info[P3350 代码]
const int N = 1e5 + 5, inf = 1e9;
int n, m, q, ans[N];
using query = tuple<int, int, int, int, int>; // {x1, y1, x2, y2, id}
vector<query> qry;
// L, R, U, D
const int dirx[] = {0, 0, 0, -1, 1};
const int diry[] = {0, -1, 1, 0, 0};
vector<vector<int>> dis, e[5];
struct node {
int x, y, d;
node(int a = 0, int b = 0, int c = 0) : x(a), y(b), d(c) {}
bool operator< (const node& a) const {return d > a.d;}
};
void dijkstra(int lx, int rx, int ly, int ry, int sx, int sy, const vector<query>& q) {
if (dis.empty()) dis.resize(n + 5, vector<int>(m + 5, 0));
for (int x = lx; x <= rx; x++) {
for (int y = ly; y <= ry; y++) dis[x][y] = inf;
}
priority_queue<node> h;
dis[sx][sy] = 0, h.emplace(sx, sy, 0);
while (!h.empty()) {
auto [x, y, dl] = h.top(); h.pop();
if (dl != dis[x][y]) continue;
for (int d = 1; d <= 4; d++) {
int nx = x + dirx[d], ny = y + diry[d];
if (nx < lx || nx > rx || ny < ly || ny > ry) continue;
if (dis[nx][ny] > dis[x][y] + e[d][x][y]) dis[nx][ny] = dis[x][y] + e[d][x][y], h.emplace(nx, ny, dis[nx][ny]);
}
}
for (const auto& [x1, y1, x2, y2, id] : q) ans[id] = min(ans[id], dis[x1][y1] + dis[x2][y2]);
}
void solve(int lx, int rx, int ly, int ry, vector<query> q) {
if (lx > rx || ly > ry || q.empty()) return;
if (rx - lx > ry - ly) {
int mid = (lx + rx) >> 1;
for (int y = ly; y <= ry; y++) dijkstra(lx, rx, ly, ry, mid, y, q);
vector<query> ql, qr;
for (const auto& [x1, y1, x2, y2, id] : q) {
if (x1 < mid && x2 < mid) ql.emplace_back(x1, y1, x2, y2, id);
if (mid < x1 && mid < x2) qr.emplace_back(x1, y1, x2, y2, id);
}
solve(lx, mid - 1, ly, ry, ql), solve(mid + 1, rx, ly, ry, qr);
} else {
int mid = (ly + ry) >> 1;
for (int x = lx; x <= rx; x++) dijkstra(lx, rx, ly, ry, x, mid, q);
vector<query> ql, qr;
for (const auto& [x1, y1, x2, y2, id] : q) {
if (y1 < mid && y2 < mid) ql.emplace_back(x1, y1, x2, y2, id);
if (mid < y1 && mid < y2) qr.emplace_back(x1, y1, x2, y2, id);
}
solve(lx, rx, ly, mid - 1, ql), solve(lx, rx, mid + 1, ry, qr);
}
}
void _main() {
cin >> n >> m;
for (int d = 1; d <= 4; d++) e[d].resize(n + 5, vector<int>(m + 5, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j < m; j++) cin >> e[2][i][j], e[1][i][j + 1] = e[2][i][j];
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= m; j++) cin >> e[4][i][j], e[3][i + 1][j] = e[4][i][j];
}
cin >> q;
for (int i = 1, x1, y1, x2, y2; i <= q; i++) cin >> x1 >> y1 >> x2 >> y2, qry.emplace_back(x1, y1, x2, y2, i);
fill(ans + 1, ans + q + 1, inf);
solve(1, n, 1, m, qry);
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
:::::
点分治
点分治是一种树上的分治,常用于对某些限定条件的路径进行静态统计。可以认为二区间合并是点分治在链上的特殊情况。
P3806 【模板】点分治:
给定一棵有
n 个点的树,q 次询问树上距离为k 的点对是否存在。
本题给出的树是一棵无根树。不妨任选一个点
- 经过根节点
p 。 - 位于根节点
p 的某棵子树中。
对于第二种情形,我们已经看到了子问题的结构,递归分治即可。下面主要处理经过
从
不过我们发现一个问题:
- 分别统计:逐个子树处理,处理当前子树时,先做完成所有插入再插入所有操作。
- 容斥原理:正常统计完成后,再做一个容斥减去不合法方案。
对于本题,可行性不具有可减性,我们选择第一种方法。
注意到如果随意选择
对于本题,我们还要做
:::::info[P3806 代码]
const int N = 1e4 + 5, K = 1e7 + 5;
int n, q, cur, ctr, k[N], sz[N], vis[N], ans[N];
vector<pair<int, int>> e[N];
void dfs1(int u, int fa) { // 找重心
sz[u] = 1;
for (auto [v, w] : e[u]) {
if (v == fa || vis[v]) continue;
dfs1(v, u), sz[u] += sz[v];
}
if (!ctr && 2 * sz[u] >= cur) ctr = u;
}
void dfs2(int u, int fa) { // 统计子树大小
cur++;
for (auto [v, w] : e[u]) if (!vis[v] && v != fa) dfs2(v, u);
}
void dfs3(int u, int fa, int dep, vector<int>& vec) { // 统计距离
if (dep >= K) return;
vec.emplace_back(dep);
for (auto [v, w] : e[u]) {
if (v == fa || vis[v]) continue;
dfs3(v, u, dep + w, vec);
}
}
bitset<K> has;
void update(int u) {
vector<int> vec = {0};
has[0] = 1;
for (auto [v, w] : e[u]) {
if (vis[v]) continue;
vector<int> cur; dfs3(v, u, w, cur);
for (int d : cur) for (int i = 1; i <= q; i++) {
if (k[i] >= d && has[k[i] - d]) ans[i] = true;
}
for (int d : cur) has[d] = 1, vec.emplace_back(d);
}
for (int d : vec) has[d] = 0;
}
void solve(int u) {
vis[u] = true, update(u);
for (auto [v, w] : e[u]) {
if (vis[v]) continue;
cur = ctr = 0, dfs2(v, u), dfs1(v, u), solve(ctr);
}
}
void _main() {
cin >> n >> q;
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e[u].emplace_back(v, w), e[v].emplace_back(u, w);
}
for (int i = 1; i <= q; i++) cin >> k[i];
cur = n, dfs1(1, -1), solve(ctr);
for (int i = 1; i <= q; i++) cout << (ans[i] ? "AYE\n" : "NAY\n");
}
:::::
边分治
边分治和点分治非常相似,都是用来处理树上信息统计的分治。区别在于,点分治的分治中心是点,而边分治的分治中心则是一条边。
记
然而朴素边分治的复杂度是假的。因此,我们需要将树进行三度化,即通过建虚点的方法,将多叉树转成二叉树再做边分治。
需要说明的是,三度化的技巧不局限于边分治。如果点分治难以合并多个信息,我们也可以三度化后点分治。
线段树分治
线段树分治是利用线段树结构对时间轴分治的一种技巧。一般来说,这类问题的形式如下:维护一些信息,这些信息在一个时间段内出现,离线回答某个时刻的信息并。
如果直接对时间轴扫描线,用数据结构维护某种信息,则需要信息具有可减性。比如并查集连边就是无法做到快速删除的。而线段树分治只要求操作可撤销,比如并查集是可以快速撤销的。
下面以模板题 P5787 【模板】线段树分治 / 二分图为例:
维护一个
n 个点,m 条边的无向图,有k 个时刻,第i 条边(u_i,v_i) 出现的时间段为[l_i,r_i) 。判断每个时刻图是否为二分图。
先考虑如何判断二分图:使用扩展域并查集,将点
注意到连边不具有可减性,但并查集可撤销。
具体地,使用并查集维护父亲的所属关系,并将每次操作入栈。撤销时,我们不断出栈,并做原操作的逆操作。可以发现这里不能路径压缩,可以用启发式合并做到
下面正式叙述线段树分治的流程。
对时间轴建立线段树,每个节点代表了一个时间段。在节点上挂 vector 来表示这个节点的操作。可以在
插入完成后,从根节点自顶向下扫描线段树,维护当前的连边状态,每到一个节点就进行操作,退出节点就撤销操作。
可以发现上述算法的时间复杂度为
:::::info[P5787 代码]
const int N = 1e5 + 5;
int n, m, k;
struct dsu {
int fa[N << 1], sz[N << 1];
stack<int, vector<int>> st;
void init() {iota(fa, fa + (N << 1), 0), fill(sz, sz + (N << 1), 1);}
int find(int x) {return x == fa[x] ? x : find(fa[x]);}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
fa[x] = y, sz[y] += sz[x], st.emplace(x);
}
void undo(int x) {
while ((int) st.size() > x) {
int u = st.top(); st.pop();
if (u != fa[u]) sz[fa[u]] -= sz[u], fa[u] = u;
}
}
} uf;
vector<pair<int, int>> val[N << 2];
#define ls (rt << 1)
#define rs (rt << 1 | 1)
void change(int tl, int tr, const pair<int, int>& c, int l = 1, int r = k, int rt = 1) {
if (tl <= l && r <= tr) return val[rt].emplace_back(c), void();
int mid = (l + r) >> 1;
if (tl <= mid) change(tl, tr, c, l, mid, ls);
if (tr > mid) change(tl, tr, c, mid + 1, r, rs);
}
bool ans[N];
void solve(int l = 1, int r = k, int rt = 1) {
int mid = (l + r) >> 1, keep = 1, step = uf.st.size();
for (const auto &i : val[rt]) {
int u = i.first, v = i.second;
if (uf.find(u) == uf.find(v)) {
fill(ans + l, ans + r + 1, 0), keep = 0;
break;
}
uf.unite(u, v + n), uf.unite(u + n, v);
}
if (!keep) return uf.undo(step), void();
if (l == r) ans[l] = 1;
else solve(l, mid, ls), solve(mid + 1, r, rs);
uf.undo(step);
}
void _main() {
cin >> n >> m >> k;
uf.init();
for (int i = 1, u, v, l, r; i <= m; i++) {
cin >> u >> v >> l >> r;
change(l + 1, r, {u, v});
}
solve();
for (int i = 1; i <= k; i++) cout << (ans[i] ? "Yes" : "No") << '\n';
}
:::::
CDQ 分治
本来这里有一堆东西,但是我发现 https://www.luogu.com.cn/article/hsdkbux2 写的远好于我,所以就删掉了。读者可以阅读这篇专栏来学习。
下面补一个参考资料中没有提到的用途:CDQ 分治的结构还可以用来优化建图。
先回顾一下前后缀优化建图,它主要适用于将一个点向一段连续的前缀或后缀区间连边的场景。
我们利用前后缀和的结构,建一排前缀虚点链
考虑一种按偏序关系建图的问题,下面举一个例子:
给定一个
n 个点的有向图,每个点有点权a_i 。若u<v \land a_u>a_v 则连边u \to v 。
直接做显然是
对值域分治,设当前分治区间
排序后,对于
对于本题,使用归并排序则连边的复杂度为
CDQ 优化建图的本质是使用 CDQ 分治套数据结构优化建图,来解决一些直接使用数据结构难以维护的连边关系。上一题中,我们使用的是 CDQ 分治套前后缀优化建图。
缺一分治
见「做题记录」背包 DP 选做。
练习
P6240 好吃的题目
给出
n 个物品,体积为v_i ,价值为w_i 。q 次询问,给出l,r,V ,求区间[l,r] 上容量为V 的 01 背包。
:::::success[题解]
01 背包的转移式为
单次合并是
直接使用线段树无法通过本题。采用二区间合并,从每个区间中点向两侧预处理背包数组即可。总时间复杂度为
:::::
:::::info[代码]
const int N = 4e4 + 5, M = 205, Q = 2e5 + 5;
using node = tuple<int, int, int, int>; // {l, r, V, id}
int n, q, v[N], w[N], ans[Q];
void solve(int l, int r, vector<node> qry) {
if (qry.empty()) return;
if (l == r) { // 边界情况特判
for (auto& [ql, qr, V, id] : qry) ans[id] = V >= v[l] ? w[l] : 0;
return;
}
int mid = (l + r) >> 1;
vector<vector<int>> f(mid - l + 5, vector<int>(M + 5, 0)); // 左侧
vector<vector<int>> g(r - mid + 5, vector<int>(M + 5, 0)); // 右侧
for (int i = mid; i >= l; i--) {
int len = mid - i + 1;
f[len] = f[len - 1];
for (int j = M; j >= v[i]; j--) f[len][j] = max(f[len][j], f[len - 1][j - v[i]] + w[i]);
}
for (int i = mid + 1; i <= r; i++) {
int len = i - mid;
g[len] = g[len - 1];
for (int j = M; j >= v[i]; j--) g[len][j] = max(g[len][j], g[len - 1][j - v[i]] + w[i]);
}
vector<node> ls, rs;
for (auto& [ql, qr, V, id] : qry) {
if (qr <= mid) {
ls.emplace_back(ql, qr, V, id);
} else if (mid < ql) {
rs.emplace_back(ql, qr, V, id);
} else {
// (max, +) 卷积合并
for (int j = 0; j <= V; j++) ans[id] = max(ans[id], f[mid - ql + 1][j] + g[qr - mid][V - j]);
}
}
solve(l, mid, ls), solve(mid + 1, r, rs);
}
void _main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> v[i];
for (int i = 1; i <= n; i++) cin >> w[i];
vector<node> vec;
for (int i = 1, l, r, v; i <= q; i++) {
cin >> l >> r >> v;
vec.emplace_back(l, r, v, i);
}
solve(1, n, vec);
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
:::::
P6109 [Ynoi2009] rprmq1
有一个
n \times n 的矩形,元素初值为0 。先进行m 次矩形加,再进行q 次矩形求 max。
:::::success[题解]
考虑本题的实际意义:将
- 在
l_1 时刻对区间[l_2,r_2] 做加法,r_1+1 时刻区间减。 - 查询
[l_1,r_1] 时刻内区间[l_2,r_2] 的历史最值。
查询时间段的历史最值是困难的,但是前缀查询则是容易的。
对时间轴做二区间合并,在中点同侧的查询归入子问题。对于跨过中点的询问,我们从中点出发跑两次历史最值。
为了让每次询问时,有且仅有关联的操作被执行,需要精细讨论一下分治的顺序:
- 先将询问划分为左侧询问、右侧询问和跨过中点的询问三部分。将跨过中点的询问按照时间分组。
- 执行时刻
[l,m] 中的所有操作。 - 在时刻
m+1 进行重置,此时历史最值更新到当前最值。 - 执行时刻
(m,r] 中的所有操作,并且更新右端点关联的询问。 - 撤销时刻
(m,r] 中的所有操作。此时[1,m] 的操作被正确执行,递归(m,r] 。 - 在时刻
m 进行重置,撤销(m,r] 中的历史最值。 - 撤销时刻
[l,m] 中的所有操作,并且更新左端点关联的询问。此时[1,l) 的操作被正确执行,递归[l,m] 。
注意一个细节:对于每个时刻的操作,必须先执行数值小的操作,否则历史最值会捕捉到一个虚假的峰值。所以执行操作要升序执行,撤销操作要倒序执行。
现在我们需要一棵历史和线段树,支持区间加、区间重置,维护当前最值、历史最值。考虑用
::::
考虑
我们称:按照积木大赛得到的答案是平凡的。对于对偶问题,这样的答案会偏小,因为对偶问题的限制是相对松的。
设
其中,
这个 DP 的正确性不是很显然。但是仔细思考一下,对于一个不平凡的情况,如果
观察一下这个 DP 式子,可以继续使用和上一题相同的网格图分治优化 DP。唯一不同的点在于起点
:::::
:::::info[代码]
const int N = 2e5 + 5;
const int64 inf = 1e18;
int n, k, q;
int64 a[N], ans[N], dis[N];
using query = tuple<int, int, int, int, int>; // {x1, y1, x2, y2, id}
vector<query> qry;
void update(int lx, int rx, int ly, int ry, int sx, int sy, const vector<query>& q) {
int s = sx * k + sy;
for (int x = lx; x <= rx; x++) {
for (int y = ly; y <= ry; y++) dis[x * k + y] = -inf;
}
dis[s] = 0;
auto chk = [&](int i) -> bool {return lx <= i / k && i / k <= rx && ly <= i % k && i % k <= ry;};
for (int x = sx; x >= lx; x--) {
for (int y = ry; y >= ly; y--) {
int i = x * k + y;
if (i > s) continue;
if (chk(i + 1)) dis[i] = max(dis[i], dis[i + 1] + max(0LL, a[i + 1] - a[i]));
if (chk(i + k)) dis[i] = max(dis[i], dis[i + k] + a[i + k]);
}
}
for (int x = sx; x <= rx; x++) {
for (int y = ly; y <= ry; y++) {
int i = x * k + y;
if (i < s) continue;
if (chk(i + 1)) dis[i + 1] = max(dis[i + 1], dis[i] + max(0LL, a[i + 1] - a[i]));
if (chk(i + k)) dis[i + k] = max(dis[i + k], dis[i] + a[i + k]);
}
}
for (const auto& [x1, y1, x2, y2, id] : q) {
if (x1 * k + y1 > s || x2 * k + y2 < s) continue;
ans[id] = max(ans[id], a[x1 * k + y1] + dis[x1 * k + y1] + dis[x2 * k + y2]);
}
}
void solve(int lx, int rx, int ly, int ry, vector<query> q) {
if (lx > rx || ly > ry || q.empty()) return;
if (rx - lx > ry - ly) {
int mid = (lx + rx) >> 1;
for (int y = ly; y <= ry; y++) update(lx, rx, ly, ry, mid, y, q);
vector<query> ql, qr;
for (const auto& [x1, y1, x2, y2, id] : q) {
if (x1 < mid && x2 < mid) ql.emplace_back(x1, y1, x2, y2, id);
if (mid < x1 && mid < x2) qr.emplace_back(x1, y1, x2, y2, id);
}
solve(lx, mid - 1, ly, ry, ql), solve(mid + 1, rx, ly, ry, qr);
} else {
int mid = (ly + ry) >> 1;
if (ly == 0 && ry == k - 1) { // 斜边
for (int x = lx; x <= rx; x++) update(lx, rx, ly, ry, x, 0, q);
}
for (int x = lx; x <= rx; x++) update(lx, rx, ly, ry, x, mid, q);
vector<query> ql, qr;
for (const auto& [x1, y1, x2, y2, id] : q) {
if (y1 < mid && y2 < mid) ql.emplace_back(x1, y1, x2, y2, id);
if (mid < y1 && mid < y2) qr.emplace_back(x1, y1, x2, y2, id);
}
solve(lx, rx, ly, mid - 1, ql), solve(lx, rx, mid + 1, ry, qr);
}
}
void _main() {
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1, l, r; i <= q; i++) {
cin >> l >> r;
qry.emplace_back(l / k, l % k, r / k, r % k, i);
}
solve(0, n / k, 0, k - 1, qry);
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
:::::
QOJ888 Travel around China
给出一个
n \times m 的网格图,点有点权。可以上下左右走,求任意点对间最短路之和,对10^9+7 取模。
:::::success[题解]
网格图最短路启示我们使用网格图分治,
对中线两侧的点对计算贡献。容易从中线向两端跑出最短路,分别记为
由于
-
- $f_{1,x_1,y_1}+g_{1,x_2,y_2} \ge f_{0,x_1,y_1}+g_{0,x_2,y_2}$。 - $f_{2,x_1,y_1}+g_{2,x_2,y_2} \ge f_{0,x_1,y_1}+g_{0,x_2,y_2}$。 - 我们需要统计满足上述条件的
f_{0,x_1,y_1}+g_{0,x_2,y_2} 之和。
发现上述条件其实与
将
钦定
现在答案还漏算了同一列的情况。对于同列点
综上,我们得到的算法复杂度满足
:::::
:::::info[代码]
const int N = 1.5e5 + 5;
const i64 inf = 1e18;
using node = array<i64, 3>;
using point = tuple<i64, i64, i64, i64, int>; // {x, y, f, g, type}
int n, m, w[3][N];
i64 col[3][3][N], pre[3][3][N], suf[3][3][N], L[3][3][N], R[3][3][N];
struct BIT {
int n, cnt[N * 3]; mint sum[N * 3];
void init(int _n) {n = _n, fill(cnt, cnt + n + 1, 0), fill(sum, sum + n + 1, 0);}
void add(int x, mint c) {
for (; x <= n; x += lowbit(x)) cnt[x]++, sum[x] += c;
}
pair<int, mint> ask(int x) {
int c = 0; mint s = 0;
for (; x >= 1; x -= lowbit(x)) c += cnt[x], s += sum[x];
return {c, s};
}
} B;
void prework() {
for (int c = 1; c <= m; c++)
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) {
for (int k = min(i, j); k <= max(i, j); k++) col[i][j][c] += w[k][c];
pre[i][j][c] = suf[i][j][c] = col[i][j][c];
}
for (int c = 2; c <= m; c++)
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
for (int x = 0; x < 3; x++) for (int y = 0; y < 3; y++) {
i64 val = pre[x][y][c - 1] + w[x][c] + (x == y ? 0 : w[y][c]);
pre[i][j][c] = min(pre[i][j][c], col[i][x][c] - w[x][c] + val + col[y][j][c] - w[y][c]);
}
for (int c = m - 1; c >= 1; c--)
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
for (int x = 0; x < 3; x++) for (int y = 0; y < 3; y++) {
i64 val = suf[x][y][c + 1] + w[x][c] + (x == y ? 0 : w[y][c]);
suf[i][j][c] = min(suf[i][j][c], col[i][x][c] - w[x][c] + val + col[y][j][c] - w[y][c]);
}
}
mint calc(vector<node>& a, vector<node>& b) {
mint res = 0;
for (int i = 0; i < 3; i++) {
int j = i == 0 ? 1 : 0, k = i == 2 ? 1 : 2;
vector<point> p;
vector<i64> d; // 离散化
for (auto& u : a) {
p.emplace_back(u[i] - u[j], u[i] - u[k], u[i], 0, 0);
d.emplace_back(u[i] - u[k]);
}
for (auto& u : b) {
p.emplace_back(u[j] - u[i], u[k] - u[i], 0, u[i], 1);
d.emplace_back(u[k] - u[i]);
}
sort(d.begin(), d.end()), d.erase(unique(d.begin(), d.end()), d.end());
auto idx = [&](i64 x) -> int {
return lower_bound(d.begin(), d.end(), x) - d.begin() + 1;
};
sort(p.begin(), p.end(), [&](const point& a, const point& b) -> bool {
if (get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);
return i > j ? get<4>(a) > get<4>(b) : get<4>(a) < get<4>(b); // x 维严格偏序
});
B.init(d.size() + 1);
for (auto [x, y, f, g, type] : p) {
y = idx(y);
if (type == 0) {
B.add(y, f);
} else {
if (i > k) y--; // y 维严格偏序
if (y <= 0) continue;
auto [cnt, sum] = B.ask(y);
res += sum + mint(cnt) * g;
}
}
} return res;
}
mint solve(int l, int r) {
if (l == r) return 0;
int mid = (l + r) >> 1;
mint res = solve(l, mid) + solve(mid + 1, r);
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) L[i][j][mid] = col[i][j][mid];
for (int c = mid - 1; c >= l; c--)
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
L[i][j][c] = inf;
for (int x = 0; x < 3; x++) L[i][j][c] = min(L[i][j][c], L[x][j][c + 1] + col[i][x][c]);
}
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) R[i][j][mid + 1] = col[i][j][mid + 1];
for (int c = mid + 2; c <= r; c++)
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) {
R[i][j][c] = inf;
for (int x = 0; x < 3; x++) R[i][j][c] = min(R[i][j][c], R[i][x][c - 1] + col[x][j][c]);
}
vector<node> vl, vr;
for (int c = l; c <= mid; c++) for (int i = 0; i < 3; i++) {
node u;
for (int k = 0; k < 3; k++) {
u[k] = inf;
for (int j = 0; j < 3; j++) u[k] = min(u[k], pre[i][j][c] + L[j][k][c] - w[j][c]);
}
vl.emplace_back(u);
}
for (int c = mid + 1; c <= r; c++) for (int i = 0; i < 3; i++) {
node u;
for (int k = 0; k < 3; k++) {
u[k] = inf;
for (int j = 0; j < 3; j++) u[k] = min(u[k], suf[i][j][c] + R[k][j][c] - w[j][c]);
}
vr.emplace_back(u);
}
return res + calc(vl, vr);
}
void _main() {
cin >> n >> m;
for (int i = 0; i < 3; i++) {
for (int j = 1; j <= m; j++) cin >> w[i][j];
}
prework();
mint res = solve(1, m);
for (int c = 1; c <= m; c++)
for (int i = 0; i < 3; i++)
for (int j = i + 1; j < 3; j++) {
i64 d = inf;
for (int k = 0; k < 3; k++) d = min(d, pre[i][k][c] + suf[k][j][c] - w[k][c]);
res += d;
}
cout << res * 2;
}
:::::
P4178 Tree
给定一棵
n 个节点的树,每条边有边权,求出树上两点距离小于等于k 的点对数量。
:::::success[题解]
点分治起手,考虑如何统计跨过根节点的点对数目。
如果使用分别统计的处理方法,我们需要维护一棵平衡树来支持排名查询,代码难度稍大。
下面演示使用容斥的处理方法:先计算当前子树内所有合法点对数,再减去每个儿子内部的点对数。计算儿子内的点对数时,我们钦定点对在其中合并。
点对数的具体计算可以使用双指针。按距离排序后,我们要统计
使用正确的实现,复杂度为
:::::
:::::info[代码]
const int N = 4e4 + 5;
int n, k, cur, ctr, ans, sz[N], vis[N];
vector<pair<int, int>> e[N];
void dfs1(int u, int fa) { // 找重心
sz[u] = 1;
for (auto [v, w] : e[u]) {
if (v == fa || vis[v]) continue;
dfs1(v, u), sz[u] += sz[v];
}
if (!ctr && 2 * sz[u] >= cur) ctr = u;
}
void dfs2(int u, int fa) { // 统计子树大小
cur++;
for (auto [v, w] : e[u]) if (!vis[v] && v != fa) dfs2(v, u);
}
void dfs3(int u, int fa, int dep, vector<int>& vec) { // 统计距离
vec.emplace_back(dep);
for (auto [v, w] : e[u]) {
if (v == fa || vis[v]) continue;
dfs3(v, u, dep + w, vec);
}
}
int calc(int u, int d) {
vector<int> vec; dfs3(u, -1, d, vec);
sort(vec.begin(), vec.end());
int res = 0;
for (int i = 0, j = vec.size() - 1; i < j; ) {
if (vec[i] + vec[j] <= k) res += j - i, i++;
else j--;
} return res;
}
void solve(int u) {
vis[u] = true, ans += calc(u, 0);
for (auto [v, w] : e[u]) {
if (vis[v]) continue;
ans -= calc(v, w);
cur = ctr = 0, dfs2(v, u), dfs1(v, u), solve(ctr);
}
}
void _main() {
cin >> n;
for (int i = 1, u, v, w; i < n; i++) {
cin >> u >> v >> w;
e[u].emplace_back(v, w), e[v].emplace_back(u, w);
}
cin >> k, cur = n, dfs1(1, -1);
solve(ctr), cout << ans;
}
:::::
CF293E Close Vertices
给定一棵
n 个节点的树,边带权,给出X,Y ,求树上边数\le X 且距离\le Y 的路径数。
:::::success[题解]
对
对
做完了,复杂度
:::::
:::::info[代码]
const int N = 1e5 + 5;
int n, X, Y, cur, ctr, sz[N], vis[N];
i64 ans, tr[N];
void add(int x, i64 c) {
for (x++; x < N; x += lowbit(x)) tr[x] += c;
}
i64 ask(int x) {
i64 res = 0;
for (x++; x >= 1; x -= lowbit(x)) res += tr[x];
return res;
}
vector<pair<int, int>> e[N];
void dfs1(int u, int fa) { // 找重心
sz[u] = 1;
for (auto [v, w] : e[u]) {
if (v == fa || vis[v]) continue;
dfs1(v, u), sz[u] += sz[v];
}
if (!ctr && 2 * sz[u] >= cur) ctr = u;
}
void dfs2(int u, int fa) { // 统计子树大小
cur++;
for (auto [v, w] : e[u]) if (!vis[v] && v != fa) dfs2(v, u);
}
void dfs3(int u, int fa, int dep, int dis, vector<pair<int, int>>& vec) { // 统计深度 & 距离
vec.emplace_back(dis, dep);
for (auto [v, w] : e[u]) {
if (v == fa || vis[v]) continue;
dfs3(v, u, dep + 1, dis + w, vec);
}
}
i64 calc(int u, int dep, int dis) {
vector<pair<int, int>> vec; dfs3(u, -1, dep, dis, vec);
sort(vec.begin(), vec.end());
for (auto [_, d] : vec) add(d, 1);
i64 res = 0;
int i = 0, j = vec.size() - 1;
while (i < j) {
auto [dis1, dep1] = vec[i]; auto [dis2, dep2] = vec[j];
if (dis1 + dis2 <= Y) add(dep1, -1), res += ask(X - dep1), i++;
else add(dep2, -1), j--;
}
if (i == j) add(vec[i].second, -1);
return res;
}
void solve(int u) {
vis[u] = true, ans += calc(u, 0, 0);
for (auto [v, w] : e[u]) {
if (vis[v]) continue;
ans -= calc(v, 1, w);
cur = ctr = 0, dfs2(v, u), dfs1(v, u), solve(ctr);
}
}
void _main() {
cin >> n >> X >> Y;
for (int u = 2, v, w; u <= n; u++) {
cin >> v >> w;
e[u].emplace_back(v, w), e[v].emplace_back(u, w);
}
cur = n, dfs1(1, -1);
solve(ctr), cout << ans;
}
:::::
P5311 [Ynoi2011] 成都七中
给你一个
n 个节点的无根树,点有颜色,q 次查询给出l,r, x ,求保留[l,r] 中的节点后x 所在连通块颜色数。
:::::success[题解]
记
点分治起手,设分治中心为
现在问题转化为:求从
设
于是从
将颜色去重后进行二维数点。对于同种颜色,若存在两点
采用类似于 HH 的项链的处理方式,维护一个树状数组,同时记录每种颜色上一次出现的位置,激活新位置时要删除上一个位置。
按照上述过程实现,视
::::::
:::::info[代码]
const int N = 1e5 + 5;
using query = tuple<int, int, int, int>; // {l, r, x, id}
using point = tuple<int, int, int>; // {x, y, col}
struct BIT {
int tr[N];
void add(int x, int c) {
for (; x < N; x += lowbit(x)) tr[x] += c;
}
int ask(int x) {
int res = 0;
for (; x >= 1; x -= lowbit(x)) res += tr[x];
return res;
}
} B;
int n, q, col[N], ans[N];
vector<int> e[N];
int ctr, cur, sz[N], vis[N];
void dfs1(int u, int fa) {
sz[u] = 1;
for (int v : e[u]) {
if (v == fa || vis[v]) continue;
dfs1(v, u), sz[u] += sz[v];
}
if (!ctr && 2 * sz[u] >= cur) ctr = u;
}
void dfs2(int u, int fa) {
cur++;
for (int v : e[u]) if (v != fa && !vis[v]) dfs2(v, u);
}
int mn[N], mx[N], bel[N];
void dfs3(int u, int fa, int minv, int maxv, int b, vector<int>& vec) {
minv = min(minv, u), maxv = max(maxv, u);
mn[u] = minv, mx[u] = maxv, bel[u] = b, vec.emplace_back(u);
for (int v : e[u]) if (v != fa && !vis[v]) dfs3(v, u, minv, maxv, b, vec);
}
int last[N];
vector<query> child[N];
vector<pair<int, int>> cp[N];
void update(int u, vector<query>& q, vector<pair<int, vector<query>>>& nxt) {
vector<int> vec = {u};
mn[u] = u, mx[u] = u, bel[u] = -1;
for (int v : e[u]) {
if (!vis[v]) dfs3(v, u, u, u, v, vec);
}
vector<query> now;
for (auto& [l, r, x, id] : q) {
if (l <= mn[x] && mx[x] <= r) now.emplace_back(l, r, x, id);
else child[bel[x]].emplace_back(l, r, x, id);
}
for (int v : e[u]) { // 下传询问
if (vis[v] || child[v].empty()) continue;
nxt.emplace_back(v, child[v]), child[v].clear();
}
// 扫描线
vector<point> p;
for (int v : vec) cp[col[v]].emplace_back(mn[v], mx[v]);
for (int v : vec) { // 去重
if (cp[col[v]].empty()) continue;
sort(cp[col[v]].begin(), cp[col[v]].end(), greater<pair<int, int>>());
int ymin = 1e9;
for (auto& [x, y] : cp[col[v]]) {
if (y < ymin) ymin = y, p.emplace_back(x, y, col[v]);
}
cp[col[v]].clear();
}
sort(now.begin(), now.end(), greater<query>());
sort(p.begin(), p.end(), greater<point>());
int i = 0;
vector<int> undo;
for (auto& [l, r, x, id] : now) {
for (; i < (int)p.size() && get<0>(p[i]) >= l; i++) {
auto& [_, y, c] = p[i];
if (last[c]) B.add(last[c], -1);
last[c] = y, B.add(last[c], 1);
undo.emplace_back(c);
}
ans[id] = B.ask(r);
}
for (int c : undo) if (last[c]) B.add(last[c], -1), last[c] = 0;
}
void solve(int u, vector<query>& q) {
if (q.empty()) return;
vis[u] = true;
vector<pair<int, vector<query>>> nxt;
update(u, q, nxt);
for (auto& [v, vec] : nxt) {
cur = ctr = 0, dfs2(v, u), dfs1(v, u);
solve(ctr, vec);
}
}
void _main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> col[i];
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
vector<query> vec;
for (int i = 1, l, r, x; i <= q; i++) {
cin >> l >> r >> x;
vec.emplace_back(l, r, x, i);
}
cur = n, dfs1(1, -1), solve(ctr, vec);
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
:::::
P14012 [POCamp 2023] 枫树 / Maple Tree
交互题。交互库有一个大小为
n 的无根树,边带权。一次询问给出a,b,c ,查询\text{dis}(a,b)<\text{dis}(a,c) 是否成立。保证任意两点距离不同,且节点度数\le 3 。还原树的形态。
:::::success[题解]
不妨将
这得到的是一个拓扑序。考虑按拓扑序增量构造,一次加点就是加叶子,只需确定叶子的父亲。
另一个重要观察是,可以通过一次询问排除一半子树。具体地,对于叶子
| 注意到树是三度化的,这恰好为边分治提供了条件。于是我们用边分治挂叶子,一次加点可以做到 |
|---|
:::::info[代码]
const int N = 1005;
int n, p[N], sz[N], vis[N];
vector<int> e[N];
bool ask(int x, int y, int z) {
cout << "? " << y << ' ' << z << ' ' << x << endl;
char c; cin >> c;
return c == 'A';
}
void dfs1(int u, int fa) {
sz[u] = 1;
for (int v : e[u]) {
if (v == fa || vis[v]) continue;
dfs1(v, u), sz[u] += sz[v];
}
}
void dfs2(int u, int fa) {
vis[u] = true;
for (int v : e[u]) {
if (v == fa || vis[v]) continue;
dfs2(v, u);
}
}
void solve(int x, int u) {
dfs1(u, -1); int c = sz[u];
if (c == 1) {
e[u].emplace_back(x), e[x].emplace_back(u);
return;
}
int p = -1, q = -1, mw = 1e9;
function<void(int, int)> dfs = [&](int u, int fa) -> void {
for (int v : e[u]) {
if (v == fa || vis[v]) continue;
int w = max(sz[v], c - sz[v]);
if (w < mw) p = u, q = v, mw = w;
dfs(v, u);
}
};
dfs(u, -1);
if (ask(x, p, q)) dfs2(q, p), solve(x, p);
else dfs2(p, q), solve(x, q);
}
void _main() {
cin >> n;
iota(p + 1, p + n + 1, 1);
stable_sort(p + 2, p + n + 1, [](int x, int y) -> bool {
return ask(1, x, y);
});
for (int i = 2; i <= n; i++) {
fill(vis + 1, vis + n + 1, 0);
solve(p[i], 1);
}
cout << "!\n";
for (int u = 1; u <= n; u++)
for (int v : e[u]) if (u < v) cout << u << ' ' << v << '\n';
cout << endl;
}
:::::
P4219 [BJOI2014] 大融合
维护一个
n 个点的森林,初始两两无边。支持加边,查询有几条路径经过给定的边。
:::::success[题解]
考虑查询操作的答案,忽略边
不妨将“忽略”看成是一次删边,在查询后再加边。具体地,对于一次查询,我们新建三个时刻,在时刻
可以用线段树分治 + 可撤销并查集维护,视
:::::
:::::info[代码]
const int N = 3e5 + 5;
int n, q, k;
struct unionfind {
int fa[N], sz[N];
stack<int> st;
unionfind() {iota(fa, fa + N, 0), fill(sz, sz + N, 1);}
int find(int x) {return x == fa[x] ? x : find(fa[x]);}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
fa[x] = y, sz[y] += sz[x], st.emplace(x);
}
void undo(int x) {
while ((int) st.size() > x) {
int u = st.top(); st.pop();
if (u != fa[u]) sz[fa[u]] -= sz[u], fa[u] = u;
}
}
} dsu;
#define ls (rt << 1)
#define rs (rt << 1 | 1)
vector<pair<int, int>> val[N << 2];
void insert(int tl, int tr, const pair<int, int>& c, int l = 1, int r = N, int rt = 1) {
if (tl <= l && r <= tr) return val[rt].emplace_back(c), void();
int mid = (l + r) >> 1;
if (tl <= mid) insert(tl, tr, c, l, mid, ls);
if (tr > mid) insert(tl, tr, c, mid + 1, r, rs);
}
map<pair<int, int>, int> last;
pair<int, int> ask[N];
i64 cnt, ans[N];
void solve(int l = 1, int r = N, int rt = 1) {
int step = dsu.st.size();
for (auto [u, v] : val[rt]) dsu.unite(u, v);
if (l == r) {
auto [u, v] = ask[l];
if (u != 0) {
u = dsu.find(u), v = dsu.find(v);
cout << 1LL * dsu.sz[u] * dsu.sz[v] << '\n';
}
return dsu.undo(step), void();
}
int mid = (l + r) >> 1;
solve(l, mid, ls), solve(mid + 1, r, rs), dsu.undo(step);
}
void _main() {
cin >> n >> q;
for (int i = 1, u, v; i <= q; i++) {
char opt; cin >> opt >> u >> v;
if (u > v) swap(u, v);
pair<int, int> e = {u, v};
if (opt == 'A') last[e] = ++k;
else insert(last[e], k, e), ask[++k] = e, last[e] = ++k;
}
for (auto [e, st] : last) insert(st, k, e);
solve();
}
:::::
CF601E A Museum Robbery
有
n 件物品,体积为v_i ,价值为w_i 。支持下列操作:
- 加入物品。
- 删除物品。
- 对所有
V \le k 询问容量为V 的 01 背包。*注意体积 & 价值的表示与原题相反。*
:::::success[题解]
背包追加是
但是我们发现每个物品出现的时间是一个时间段,考虑线段树分治,在进入子树时进行
没有必要考虑退背包等科技。可以直接
复杂度为
:::::
:::::info[代码]
const int N = 1e5 + 5, M = 1e3 + 5;
const mint base = 10000019;
int n, k, q, cnt, cur;
tuple<int, int, int, int> e[N];
#define ls (rt << 1)
#define rs (rt << 1 | 1)
vector<pair<int, int>> val[N << 2];
void insert(int tl, int tr, const pair<int, int>& c, int l = 1, int r = cur, int rt = 1) {
if (tl <= l && r <= tr) return val[rt].emplace_back(c), void();
int mid = (l + r) >> 1;
if (tl <= mid) insert(tl, tr, c, l, mid, ls);
if (tr > mid) insert(tl, tr, c, mid + 1, r, rs);
}
void solve(vector<int>& dp, int l = 1, int r = cur, int rt = 1) {
vector<int> f(dp.begin(), dp.end());
for (auto& [v, w] : val[rt]) {
for (int i = k; i >= v; i--) f[i] = max(f[i], f[i - v] + w);
}
if (l == r) {
mint res = 0;
for (int i = k; i >= 1; i--) res = res * base + f[i];
return cout << res << '\n', void();
}
int mid = (l + r) >> 1;
solve(f, l, mid, ls), solve(f, mid + 1, r, rs);
}
void _main() {
cin >> n >> k;
for (int i = 1, v, w; i <= n; i++) cin >> w >> v, e[i] = {v, w, 1, -1};
cin >> q, cnt = n, cur = 1;
for (int opt, v, w; q--; ) {
cin >> opt;
if (opt == 1) cin >> w >> v, e[++cnt] = {v, w, cur, -1};
else if (opt == 2) cin >> v, get<3>(e[v]) = cur - 1;
else cur++; // cur 作为查询时刻
}
cur--;
for (int i = 1; i <= cnt; i++) {
auto [v, w, l, r] = e[i];
if (r == -1) r = cur;
if (l <= r) insert(l, r, {v, w});
}
vector<int> f(M + 5);
solve(f);
}
:::::
P2056 [ZJOI2007] 捉迷藏
给你一棵无根树,你需要维护一个点集
S ,初始时S=\{1,2,\cdots,n\} 。有如下操作:
- 将一个节点加入 / 移出点集
S 。- 查询点集
S 的直径。
:::::success[题解]
对于动态维护点集直径的问题,我们有结论:设
求出 LCA 维护树上距离,即可做到
我们发现每个点在点集中出现的时刻也是一个时间段,可以线段树分治,用同样的方法加点。
直接将修改后的直径端点复制给儿子,让儿子继续递归,即可做到撤销的效果。
视
:::::
:::::info[代码]
const int N = 6e5 + 5;
int n, q, last[N], ins[N];
vector<int> e[N];
int sz[N], fa[N], dep[N], son[N], top[N];
void dfs1(int u) {
sz[u] = 1;
for (int v : e[u]) {
if (v == fa[u]) continue;
fa[v] = u, dep[v] = dep[u] + 1, dfs1(v), sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int t) {
top[u] = t;
if (son[u]) dfs2(son[u], t);
for (int v : e[u]) {
if (v != fa[u] && v != son[u]) dfs2(v, v);
}
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
} return dep[u] < dep[v] ? u : v;
}
int dis(int u, int v) {
if (u == -1 || v == -1) return -1;
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
#define ls (rt << 1)
#define rs (rt << 1 | 1)
vector<int> val[N << 2];
bool ask[N];
void insert(int tl, int tr, int c, int l = 1, int r = q + 2, int rt = 1) {
if (tl <= l && r <= tr) return val[rt].emplace_back(c), void();
int mid = (l + r) >> 1;
if (tl <= mid) insert(tl, tr, c, l, mid, ls);
if (tr > mid) insert(tl, tr, c, mid + 1, r, rs);
}
void solve(int u, int v, int l = 1, int r = q + 2, int rt = 1) {
for (int w : val[rt]) {
int d0 = dis(u, v), d1 = dis(u, w), d2 = dis(v, w);
if (u == -1 || v == -1) u = v = w;
else if (d1 >= d0 && d1 >= d2) v = w;
else if (d2 >= d0 && d2 >= d1) u = v, v = w;
}
if (l == r) {
if (ask[l]) cout << dis(u, v) << '\n';
return;
}
int mid = (l + r) >> 1;
solve(u, v, l, mid, ls), solve(u, v, mid + 1, r, rs);
}
void _main() {
cin >> n;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].emplace_back(v), e[v].emplace_back(u);
}
cin >> q, dfs1(1), dfs2(1, 1);
fill(last + 1, last + n + 1, 1), fill(ins + 1, ins + n + 1, 1);
for (int i = 2, x; i <= q + 1; i++) {
char opt; cin >> opt;
if (opt == 'C') {
cin >> x;
if (ins[x]) ins[x] = 0, insert(last[x], i, x);
else ins[x] = 1, last[x] = i;
} else {
ask[i] = true;
}
}
for (int i = 1; i <= n; i++) {
if (ins[i]) insert(last[i], q + 2, i);
}
solve(-1, -1);
}
:::::
P3206 [HNOI2010] 城市建设
你需要维护一个
n 个点m 条边的无向带权图。q 次操作,修改一条边的边权,然后查询最小生成树的边权和。
:::::success[题解]
线段树分治起手,但是加边删边无法简单地维护 MST,使用 LCT 常数过大且实现难度大。
考虑在线段树叶子节点直接跑
本题的精妙之处在于,在进入子树递归时,只保留当前不确定是否在 MST 中的边。
在线段树上的节点
- 动态边集
E_0 :这些边在时间[l,r] 内权值会被修改。 - 静态边集
E_1 :这些边在时间[l,r] 内不变。可以发现E_1 =E \setminus E_0 。
通过分析
-
删除无用边:令
E_2 \gets E_1 。对于(u,v,w) \in E_0 ,将(u,v,+\infty) 加入E_2 ,对G_2=(V,E_2) 跑 MST。
此时 Kruskal 优先选择E_1 中的边作为 MST 中的边。在这种情形下,若e \in E_1 且e 不属于 MST,这说明在G_1=(V,E_1) 中已经存在了连接e 两端的路径,则边e 一定无用。
对于这种边e ,我们直接将其删除。 -
锁定必选边:令
E_3 \gets E_1 。对于(u,v,w) \in E_0 ,将(u,v,-\infty) 加入E_3 ,对G_3=(V,E_3) 跑 MST。
此时 Kruskal 优先选择E_0 中的边作为 MST 中边。在这种情形下,若e \in E_1 且e 还属于 MST,这说明在G_0=(V,E_0) 中e 的两端是不连通的,而e 的边权是将其连通的最小代价,则边e 是必选边。
对于必选边e ,可以提前将e 的权值加入答案,然后将e 的两个端点缩成一点,边e 不参与后续计算。
缩点后
实现的时候,我们不用建立线段树的显式结构,可以直接递归分治。所以这个东西其实更像 CDQ 分治。代码写的有点乱。
:::::
:::::info[代码]
const int N = 7e4 + 5, inf = 1e9;
using modify = pair<int, int>; // {id, w}
using edge = tuple<int, int, int>; // {u, v, id}
using wedge = tuple<int, int, int, bool, int>; // {w, u, v, in E1, id}
int n, m, q, fa[N], in0[N], val[N];
modify mod[N];
i64 ans[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void init(vector<edge>& e) {
for (auto [u, v, id] : e) fa[u] = u, fa[v] = v;
}
void init(vector<wedge>& e) {
for (auto [w, u, v, is1, id] : e) fa[u] = u, fa[v] = v;
}
void solve(int l, int r, vector<edge>& e, i64 tot) {
auto cmp = [&](const edge& a, const edge& b) -> bool {
return val[get<2>(a)] < val[get<2>(b)];
};
if (l == r) {
auto [id, w] = mod[l];
val[id] = w, init(e), sort(e.begin(), e.end(), cmp), ans[l] = tot;
for (auto [u, v, id] : e) {
u = find(u), v = find(v);
if (u != v) fa[u] = v, ans[l] += val[id];
}
return;
}
// 1. 划分 E0, E1
for (int i = l; i <= r; i++) in0[mod[i].first] = true;
vector<edge> e0, e1;
for (auto [u, v, id] : e) {
if (in0[id]) e0.emplace_back(u, v, id);
else e1.emplace_back(u, v, id);
}
for (int i = l; i <= r; i++) in0[mod[i].first] = false;
// 2. 删除无用边
vector<wedge> e2;
for (auto [u, v, id] : e1) e2.emplace_back(val[id], u, v, 1, id);
for (auto [u, v, id] : e0) e2.emplace_back(inf, u, v, 0, id);
init(e2), sort(e2.begin(), e2.end());
vector<edge> e1n;
for (auto [w, u, v, is1, id] : e2) {
int fu = find(u), fv = find(v);
if (fu == fv) continue;
fa[fu] = fv;
if (is1) e1n.emplace_back(u, v, id);
}
// 3. 锁定必选边
vector<wedge> e3;
for (auto [u, v, id] : e1n) e3.emplace_back(val[id], u, v, 1, id);
for (auto [u, v, id] : e0) e3.emplace_back(-inf, u, v, 0, id);
init(e3), sort(e3.begin(), e3.end());
vector<edge> must, pend;
for (auto [w, u, v, is1, id] : e3) {
int fu = find(u), fv = find(v);
if (fu != fv) {
fa[fu] = fv;
if (is1) tot += val[id], must.emplace_back(u, v, id);
} else {
if (is1) pend.emplace_back(u, v, id);
}
}
// 4. 缩点
init(e);
for (auto [u, v, id] : must) fa[find(u)] = find(v);
vector<edge> en;
for (auto [u, v, id] : pend) {
u = find(u), v = find(v);
if (u == v) continue;
en.emplace_back(u, v, id);
}
for (auto [u, v, id] : e0) {
u = find(u), v = find(v);
if (u == v) continue;
en.emplace_back(u, v, id);
}
// 5. 递归
int mid = (l + r) >> 1;
solve(l, mid, en, tot), solve(mid + 1, r, en, tot);
}
void _main() {
cin >> n >> m >> q;
iota(fa + 1, fa + n + 1, 1);
vector<edge> e;
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
e.emplace_back(u, v, i), val[i] = w;
}
for (int i = 1; i <= q; i++) cin >> mod[i];
solve(1, q, e, 0);
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
:::::
P9168 [省选联考 2023] 人员调度
给你一棵以
1 为根的有根树,有k 个人初始位于x_1,x_2,\cdots,x_k ,且每个人有一个权值v_i 。你需要进行
q 次操作,支持加人、删人。在开始和每次操作后,查询如下问题的答案:将每个人的位置改到子树内,定义得分为每个节点上权值最大值的和,求最大得分。查询之间独立。
:::::success[题解]
设
我们维护一个多重集
如果
使用可并堆或者 multiset 启发式合并维护,复杂度
注意到题目中加人删人的操作使得每个人的出现时间是一个时间段,考虑线段树分治,将删除变成撤销。现在必须正面维护合并的过程。
直接对着集合合并维护是困难的,考虑加点过程,关注其对答案的影响。
为每个节点维护一个剩余容量
当我们在
- 如果保留这个人,则会占用
u 所在根链的剩余容量。即对于u 的所有祖先p ,f_p \gets f_p-1 。 - 因此,判断加点是否合并,只需找到深度最深的容量为
0 的点p 。- 若
p 不存在,路径容量充足,直接保留。 - 若存在
p ,此时我们在p 子树内找到权值最小的人,设其权值为x' 。若x >x' 则替换,否则放弃。
- 若
先重链剖分,建一棵支持区间加法、区间求最小值的线段树来维护
再在每个节点开一个 multiset,维护当前时刻被选中并被放到
综上,视
:::::
:::::info[代码]
const int N = 2e5 + 5, inf = 1e9;
using node = pair<int, int>; // {val, id}
int n, k, q, fa[N];
vector<int> e[N];
multiset<node> st[N];
int dn, dep[N], sz[N], son[N], dfn[N], top[N], rev[N];
void dfs1(int u) {
sz[u] = 1;
for (int v : e[u]) {
dep[v] = dep[u] + 1, dfs1(v), sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int t) {
dfn[u] = ++dn, rev[dn] = u, top[u] = t;
if (son[u]) dfs2(son[u], t);
for (int v : e[u]) if (v != son[u]) dfs2(v, v);
}
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
int fmin[N << 2], tag[N << 2];
node vmin[N << 2];
void pushup(int rt) {fmin[rt] = min(fmin[ls], fmin[rs]), vmin[rt] = min(vmin[ls], vmin[rs]);}
void apply(int rt, int c) {fmin[rt] += c, tag[rt] += c;}
void pushdown(int rt) {
if (!tag[rt]) return;
apply(ls, tag[rt]), apply(rs, tag[rt]), tag[rt] = 0;
}
void build(int l = 1, int r = n, int rt = 1) {
if (l == r) return fmin[rt] = sz[rev[l]], vmin[rt] = {inf, -1}, void();
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs), pushup(rt);
}
void fadd(int tl, int tr, int c, int l = 1, int r = n, int rt = 1) {
if (tl <= l && r <= tr) return apply(rt, c), void();
int mid = (l + r) >> 1; pushdown(rt);
if (tl <= mid) fadd(tl, tr, c, l, mid, ls);
if (tr > mid) fadd(tl, tr, c, mid + 1, r, rs);
pushup(rt);
}
int find(int tl, int tr, int l = 1, int r = n, int rt = 1) {
if (fmin[rt] > 0) return -1;
if (l == r) return l;
int mid = (l + r) >> 1, res = -1; pushdown(rt);
if (tr > mid) res = find(tl, tr, mid + 1, r, rs);
if (tl <= mid && res == -1) res = find(tl, tr, l, mid, ls);
return res;
}
void vadd(int x, int l = 1, int r = n, int rt = 1) {
if (l == r) {
int u = rev[x];
vmin[rt] = st[u].empty() ? node(inf, -1) : *st[u].begin();
return;
}
int mid = (l + r) >> 1; pushdown(rt);
if (x <= mid) vadd(x, l, mid, ls);
else vadd(x, mid + 1, r, rs);
pushup(rt);
}
node vask(int tl, int tr, int l = 1, int r = n, int rt = 1) {
if (tl <= l && r <= tr) return vmin[rt];
int mid = (l + r) >> 1; pushdown(rt);
if (tl <= mid && mid < tr) return min(vask(tl, tr, l, mid, ls), vask(tl, tr, mid + 1, r, rs));
return tl <= mid ? vask(tl, tr, l, mid, ls) : vask(tl, tr, mid + 1, r, rs);
}
} sgt;
int find(int u) {
for (; u; u = fa[top[u]]) {
int id = sgt.find(dfn[top[u]], dfn[u]);
if (id != -1) return rev[id];
} return -1;
}
void fadd(int u, int c) {
for (; u; u = fa[top[u]]) sgt.fadd(dfn[top[u]], dfn[u], c);
}
vector<int> val[N << 2];
void insert(int tl, int tr, int c, int l = 0, int r = q, int rt = 1) {
if (tl <= l && r <= tr) return val[rt].emplace_back(c), void();
int mid = (l + r) >> 1;
if (tl <= mid) insert(tl, tr, c, l, mid, ls);
if (tr > mid) insert(tl, tr, c, mid + 1, r, rs);
}
node p[N];
i64 cur, ans[N];
void add(int x) {
auto [v, u] = p[x];
cur += v, st[u].emplace(v, x);
sgt.vadd(dfn[u]), fadd(u, -1);
}
void del(int x) {
auto [v, u] = p[x];
cur -= v, st[u].erase(st[u].find(node(v, x)));
sgt.vadd(dfn[u]), fadd(u, 1);
}
stack<pair<int, int>> his;
void solve(int l = 0, int r = q, int rt = 1) {
int step = his.size();
for (int id : val[rt]) {
int u = find(p[id].second);
if (u == -1) {
add(id), his.emplace(id, -1);
} else {
node res = sgt.vask(dfn[u], dfn[u] + sz[u] - 1);
if (res.first >= p[id].first) continue;
del(res.second), add(id);
his.emplace(id, res.second);
}
}
int mid = (l + r) >> 1;
if (l == r) ans[l] = cur;
else solve(l, mid, ls), solve(mid + 1, r, rs);
while ((int)his.size() > step) {
auto [x, y] = his.top(); his.pop(), del(x);
if (y != -1) add(y);
}
}
int L[N], R[N];
void _main() {
cin >> n >> n >> k >> q;
for (int u = 2; u <= n; u++) cin >> fa[u], e[fa[u]].emplace_back(u);
dfs1(1), dfs2(1, 1), sgt.build();
for (int i = 1, x, y; i <= k; i++) cin >> x >> y, p[i] = {y, x}, R[i] = q;
int m = k;
for (int i = 1, opt, x, v; i <= q; i++) {
cin >> opt >> x;
if (opt == 1) cin >> v, m++, p[m] = {v, x}, L[m] = i, R[m] = q;
else R[x] = i - 1;
}
for (int i = 1; i <= m; i++) if (L[i] <= R[i]) insert(L[i], R[i], i);
solve();
for (int i = 0; i <= q; i++) cout << ans[i] << ' ';
}
:::::
P3157 [CQOI2011] 动态逆序对
给出一个长为
n 的排列,q 次操作,每次删除一个数,查询删除之前序列的逆序对数。
:::::success[题解]
先对原序列跑归并排序 / 树状数组求出逆序对数,问题变为每次操作减少的逆序对数。
把每个元素被删除的时刻
这是一个三维偏序问题,做两次 CDQ 分治即可
:::::
:::::info[代码]
const int N = 1e5 + 5;
int n, q, a[N], pos[N], t[N];
i64 cnt[N];
struct BIT {
int tr[N];
void add(int x, int c) {
for (; x <= n; x += lowbit(x)) tr[x] += c;
}
int ask(int x) {
int res = 0;
for (; x >= 1; x -= lowbit(x)) res += tr[x];
return res;
}
} B;
struct CDQ {
using node = tuple<int, int, int>; // {y, z, id}
node a[N]; BIT B; i64 ans[N];
void solve(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
solve(l, mid), solve(mid + 1, r);
int i = l, j = mid + 1;
vector<node> tmp;
auto iadd = [&]() -> void {
auto [y, z, id] = a[i];
B.add(z, 1), tmp.emplace_back(a[i++]);
};
auto jadd = [&]() -> void {
auto [y, z, id] = a[j];
ans[id] += B.ask(z - 1), tmp.emplace_back(a[j++]);
};
while (i <= mid && j <= r) {
if (get<0>(a[i]) < get<0>(a[j])) iadd();
else jadd();
}
while (i <= mid) iadd();
while (j <= r) jadd();
for (int k = l; k <= mid; k++) B.add(get<1>(a[k]), -1);
copy(tmp.begin(), tmp.end(), a + l);
}
} C1, C2;
void _main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i], pos[a[i]] = i;
fill(t + 1, t + n + 1, q + 1);
for (int i = 1, x; i <= q; i++) cin >> x, t[pos[x]] = i;
i64 inv = 0;
for (int i = 1; i <= n; i++) inv += i - 1 - B.ask(a[i]), B.add(a[i], 1);
for (int i = 1; i <= n; i++) {
C1.a[i] = {n - a[i] + 1, q - t[i] + 2, i};
C2.a[n - i + 1] = {a[i], q - t[i] + 2, i};
}
C1.solve(1, n), C2.solve(1, n);
for (int i = 1; i <= n; i++) {
if (t[i] <= q) cnt[t[i]] = C1.ans[i] + C2.ans[i];
}
for (int i = 1; i <= q; i++) cout << inv << '\n', inv -= cnt[i];
}
:::::
P14957 【模板】离线静态四维数点
给出
n 个元素,元素有四个属性值a_i,b_i,c_i,d_i 。q 次询问给出A,B,C,D ,求满足a_i \le A \land b_ i\le B \land c_i \ge C \land d_i \ge D 的元素数目。
:::::success[题解]
典型的四维偏序,先对
此时还需考虑
本题有一点细节:需要将
总复杂度为
:::::
:::::info[代码]
const int N = 8e5 + 5;
int n, m, q;
vector<int> vec;
struct node {
int a, b, c, d, type, id, part;
} a[N], b[N];
i64 ans[N];
struct BIT {
int tr[N];
void add(int x, int c) {
for (; x <= m; x += lowbit(x)) tr[x] += c;
}
int ask(int x) {
int res = 0;
for (; x >= 1; x -= lowbit(x)) res += tr[x];
return res;
}
} B;
void cdq(int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
cdq(l, mid), cdq(mid + 1, r);
int i = l, j = mid + 1;
while (i <= mid && j <= r) {
if (b[i].c <= b[j].c) {
if (b[i].part == 0) B.add(b[i].d, 1);
i++;
} else {
if (b[j].part == 1) ans[b[j].id] += B.ask(b[j].d);
j++;
}
}
for (; i <= mid; i++) {
if (b[i].part == 0) B.add(b[i].d, 1);
}
for (; j <= r; j++) {
if (b[j].part == 1) ans[b[j].id] += B.ask(b[j].d);
}
for (int k = l; k <= mid; k++) {
if (b[k].part == 0) B.add(b[k].d, -1);
}
inplace_merge(b + l, b + mid + 1, b + r + 1, [](const node& a, const node& b) -> bool {
return a.c < b.c;
});
}
void solve(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
solve(l, mid), solve(mid + 1, r);
int i = l, j = mid + 1, cnt = 0;
while (i <= mid && j <= r) {
if (a[i].b <= a[j].b) {
if (a[i].type == 0) b[++cnt] = a[i], b[cnt].part = 0;
i++;
} else {
if (a[j].type == 1) b[++cnt] = a[j], b[cnt].part = 1;
j++;
}
}
for (; i <= mid; i++) {
if (a[i].type == 0) b[++cnt] = a[i], b[cnt].part = 0;
}
for (; j <= r; j++) {
if (a[j].type == 1) b[++cnt] = a[j], b[cnt].part = 1;
}
cdq(1, cnt);
inplace_merge(a + l, a + mid + 1, a + r + 1, [](const node& a, const node& b) -> bool {
return a.b < b.b;
});
}
void _main() {
cin >> n >> q;
for (int i = 1, a, b, c, d; i <= n; i++) {
cin >> a >> b >> c >> d;
::a[i] = {a, b, -c, -d, 0, 0, 0};
vec.emplace_back(-d);
}
for (int i = 1, a, b, c, d; i <= q; i++) {
cin >> a >> b >> c >> d;
::a[i + n] = {a, b, -c, -d, 1, i, 0};
vec.emplace_back(-d);
}
sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()), m = vec.size();
for (int i = 1; i <= n + q; i++) a[i].d = lower_bound(vec.begin(), vec.end(), a[i].d) - vec.begin() + 1;
sort(a + 1, a + n + q + 1, [](const node& a, const node& b) -> bool {
if (a.a != b.a) return a.a < b.a;
if (a.b != b.b) return a.b < b.b;
if (a.c != b.c) return a.c < b.c;
return a.d != b.d ? a.d < b.d : a.type < b.type;
});
solve(1, n + q);
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
:::::
P2487 [SDOI2011] 拦截导弹
给出二维平面上的
n 个点(x_i,y_i) 。先求出 LDS 长度,再求出对于每个i 求出第i 个点被选入二维 LDS 的概率。LDS 指最长不升子序列。
:::::success[题解]
根据 ABC354F 的首尾合并思想,可以设计出前后缀 DP,设
同理设
可得第一问答案为
观察 DP 式,转移关系
一些实现细节:
- 反向 DP 时,CDQ 的分治顺序是相反的。
- 对于
g 要开double。
:::::
:::::info[代码]
const int N = 5e4 + 5;
int n, m, d[N];
using info = pair<int, double>;
info operator+ (const info& a, const info& b) {
if (a.first != b.first) return max(a, b);
return {a.first, a.second + b.second};
}
info& operator+= (info& a, const info& b) {return a = a + b;}
struct BIT {
info tr[N];
void add(int x, info c) {
for (; x <= m; x += lowbit(x)) tr[x] += c;
}
info ask(int x) {
info res;
for (; x >= 1; x -= lowbit(x)) res += tr[x];
return res;
}
void clear(int x) {
for (; x <= m; x += lowbit(x)) tr[x] = info(-1, -1);
}
} B1, B2;
struct node {
int id, x, y;
info pre, suf;
} a[N];
void solve1(int l, int r) {
if (l == r) {
if (a[l].pre.first == 0) a[l].pre = info(1, 1);
return;
}
int mid = (l + r) >> 1;
solve1(l, mid);
vector<int> L, R;
for (int i = l; i <= mid; i++) L.emplace_back(i);
for (int i = mid + 1; i <= r; i++) R.emplace_back(i);
sort(L.begin(), L.end(), [](int x, int y) -> bool {return a[x].x > a[y].x;});
sort(R.begin(), R.end(), [](int x, int y) -> bool {return a[x].x > a[y].x;});
int i = 0;
for (int j : R) {
for (; i < (int)L.size() && a[L[i]].x >= a[j].x; i++) B1.add(m - a[L[i]].y + 1, a[L[i]].pre);
info u = B1.ask(m - a[j].y + 1);
if (u.first > 0) a[j].pre += info(u.first + 1, u.second);
}
for (int k = 0; k < i; k++) B1.clear(m - a[L[k]].y + 1);
solve1(mid + 1, r);
}
void solve2(int l, int r) {
if (l == r) {
if (a[l].suf.first == 0) a[l].suf = info(1, 1);
return;
}
int mid = (l + r) >> 1;
solve2(mid + 1, r);
vector<int> L, R;
for (int i = l; i <= mid; i++) L.emplace_back(i);
for (int i = mid + 1; i <= r; i++) R.emplace_back(i);
sort(L.begin(), L.end(), [](int x, int y) -> bool {return a[x].x < a[y].x;});
sort(R.begin(), R.end(), [](int x, int y) -> bool {return a[x].x < a[y].x;});
int i = 0;
for (int j : L) {
for (; i < (int)R.size() && a[R[i]].x <= a[j].x; i++) B2.add(a[R[i]].y, a[R[i]].suf);
info u = B2.ask(a[j].y);
if (u.first > 0) a[j].suf += info(u.first + 1, u.second);
}
for (int k = 0; k < i; k++) B2.clear(a[R[k]].y);
solve2(l, mid);
}
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].x >> a[i].y;
a[i].id = i, d[i] = a[i].y;
}
sort(d + 1, d + n + 1), m = unique(d + 1, d + n + 1) - d - 1;
for (int i = 1; i <= n; i++) a[i].y = lower_bound(d + 1, d + m + 1, a[i].y) - d;
solve1(1, n), solve2(1, n);
int len = 1;
for (int i = 1; i <= n; i++) len = max(len, a[i].pre.first);
cout << len << '\n' << fixed << setprecision(5);
double tot = 0;
for (int i = 1; i <= n; i++) {
if (a[i].pre.first == len) tot += a[i].pre.second;
}
for (int i = 1; i <= n; i++) {
auto [f0, g0] = a[i].pre;
auto [f1, g1] = a[i].suf;
if (f0 + f1 - 1 == len) cout << g0 * g1 / tot << ' ';
else cout << 0.0 << ' ';
}
}
:::::
P5979 [PA 2014] Druzyny
给出
n 个物品,每个物品有属性l_i,r_i ,你需要将它们划分为若干连续段,满足第i 个物品所属连续段长度\in [l_i,r_i] 。求出最大段数和达成此段数的方案数,或者报告无解。方案数对
10^9+7 取模。
:::::success[题解]
容易设计一个朴素 DP,设
方案数容易根据
将
DP 式不满足决策单调性,
将点对
本题最为精妙的点在于将第二个条件按照
第一个条件关于
把一个
复杂度
:::::
:::::info[代码]
const int N = 1e6 + 5, inf = 1e9;
int n, a[N], b[N];
using node = pair<int, mint>;
node operator+ (const node& a, const node& b) {
if (a.first != b.first) return max(a, b);
return {a.first, a.second + b.second};
}
int tot;
struct segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
node sum[N << 2];
void pushup(int rt) {sum[rt] = sum[ls] + sum[rs];}
void build(int l = 0, int r = tot, int rt = 1) {
sum[rt] = node(-inf, 0);
if (l == r) return;
int mid = (l + r) >> 1;
build(l, mid, ls), build(mid + 1, r, rs);
}
void change(int x, const node& c, int l = 0, int r = tot, int rt = 1) {
if (l == r) return sum[rt] = c, void();
int mid = (l + r) >> 1;
if (x <= mid) change(x, c, l, mid, ls);
else change(x, c, mid + 1, r, rs);
pushup(rt);
}
node ask(int tl, int tr, int l = 0, int r = tot, int rt = 1) {
if (tl <= l && r <= tr) return sum[rt];
int mid = (l + r) >> 1;
if (tl <= mid && mid < tr) return ask(tl, tr, l, mid, ls) + ask(tl, tr, mid + 1, r, rs);
return tl <= mid ? ask(tl, tr, l, mid, ls) : ask(tl, tr, mid + 1, r, rs);
}
} sgt;
node dp[N];
vector<pair<int, int>> vec[N];
void solve(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
solve(l, mid);
for (int i = mid + 1; i <= r; i++) vec[i].clear();
for (int i = mid, cl = 1, cr = n; i >= l; i--) {
if (cl > cr || i + cr <= mid) break;
if (i + cl <= r) {
vec[max(mid + 1, i + cl)].emplace_back(i, 1);
vec[min(r + 1, i + cr + 1)].emplace_back(i, -1);
}
cl = max(cl, a[i]), cr = min(cr, b[i]);
}
tot = mid - l + 1, sgt.build();
for (int i = mid + 1, cl = 1, cr = n; i <= r; i++) {
for (auto& [x, op] : vec[i]) {
if (op == 1) sgt.change(x - l + 1, dp[x]);
else sgt.change(x - l + 1, node(-inf, 0));
}
cl = max(cl, a[i]), cr = min(cr, b[i]);
if (cl > cr || i - cr > mid) break;
int ql = max(l, i - cr) - l + 1, qr = min(mid, i - cl) - l + 1;
if (ql > qr) continue;
node u = sgt.ask(ql, qr);
dp[i] = dp[i] + node(u.first + 1, u.second);
}
solve(mid + 1, r);
}
void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
fill(dp + 1, dp + n + 1, node(-inf, 0));
dp[0] = node(0, 1), solve(0, n);
auto [f, g] = dp[n];
if (g.val == 0) cout << "NIE";
else cout << f << ' ' << g;
}
:::::
P4169 [Violet] 天使玩偶/SJY摆棋子
二维平面上初始有
n 个点(x_i,y_i) ,进行q 次操作:
- 加入一个新点。
- 给出
(x_0,y_0) ,求当前点中,与(x_0,y_0) 最近的点到它的曼哈顿距离。
:::::success[题解]
考虑不带修的做法,相当于求如下式子:
带绝对值的式子考虑拆掉绝对值。以
将
另外三个方向类似,取一个相反数再跑 CDQ 即可。细节上注意树状数组初始化为负无穷。视
:::::
:::::info[代码]
const int N = 1e6 + 5, inf = 1e9;
struct node {
int x, y, id, type;
} a[N], b[N];
int ans[N];
struct BIT {
int tr[N];
void init() {fill(tr, tr + N, -inf);}
void add(int x, int c) {
for (; x < N; x += lowbit(x)) tr[x] = max(tr[x], c);
}
int ask(int x) {
int res = -inf;
for (; x >= 1; x -= lowbit(x)) res = max(res, tr[x]);
return res;
}
void clear(int x) {
for (; x < N; x += lowbit(x)) tr[x] = -inf;
}
} B;
int n, q;
void cdq(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
cdq(l, mid), cdq(mid + 1, r);
int i = l, j = mid + 1;
for (; j <= r; j++) {
for (; i <= mid && b[i].x <= b[j].x; i++) {
if (b[i].type == 1) B.add(b[i].y, b[i].x + b[i].y);
}
if (b[j].type == 2) ans[b[j].id] = min(ans[b[j].id], b[j].x + b[j].y - B.ask(b[j].y));
}
for (int k = l; k < i; k++) {
if (b[k].type == 1) B.clear(b[k].y);
}
inplace_merge(b + l, b + mid + 1, b + r + 1, [](const node& a, const node& b) -> bool {
return a.x < b.x;
});
}
void solve(int tx, int ty) {
for (int i = 1; i <= n + q; i++) {
b[i] = a[i];
if (tx) b[i].x = 1e6 - b[i].x + 1;
if (ty) b[i].y = 1e6 - b[i].y + 1;
}
B.init(), cdq(1, n + q);
}
void _main() {
cin >> n >> q;
for (int i = 1, x, y; i <= n; i++) {
cin >> x >> y, x++, y++;
a[i] = {x, y, 0, 1};
}
for (int i = 1, opt, x, y; i <= q; i++) {
cin >> opt >> x >> y; x++, y++;
a[i + n] = {x, y, i, opt};
}
fill(ans + 1, ans + q + 1, inf);
solve(0, 0), solve(0, 1), solve(1, 0), solve(1, 1);
for (int i = 1; i <= q; i++) {
if (ans[i] != inf) cout << ans[i] << '\n';
}
}
:::::
P4690 [Ynoi Easy Round 2016] 镜中的昆虫
维护一个长为
n 的序列a_i ,q 次操作,支持区间覆盖、区间数颜色。
:::::success[题解]
静态区间数颜色是经典题 HH 的项链,做法为离散化后维护
如果本题是单点修改,可以直接上一个 CDQ 分治,将动态问题静态化。此时相当于解决一个单点加矩形求和问题,用扫描线即可处理好所有的修改—询问关系。
考虑区间修改怎么做,发现难以解决的原因是对
基于此,考虑用 ODT 维护序列
这样本题复杂度做到
:::::
:::::info[代码]
const int N = 1e5 + 5, M = 1.4e6 + 5;
using query = tuple<int, int, int>; // {x, l, r}
struct info {
int x, y, id, v;
bool operator< (const info& a) const {return x < a.x;}
};
int n, m, v, tot, cnt, a[N], d[N << 1], ans[N];
query q[N << 1];
info op[M];
struct node {
int l, r;
mutable int v;
node(int a = 0, int b = 0, int c = 0) : l(a), r(b), v(c) {}
bool operator< (const node& a) const {return l < a.l;}
};
set<node> odt;
using IT = set<node>::iterator;
set<int> col[N << 1];
int to[N << 1];
vector<info> vec;
void P(int x, int y, int v) {op[++cnt] = info{x, y, -1, v};}
void Q(int x, int y, int id, int v) {op[++cnt] = info{x, y, id, v};}
IT add(int l, int r, int v) {
to[l] = r;
auto it = col[v].emplace(l).first;
int pre = (it != col[v].begin()) ? *prev(it) : 0;
it++; int nxt = (it != col[v].end()) ? *it : 0;
int u = to[pre] + 1;
P(l, u, 1);
if (nxt) P(nxt, u, -1), P(nxt, r + 1, 1);
return odt.emplace(l, r, v).first;
}
void del(int l, int r, int v, bool keep = 0) {
auto it = col[v].find(l);
int pre = (it != col[v].begin()) ? *prev(it) : 0;
it++; int nxt = (it != col[v].end()) ? *it : 0;
int u = to[pre] + 1;
P(l, u, -1);
if (nxt) P(nxt, u, 1), P(nxt, r + 1, -1);
col[v].erase(col[v].find(l));
if (!keep) odt.erase(odt.find(node(l, r, v)));
}
void del(IT it, bool keep = 0) {del(it->l, it->r, it->v, keep);}
IT split(int x) {
IT it = odt.lower_bound(node(x, 0, 0));
if (it != odt.end() && it->l == x) return it;
auto [l, r, v] = *prev(it);
return del(l, r, v), add(l, x - 1, v), add(x, r, v);
}
void assign(int l, int r, int v) {
IT itr = split(r + 1), itl = split(l);
for (IT it = itl; it != itr; it++) del(it, 1);
odt.erase(itl, itr);
IT pre = odt.lower_bound(node(l, 0, 0));
if (pre != odt.begin() && prev(pre)->v == v) pre--, l = pre->l, del(pre);
IT nxt = odt.upper_bound(node(r, 0, 0));
if (nxt != odt.end() && nxt->v == v) r = nxt->r, del(nxt);
add(l, r, v);
}
struct BIT {
int tr[N];
void add(int x, int c) {
for (; x <= n; x += lowbit(x)) tr[x] += c;
}
int ask(int x) {
int res = 0;
for (; x >= 1; x -= lowbit(x)) res += tr[x];
return res;
}
} B;
void solve(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
solve(l, mid), solve(mid + 1, r);
int i = l, j = mid + 1;
for (; j <= r; j++) {
for (; i <= mid && op[i].x <= op[j].x; i++) {
if (op[i].id == -1) B.add(op[i].y, op[i].v);
}
if (op[j].id != -1) ans[op[j].id] += op[j].v * B.ask(op[j].y);
}
for (int k = l; k < i; k++) {
if (op[k].id == -1) B.add(op[k].y, -op[k].v);
}
inplace_merge(op + l, op + mid + 1, op + r + 1);
}
void _main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i], d[++v] = a[i];
for (int i = 1, opt, l, r, x; i <= m; i++) {
cin >> opt >> l >> r;
if (opt == 1) cin >> x, q[i] = {x, l, r}, d[++v] = x;
else q[i] = {-1, l, r};
}
sort(d + 1, d + v + 1), v = unique(d + 1, d + v + 1) - d - 1;
for (int i = 1; i <= n; i++) a[i] = lower_bound(d + 1, d + v + 1, a[i]) - d;
for (int i = 1; i <= m; i++) {
int& c = get<0>(q[i]);
if (c != -1) c = lower_bound(d + 1, d + v + 1, c) - d;
}
for (int i = 1; i <= n; ) {
int l = i;
while (i <= n && a[i] == a[l]) i++;
add(l, i - 1, a[l]);
}
for (int i = 1; i <= m; i++) {
auto [x, l, r] = q[i];
if (x != -1) {
assign(l, r, x);
} else {
ans[++tot] = 1;
if (l < r) Q(r, l, tot, 1), Q(l, l, tot, -1);
}
}
solve(1, cnt);
for (int i = 1; i <= tot; i++) cout << ans[i] << '\n';
}
:::::
P5331 [SNOI2019] 通信
给定
n 个节点,每个点有点权a_i 。每个节点必须选择下列之一:
- 连接到汇点,代价为
w 。- 连接到前面的节点
j ,满足j<i ,代价为|a_i-a_j| 。要求节点入度不超过1 。求最小代价。
:::::success[题解]
由于只有
考虑节点之间的连接形成的结构,由于题目强制入度出度必须为
经过上述讨论,本题是一个最小权 DAG 路径覆盖问题。可以使用拆点 + 费用流解决。我们将节点拆成入点
这样得到一张
瓶颈在第四步连边,考虑 CDQ 分治优化建图。对于分治区间
本题比较精妙的地方在于处理
将相邻的虚点用双向边连接,容量设为
这样形成一个
:::::
:::::info[代码]
const int N = 1e5 + 5;
int n, w, a[N], cnt;
mincost_flow<N, N> G;
void solve(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
solve(l, mid), solve(mid + 1, r);
vector<int> vec(a + l, a + r + 1);
sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end());
int m = vec.size();
for (int i = 1; i < m; i++) {
G.add(i - 1 + cnt, i + cnt, G.INF, vec[i] - vec[i - 1]);
G.add(i + cnt, i - 1 + cnt, G.INF, vec[i] - vec[i - 1]);
}
for (int i = l; i <= mid; i++) {
int x = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
G.add(x + cnt, i + n, 1, 0);
}
for (int i = mid + 1; i <= r; i++) {
int x = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
G.add(i, x + cnt, 1, 0);
}
cnt += m;
}
void _main() {
cin >> n >> w;
for (int i = 1; i <= n; i++) cin >> a[i];
int s = 0, t = 2 * n + 1; cnt = 2 * n + 2;
for (int i = 1; i <= n; i++) G.add(s, i, 1, 0), G.add(i + n, t, 1, 0), G.add(i, t, 1, w);
solve(1, n);
cout << G(s, t).second;
}
:::::
P14638 [NOIP2025] 序列询问
给你一个长为
n 的整数序列a 。q 次询问给出L,R ,对每个i 求出:\max_{i \in [l,r],r-l+1 \in [L,R]} \sum_{j=l}^r a_j
:::::warning[注意]{open} 做法不是正解,仅供参考。 :::::
:::::success[题解]
注意到特殊性质 D & E,这只能说明一个事实:合法的区间一定跨过序列的中点或四等分点。这启示我们使用序列分治解决本题。
设当前分治区间
设
设
分治结构的好处在于我们钦定合法区间跨过 y....x....m....r 的结构,我们发现
综上,对
开始卡常。先做如下两个优化:
- 在分治内部,不应显式建立
f,g 数组,可以直接用一个变量记前后缀 max,滚动更新。 - 当
[l,r] 的长度小于L 时直接返回。
经过卡常的代码在洛谷 3s 时限下直接获得了 100 分。在 QOJ 上获得了 75 分。
::::info[代码]
const int N = 5e4 + 5;
const i64 inf = 1e18;
static int n, q, L, R;
static i64 a[N], ans[N], mn[18][N], mx[18][N];
static constexpr i64 max(i64 a, i64 b) {return a > b ? a : b;}
static constexpr i64 qmax(int l, int r) {
if (l > r) return -inf;
r++; int k = lg(r - l);
return max(mx[k][l], mx[k][r - (1 << k)]);
}
static constexpr i64 qmin(int l, int r) {
if (l > r) return inf;
r++; int k = lg(r - l);
return min(mn[k][l], mn[k][r - (1 << k)]);
}
static void solve(int l, int r) {
if (r - l + 1 < L) return;
if (l == r) {
if (L == 1) ans[l] = max(ans[l], a[l] - a[l - 1]);
return;
}
int mid = (l + r) >> 1;
solve(l, mid), solve(mid + 1, r);
auto lval = [&](int i) -> i64 {
return qmax(max(mid + 1, i + L - 1), min(r, i + R - 1)) - a[i - 1];
};
auto rval = [&](int i) -> i64 {
return a[i] - qmin(max(l - 1, i - R), min(mid - 1, i - L));
};
i64 pre = lval(l), suf = rval(r);
ans[l] = max(ans[l], pre), ans[r] = max(ans[r], suf);
for (int i = l + 1; i <= mid; i++) pre = max(pre, lval(i)), ans[i] = max(ans[i], pre);
for (int i = r - 1; i > mid; i--) suf = max(suf, rval(i)), ans[i] = max(ans[i], suf);
}
static void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
copy(a, a + n + 1, mx[0]), copy(a, a + n + 1, mn[0]);
for (int i = 1; (1 << i) <= n; i++) {
for (int j = 0; j + (1 << i) - 1 <= n; j++) {
mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
}
}
for (cin >> q; q--; ) {
cin >> L >> R;
fill(ans + 1, ans + n + 1, -inf);
solve(1, n);
u64 res = 0;
for (int i = 1; i <= n; i++) res ^= (u64)i * (u64)ans[i];
cout << res << '\n';
}
}
::::
我们将 ST 表手动内联,并且优化循环范围,使得每次查询有效。
较为关键的优化是,我们可以设定一个阈值
这个做法的执行次数大概是
此代码在洛谷评测机上获得了最慢点 1.93s 的速度,可以在 QOJ 无压力通过。
:::::
:::::info[代码]
const int N = 5e4 + 5, B = 64;
const i64 inf = 1e18;
static int n, q, L, R, len[N];
static i64 a[N], ans[N], mn[16][N], mx[16][N], st[7][B + 5][N];
static void build(int l, int r) {
if (r - l + 1 <= B) {
fill(len + l, len + r + 1, r - l + 1);
for (int i = l; i <= r; i++) {
for (int k = 1; k <= r - l + 1; k++) {
i64 mx = -inf;
for (int x = max(l, i - k + 1); x <= min(r - k + 1, i); x++) {
i64 val = a[x + k - 1] - a[x - 1];
if (val > mx) mx = val;
}
st[0][k][i] = mx;
}
} return;
}
int mid = (l + r) >> 1;
build(l, mid), build(mid + 1, r);
}
static void prework() {
for (int i = 1; i <= n; i++) {
for (int j = 1; (1 << j) <= len[i]; j++) {
for (int k = 1; k + (1 << j) - 1 <= len[i]; k++) {
st[j][k][i] = max(st[j - 1][k][i], st[j - 1][k + (1 << (j - 1))][i]);
}
}
}
}
static void solve(int l, int r) {
if (r - l + 1 < L) return;
if (r - l + 1 <= B) return;
if (l == r) {
if (L == 1) ans[l] = max(ans[l], a[l] - a[l - 1]);
return;
}
int mid = (l + r) >> 1, ql, qr, k;
solve(l, mid), solve(mid + 1, r);
int il = max(l, mid - R + 2), ir = min(mid, r - L + 1);
if (il <= ir) {
i64 pre = -inf;
for (int i = il; i <= ir; i++) {
ql = max(mid + 1, i + L - 1), qr = min(r, i + R - 1);
i64 val = -inf;
if (ql <= qr) k = __lg(qr - ql + 1), val = max(mx[k][ql], mx[k][qr - (1 << k) + 1]) - a[i - 1];
if (val > pre) pre = val;
if (pre > ans[i]) ans[i] = pre;
}
if (pre != -inf)
for (int i = ir + 1; i <= mid; i++) ans[i] = max(ans[i], pre);
}
int jl = max(mid + 1, l + L - 1), jr = min(r, mid + R - 1);
if (jl <= jr) {
i64 suf = -inf;
for (int i = jr; i >= jl; i--) {
ql = max(l - 1, i - R), qr = min(mid - 1, i - L);
i64 val = -inf;
if (ql <= qr) k = __lg(qr - ql + 1), val = a[i] - min(mn[k][ql], mn[k][qr - (1 << k) + 1]);
if (val > suf) suf = val;
if (suf > ans[i]) ans[i] = suf;
}
if (suf != -inf)
for (int i = jl - 1; i > mid; i--) ans[i] = max(ans[i], suf);
}
}
static void _main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i], a[i] += a[i - 1];
copy(a, a + n + 1, mx[0]), copy(a, a + n + 1, mn[0]);
for (int i = 1; (1 << i) <= n; i++) {
for (int j = 0; j + (1 << i) - 1 <= n; j++) {
mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
}
}
build(1, n), prework();
for (cin >> q; q--; ) {
cin >> L >> R;
for (int i = 1; i <= n; i++) {
int mk = min(R, len[i]);
if (L > mk) {
ans[i] = -inf;
} else {
int k = __lg(mk - L + 1);
ans[i] = max(st[k][L][i], st[k][mk - (1 << k) + 1][i]);
}
}
solve(1, n);
u64 res = 0;
for (int i = 1; i <= n; i++) res ^= (u64)i * (u64)ans[i];
cout << res << '\n';
}
}
:::::
P4948 数列求和
求
S_{n}(k)=\sum_{i=1}^k i^n x^i
:::::success[题解]
考虑用分治来进行求和,按照
- 当
k 为奇数时,有
- 当
k 为偶数时,有
递归求解即可,边界为
注意:偶数情况中
如果使用杨辉三角递推组合数,该做法支持任意模数。
:::::
:::::info[代码]
const int N = 2005;
long long n, k;
mint x, c[N][N];
void prework() {
for (int i = 0; i <= n; i++) c[i][0] = c[i][i] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
vector<mint> solve(long long k) {
if (k == 1) return vector<mint>(n + 1, x);
vector<mint> S(n + 1);
if (k & 1) {
auto T = solve(k - 1);
for (int i = 0; i <= n; i++) {
mint cur = 0;
for (int j = 0; j <= i; j++) cur += c[i][j] * T[j];
S[i] = x + x * cur;
}
return S;
} else {
auto T = solve(k >> 1);
mint p = x.pow(k >> 1);
for (int i = 0; i <= n; i++) {
mint cur = 0, b = k >> 1, pw = 1;
for (int j = i; j >= 0; j--, pw *= b) cur += c[i][j] * T[j] * pw;
S[i] = T[i] + p * cur;
}
return S;
}
}
void _main() {
cin >> k >> x >> n;
prework();
auto S = solve(k);
cout << S[n];
}
:::::
AT_ttpc2022_i XOR Reachable
给你一个
n 个点m 条边的无向图,边带权w_i 。再给定一个k ,回答q 次询问,给出d ,查询仅保留(w_i \oplus d) < k 的边的情况下,可达点对的数目。
:::::success[题解]
先考虑一个暴力,每次询问使用并查集求连通块,设连通块有
这个过程可以用可撤销并查集维护,每次合并时减去原本的贡献,加上新连通块的贡献。撤销做这个操作的逆操作。这启示我们使用线段树分治等方法维护。
线段树分治适合于处理时间轴上连续段的问题,而本题相当于是有关位运算的连续段问题。考虑建立 01-Trie,利用 01-Trie 的结构分治。
从高位向低位建立 01-Trie,将询问的
在当前节点,记录一个边集
- 若
k 的当前位是0 ,则当前位必须为0 。
向左儿子走,则只有E_0 合法;向右儿子走,则只有E_1 合法。 - 若
k 的当前位是1 ,继续讨论:- 若异或结果当前位为
0 ,此时一定合法,直接在并查集中连上所有边。 - 若异或结果当前位为
1 ,此时仍然待定,形成子问题结构,递归分治处理。 - 以左儿子为例,根据上述讨论得到的分治流程如下:
- 对于
E_0 中的边,一定合法,故直接连边。 - 对于
E_1 中的边,递归左儿子处理。 - 递归完成后,将并查集撤销到递归前。
- 对于
- 若异或结果当前位为
这个做法可以被称为 01-Trie 分治。视
:::::
:::::info[代码]
const int N = 1e5 + 5;
using edge = tuple<int, int, int>;
i64 cur, ans[N];
struct unionfind {
int fa[N], sz[N];
static i64 C(i64 x) {return x * (x - 1) / 2;}
stack<int> st;
unionfind() {iota(fa, fa + N, 0), fill(sz, sz + N, 1);}
int find(int x) {return x == fa[x] ? x : find(fa[x]);}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
cur -= C(sz[x]) + C(sz[y]);
fa[x] = y, sz[y] += sz[x], st.emplace(x);
cur += C(sz[y]);
}
void undo(int x) {
while ((int)st.size() > x) {
int u = st.top(), p = fa[u]; st.pop();
if (u == p) continue;
cur -= C(sz[p]);
sz[p] -= sz[u], fa[u] = u;
cur += C(sz[p]) + C(sz[u]);
}
}
} dsu;
int n, m, k, q;
#define ls son[0][u]
#define rs son[1][u]
int cnt = 1, son[2][N << 5];
vector<int> val[N << 5];
void insert(int x, int id) {
int u = 1;
val[u].emplace_back(id);
for (int d = 30; d >= 0; d--) {
if (!son[x >> d & 1][u]) son[x >> d & 1][u] = ++cnt;
u = son[x >> d & 1][u];
val[u].emplace_back(id);
}
}
void solve(int u, int dep, vector<edge>& e) {
if (e.empty() || dep < 0) {
for (int id : val[u]) ans[id] = cur;
return;
}
vector<edge> e0, e1;
for (auto& [u, v, w] : e) {
if (w >> dep & 1) e1.emplace_back(u, v, w);
else e0.emplace_back(u, v, w);
}
if (k >> dep & 1) {
if (ls) {
int step = dsu.st.size();
for (auto& [u, v, w] : e0) dsu.unite(u, v);
solve(ls, dep - 1, e1), dsu.undo(step);
}
if (rs) {
int step = dsu.st.size();
for (auto& [u, v, w] : e1) dsu.unite(u, v);
solve(rs, dep - 1, e0), dsu.undo(step);
}
} else {
if (ls) solve(ls, dep - 1, e0);
if (rs) solve(rs, dep - 1, e1);
}
}
void _main() {
cin >> n >> m >> k;
vector<edge> e;
for (int i = 1, u, v, w; i <= m; i++) {
cin >> u >> v >> w;
e.emplace_back(u, v, w);
}
cin >> q;
for (int i = 1, v; i <= q; i++) cin >> v, insert(v, i);
solve(1, 30, e);
for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
}
:::::