Codeforces 696E ...Wait for it...(树链剖分)

题目链接  ...Wait for it...

考虑树链剖分。

对于树上的每个点开一个set,记录当前该节点上所有的girls。

每个节点初始的权值为set中的最小值。

询问的时候每次在路径上寻找最小值,并返回这个点的编号。

然后把这个点的set的第一个元素取出,换成下一个元素。

因为女孩总数不超过1e5,所以总查询次数不会超过1e5

修改操作用lazy标记就可以了。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define lson i << 1, L, mid
#define rson i << 1 | 1, mid + 1, R
#define ls i << 1
#define rs i << 1 | 1
#define MP make_pair
#define fi first
#define se second typedef long long LL;
typedef pair <LL, int> PII; const int N = 1e5 + 10;
const LL inf = 1e18; int n, m, q;
int id, cnt = 0;
int ret[N];
int at[N], sz[N], son[N], top[N], f[N], in[N], out[N], deep[N], father[N];
vector <int> v[N];
set <PII> s[N];
LL lazy[N << 2];
PII t[N << 2]; void dfs(int x, int fa, int dep){
sz[x] = 1;
son[x] = 0;
father[x] = fa;
deep[x] = dep;
for (auto u : v[x]){
if (u == fa) continue;
dfs(u, x, dep + 1);
sz[x] += sz[u];
if (sz[son[x]] < sz[u]) son[x] = u;
}
} void dfs2(int x, int tp){
top[x] = tp;
in[x] = f[x] = ++id;
if (son[x]) dfs2(son[x], tp);
for (auto u : v[x]){
if (u == father[x] || u == son[x]) continue;
dfs2(u, u);
}
out[x] = id;
} void pushup(int i){
t[i] = min(t[ls], t[rs]);
} void pushdown(int i){
if (lazy[i]){
lazy[ls] += lazy[i];
lazy[rs] += lazy[i];
t[ls].fi += lazy[i];
t[rs].fi += lazy[i];
lazy[i] = 0;
}
} void build(int i, int L, int R){
lazy[i] = 0;
if (L == R){
t[i] = *s[L].begin();
return;
} int mid = (L + R) >> 1;
build(lson);
build(rson);
pushup(i);
} void update(int i, int L , int R , int l, int r, LL val){
if (l <= L && R <= r){
lazy[i] += val;
t[i].fi += val;
return;
} pushdown(i);
int mid = (L + R) >> 1 ;
if (l <= mid) update(lson, l, r, val);
if (r > mid) update(rson, l, r, val);
pushup(i);
} void modify(int i, int L, int R, int x){
if (L == R){
s[L].erase(s[L].begin());
t[i] = *s[L].begin();
t[i].fi += lazy[i];
return;
}
pushdown(i);
int mid = (L + R) >> 1 ;
if (x <= mid) modify(lson, x) ;
else modify(rson, x);
pushup(i);
} PII query(int i, int L, int R, int l, int r){
if (l <= L && R <= r) return t[i];
pushdown(i);
int mid = (L + R) >> 1 ;
if (r <= mid) return query(lson, l, r);
if (l > mid) return query(rson, l, r);
return min(query(lson, l, r), query(rson, l, r));
} int Query(int x, int y){
PII ans = PII(inf, 0);
while (top[x] ^ top[y]){
if (deep[top[x]] < deep[top[y]]) swap(x, y);
ans = min(ans, query(1, 1, n, f[top[x]], f[x]));
x = father[top[x]];
}
if (deep[x] > deep[y]) swap(x, y);
ans = min(ans, query(1, 1, n, f[x], f[y]));
return ans.se;
} int main(){ scanf("%d%d%d", &n, &m, &q);
rep(i, 2, n){
int x, y;
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
} dfs(1, 0, 0);
dfs2(1, 1); rep(i, 1, n) s[i].insert(MP(inf, 0));
at[0] = N - 1; rep(i, 1, m){
int x;
scanf("%d", &x);
at[i] = x;
s[f[x]].insert(MP(i, i));
} build(1, 1, n); while (q--){
int op, x, y, lim;
LL val;
scanf("%d", &op);
if (op == 2){
scanf("%d%lld", &x, &val);
update(1, 1, n, in[x], out[x], val);
}
else{
scanf("%d%d%d", &x, &y, &lim);
cnt = 0;
while (lim--){
int idx = Query(x, y);
if (idx == 0) break;
ret[++cnt] = idx;
modify(1, 1, n, f[at[idx]]);
}
printf("%d", cnt);
rep(i, 1, cnt) printf(" %d", ret[i]);
putchar(10);
}
} return 0;
}
上一篇:Java Socket通信代码片


下一篇:【Codeforces】【网络流】【树链剖分】【线段树】ALT (CodeForces - 786E)