那个……令姐……能以成亲为前提……和我交往吗(娇羞)
集训完刚好开方舟春活,并且我刚好攒够了给令姐买衣服的石头,这真的是巧合吗?
思路
各种做法,但是有强化版。
首先是 naive 的线段树合并维护深度做法。
然后可以考虑主席树。正常来说距离不超过 \(k\) 的子树问题,是以 dfs 序为时间轴,以深度为下标建主席树。
但是取最小值不具有可减性,所以以深度为时间轴,以 dfs 序为下标建主席树,这样只需要在某个版本的主席上查询一段连续区间的最小值即可。
当然还有诡异的树套树做法,但是我不是很懂,有懂哥可以教一下。
强化版 BZOJ#4771:维护子树内不同颜色的出现次数。
这里有一个虚树差分 + 主席树的 \(O(n \log n)\) 做法。
树链的并:对于 \(k\) 个树上的不同结点 \(a_1, ..., a_n\),
考虑覆盖根到每一个结点的路径。那么可以先把 \(a\) 按照 dfs 序排序,然后将 \(a_i\) 到 \(\operatorname{lca}(a_i, a_{i + 1})\) 之间的路径加一。
虚树差分:对于树链的并中每个结点权值加一。
考虑对 \(a\) 建立出虚树,然后考虑将虚树上每个点的权值赋为 \(1\),按 dfs 序排序后将 \(\operatorname{lca}(a_i, a_{i + 1})\) 的点权减一,最后查询子树和。
回到原题。对于每种颜色的结点,贡献实际上就是一个树链并。
考虑用虚树差分维护。用类似弱化版的主席树维护一下深度。
这里每种颜色的贡献是动态的,不能直接虚树差分。可以用一个 set
维护单种颜色的结点中 dfs 序的前驱后继,这样就可以动态维护了。
代码懒得写了,网上一搜都是。
代码
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 1e5 + 5;
const int t_sz = maxn * 40;
const int inf = 0x3f3f3f3f;
inline int min(const int &a, const int &b) { return (a <= b ? a : b); }
inline int read()
{
int res = 0;
char ch = getchar();
while ((ch < '0') || (ch > '9')) ch = getchar();
while ((ch >= '0') && (ch <= '9'))
{
res = res * 10 + ch - '0';
ch = getchar();
}
return res;
}
inline void write(int x)
{
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
namespace PST
{
int cnt = 0;
int ls[t_sz], rs[t_sz], val[t_sz];
inline void push_up(int k) { val[k] = min(val[ls[k]], val[rs[k]]); }
inline int build(int l, int r)
{
int k = ++cnt;
val[k] = inf;
if (l == r) return k;
int mid = (l + r) >> 1;
ls[k] = build(l, mid);
rs[k] = build(mid + 1, r);
return k;
}
inline int update(int pre, int l, int r, int p, int w)
{
int k = ++cnt;
ls[k] = ls[pre], rs[k] = rs[pre], val[k] = min(val[pre], w);
if (l == r) return k;
int mid = (l + r) >> 1;
if (p <= mid) ls[k] = update(ls[pre], l, mid, p, w);
else rs[k] = update(rs[pre], mid + 1, r, p, w);
return k;
}
inline int query(int k, int l, int r, int ql, int qr)
{
if ((l >= ql) && (r <= qr)) return val[k];
int mid = (l + r) >> 1, res = inf;
if (ql <= mid) res = min(res, query(ls[k], l, mid, ql, qr));
if (qr > mid) res = min(res, query(rs[k], mid + 1, r, ql, qr));
return res;
}
}
struct item
{
int p, w;
} ;
int n, m, root, cnt;
int dep[maxn], dfn[maxn], w[maxn], rt[maxn], sz[maxn];
vector<int> g[maxn];
vector<item> nd[maxn];
void dfs(int u, int fa)
{
dep[u] = dep[fa] + 1;
dfn[u] = ++cnt;
sz[u] = 1;
for (int v : g[u])
{
if (v == fa) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
int main()
{
int last_ans = 0;
n = read(), root = read();
for (int i = 1; i <= n; i++) w[i] = read();
for (int i = 1, u, v; i <= n - 1; i++)
{
u = read(), v = read();
g[u].push_back(v), g[v].push_back(u);
}
dfs(root, 0);
for (int i = 1; i <= n; i++) nd[dep[i]].push_back((item){dfn[i], w[i]});
rt[0] = PST::build(1, n);
for (int i = 1; i <= n; i++)
{
rt[i] = rt[i - 1];
for (item it : nd[i]) rt[i] = PST::update(rt[i], 1, n, it.p, it.w);
}
m = read();
while (m--)
{
int x, k;
x = read(), k = read();
x = (x + last_ans) % n + 1, k = (k + last_ans) % n;
write(last_ans = PST::query(rt[min(dep[x] + k, n)], 1, n, dfn[x], dfn[x] + sz[x] - 1));
putchar('\n');
}
return 0;
}
标签:sz,CF893F,val,int,题解,mid,dfs,Minimum,maxn
From: https://www.cnblogs.com/lingspace/p/cf893f.html