暑假集训 ---- (树上)数据结构

暑假集训 ---- (树上)数据结构

​​ZJOI 2007 捉迷藏 ​​​

一棵树，点权为 0/1，每次修改一个点的点权，询问两个最远的 1 的距离 点分树每个点维护：到当前节点的最远距离，维护最大和次大拼起来的，和一个全局最大的

#include#define N 200050#define inf 0x3fffffffusing namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f;}int n, q, a[N], cnt;int first[N], nxt[N], to[N], tot;void add(int x, int y){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y;}int father[N]; // 点分树int fa[N][20], dep[N];int Siz, rt, Maxson[N], siz[N], vis[N];struct Node{ priority_queue q1, q2; void Push(int x){ q1.push(x); } void Delete(int x){ q2.push(x); } int Top(){ while(q2.size() && q1-() == q2-()) q1.pop(), q2.pop(); return q1-(); } void Pop(){ while(q2.size() && q1-() == q2-()) q1.pop(), q2.pop(); q1.pop(); } int Top2(){ int val = Top(); Pop(); int ret = Top(); Push(val); return ret;} int Siz(){ return q1.size() - q2.size();}}h1[N], h2[N], h3;void dfs(int u, int f){ for(int i=1; i<=18; i++) fa[u][i] = fa[fa[u][i-1]][i-1]; for(int i=first[u];i;i=nxt[i]){ int t = to[i]; if(t == f) continue; dep[t] = dep[u] + 1; fa[t][0] = u; dfs(t, u); }}void getrt(int u, int f){ siz[u] = 1; Maxson[u] = 0; for(int i=first[u];i;i=nxt[i]){ int t = to[i]; if(t == f || vis[t]) continue; getrt(t, u); siz[u] += siz[t]; Maxson[u] = max(Maxson[u], siz[t]); } Maxson[u] = max(Maxson[u], Siz - Maxson[u]); if(Maxson[u] < Maxson[rt]) rt = u;}int lca(int x, int y){ if(dep[x] < dep[y]) swap(x, y); for(int i=18; i>=0; i--) if(dep[fa[x][i]] >= dep[y]) x = fa[x][i]; if(x == y) return x; for(int i=18; i>=0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return fa[x][0];}int Dis(int x, int y){ return dep[x] + dep[y] - 2 * dep[lca(x, y)];}void dfs2(int u, int fa, int goal){ h1[rt].Push(Dis(u, goal)); for(int i=first[u];i;i=nxt[i]){ int t = to[i]; if(t == fa || vis[t]) continue; dfs2(t, u, goal); }}void Divide(int u, int fa){ father[u] = fa; vis[u] = 1; h2[u].Push(0); int sum = Siz; for(int i=first[u];i;i=nxt[i]){ int t = to[i]; if(vis[t]) continue; if(siz[t] > siz[u]) Siz = sum - siz[u]; else Siz = siz[t]; rt = 0; getrt(t, 0); dfs2(rt, 0, u); h2[u].Push(h1[rt].Top()); Divide(rt, u); } if(h2[u].Siz() > 1) h3.Push(h2[u].Top() + h2[u].Top2());}void off(int x){ if(h2[x].Siz() > 1) h3.Delete(h2[x].Top() + h2[x].Top2()); h2[x].Delete(0); if(h2[x].Siz() > 1) h3.Push(h2[x].Top() + h2[x].Top2()); #define fa father[u] for(int u = x; fa; u = fa){ if(h2[fa].Siz() > 1) h3.Delete(h2[fa].Top() + h2[fa].Top2()); h2[fa].Delete(h1[u].Top()); h1[u].Delete(Dis(x, fa)); if(h1[u].Siz()) h2[fa].Push(h1[u].Top()); if(h2[fa].Siz() > 1) h3.Push(h2[fa].Top() + h2[fa].Top2()); } }void on(int x){ if(h2[x].Siz() > 1) h3.Delete(h2[x].Top() + h2[x].Top2()); h2[x].Push(0); if(h2[x].Siz() > 1) h3.Push(h2[x].Top() + h2[x].Top2()); for(int u = x; fa; u = fa){ if(h2[fa].Siz() > 1) h3.Delete(h2[fa].Top() + h2[fa].Top2()); if(h1[u].Siz()) h2[fa].Delete(h1[u].Top()); h1[u].Push(Dis(x, fa)); h2[fa].Push(h1[u].Top()); if(h2[fa].Siz() > 1) h3.Push(h2[fa].Top() + h2[fa].Top2()); } #undef fa}int main(){ cnt = n = read(); for(int i=1; i

​​BZOJ 2566 xmastree​​​

#include#define N 500050using namespace std;int first[N], nxt[N], to[N], tot;void add(int x, int y){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y;}int n, m, val[N];struct vec{ vector v; int s; void init(){ v.assign(s+10, 0);} void update(int x, int val){ x++; for(;x<=s;x+=x&-x) v[x]+=val; } int Ask(int x){ x++; x = min(x, s); int res = 0; for(;x>=1;x-=x&-x) res += v[x]; return res; }}f1[N], f2[N];int st[N][22], sign, id[N], dis[N], lg[N];void dfs(int u, int f){ st[++sign][0] = dis[u]; id[u] = sign; for(int i=first[u];i;i=nxt[i]){ int t = to[i]; if(t == f) continue; dis[t] = dis[u] + 1; dfs(t, u); st[++sign][0] = dis[u]; }}int siz[N], Maxson[N], rt, Siz, vis[N];void getrt(int u, int f){ siz[u] = 1; Maxson[u] = 0; for(int i=first[u];i;i=nxt[i]){ int t = to[i]; if(t == f || vis[t]) continue; getrt(t, u); siz[u] += siz[t]; Maxson[u] = max(Maxson[u], siz[t]); } Maxson[u] = max(Maxson[u], Siz - siz[u]); if(Maxson[u] < Maxson[rt]) rt = u;}int fa[N], dep[N], d[N], res;int dist(int u, int v){ int x = id[u], y = id[v]; if(x > y) swap(x, y); int t = lg[y - x + 1]; return dis[u] + dis[v] - 2 * min(st[x][t], st[y-(1< siz[u]) Siz = sum - siz[u]; else Siz = siz[t]; rt = 0; getrt(t, 0); dep[t] = 1; getdis(t, 0); calc(f2[rt]); dep[t] = 0; Divide(rt, u); }}int ans;int Qu(int x, int k){ int res = 0; for(int i=x; i; i = fa[i]){ res += f1[i].Ask(k - dist(i, x)); } for(int i=x; fa[i]; i = fa[i]){ res -= f2[i].Ask(k - dist(fa[i], x)); } return res;}void Modify(int x, int k){ for(int i=x; i; i = fa[i]){ f1[i].update(dist(x, i), k); } for(int i=x; fa[i]; i = fa[i]){ f2[i].update(dist(fa[i], x), k); }}int main(){ scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) scanf("%d", &val[i]); for(int i=1; i>1] + 1; for(int i=1; (1<

​​[ZJOI2015]幻想乡战略游戏​​​

#include#define N 200050using namespace std;typedef long long ll;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt * f;}int n, m;int first[N], nxt[N], to[N], w[N], tot;void add(int x, int y,int z){ nxt[++tot] = first[x], first[x] = tot; to[tot] = y; w[tot] = z;}ll dis[N], st[N][22]; int lg[N], sign, id[N];int Siz, siz[N], Maxson[N], rt; void dfs(int u, int f){ st[++sign][0] = dis[u]; id[u] = sign; for(int i=first[u];i;i=nxt[i]){ int t = to[i]; if(t == f) continue; dis[t] = dis[u] + (ll)w[i]; dfs(t, u); st[++sign][0] = dis[u]; }}int vis[N];ll getdis(int u, int v){ int x = id[u], y = id[v]; if(x > y) swap(x, y); int t = lg[y-x+1]; return dis[u] + dis[v] - 2 * min(st[x][t], st[y-(1< >son[N];#define mp make_pair void Divide(int u, int f){ fa[u] = f; vis[u] = 1; int sum = Siz; for(int i=first[u];i;i=nxt[i]){ int t = to[i]; if(vis[t]) continue; if(siz[t] > siz[u]) Siz = sum - siz[u]; else Siz = siz[t]; rt = 0; getrt(t, 0); son[u].push_back(mp(t, rt)); Divide(rt, u); }}void update(int u, ll k){ sum[u] += k; for(int i=u; fa[i]; i = fa[i]){ ll d = getdis(fa[i], u); dis2[i] += k * d; dis1[fa[i]] += k * d; sum[fa[i]] += k; }}ll calc(int u){ ll res = dis1[u]; for(int i=u; fa[i]; i = fa[i]){ ll d = getdis(u, fa[i]); res += dis1[fa[i]] - dis2[i]; res += d * (sum[fa[i]] - sum[i]); } return res;}ll query(int u){ ll ans = calc(u); for(int i=0; i>1] + 1; for(int i=1; (1<

​​[Ynoi2011]D1T3​​​

#include#define N 100050using namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = (cnt << 1) + (cnt << 3) + (ch-'0'), ch = getchar(); return cnt * f;}int n, m, c[N], exi[N];int first[N], nxt[N<<1], to[N<<1], tot;void add(int x, int y){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y;}struct node{ int id, l, r, op; node(int a=0, int b=0, int c=0, int d=0){ id = a; l = b; r = c; op = d;} bool operator < (const node &a) const{ return r < a.r || (r == a.r && op < a.op); }} q[N]; int res, ans[N];int siz[N], mxson[N], rt, Siz, vis[N];void getrt(int u, int fa){ siz[u] = 1; mxson[u] = 0; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa || vis[t]) continue; getrt(t, u); siz[u] += siz[t]; mxson[u] = max(mxson[u], siz[t]); } mxson[u] = max(mxson[u], Siz - siz[u]); if(mxson[u] < mxson[rt]) rt = u;} vector v[N];void dfs(int rot, int u, int fa, int mi, int mx){ mi = min(mi, u); mx = max(mx, u); v[rot].push_back(node(c[u], mi, mx, 0)); for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa || vis[t]) continue; dfs(rot, t, u, mi, mx); }}#define pa pair#define mp make_pairvector dat[N];vector fa[N];void dfs1(int u, int f, int mi, int mx, int rot){ mi = min(mi, u); mx = max(mx, u); dat[u].push_back(mp(mi, mx));// cout< siz[u]) Siz = sz - siz[u]; else Siz = siz[t]; rt = 0; getrt(t, u); dfs1(t, 0, u, u, u); Solve(rt); } }struct BIT{ int c[N]; void Add(int x, int v){ for(;x;x-=x&-x) c[x] += v;} int Ask(int x){ int ans = 0; for(;x<=n;x+=x&-x) ans += c[x]; return ans;}}Bit;int main(){ n = read(), m = read(); for(int i = 1; i <= n; i++) c[i] = read(); for(int i = 1; i < n; i++){ int x = read(), y = read(); add(x, y); add(y, x); } rt = 0; mxson[0] = n+1; Siz = n; getrt(1, 0); Solve(rt); for(int i = 1; i <= m; i++){ int l = read(), r = read(), x = read(); for(int j = 0; j < fa[x].size(); j++){ if(dat[x][j].first >= l && dat[x][j].second <= r){ x = fa[x][j];} } v[x].push_back(node(i, l, r, 1)); } for(int x = 1; x <= n; x++){ sort(v[x].begin(), v[x].end()); for(int i = 0; i < v[x].size(); i++){ if(!v[x][i].op){ if(exi[v[x][i].id] < v[x][i].l){ if(exi[v[x][i].id]) Bit.Add(exi[v[x][i].id], -1); Bit.Add(v[x][i].l, 1); exi[v[x][i].id] = v[x][i].l; } } else ans[v[x][i].id] = Bit.Ask(v[x][i].l); } for(int i = 0; i < v[x].size(); i++){ if(!v[x][i].op){ if(exi[v[x][i].id]) Bit.Add(exi[v[x][i].id], -1), exi[v[x][i].id] = 0; } } v[x].clear(); } for(int i = 1; i <= m; i++) cout << ans[i] << "\n"; return 0;}

#include#define N 1200050using namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = (cnt << 1) + (cnt << 3) + (ch-'0'), ch = getchar(); return cnt * f;}int n, m;int first[N], nxt[N<<1], to[N<<1], tot;void add(int x, int y){ nxt[++tot] = first[x], first[x] = tot, to[tot] = y;}int a[N];int c[N];void Add(int x, int v){ for(;x<=n;x+=x&-x) c[x] += v;}int Ask(int x){ int ans = 0; for(;x;x-=x&-x) ans += c[x]; return ans;}int dep[N], fa[N], top[N], siz[N], son[N], id[N], sign;int rnd(){ return (rand() << 15) | rand();}struct Treap{ int ch[2], siz, val, rnd, cnt;}t[N];#define ls t[x].ch[0]#define rs t[x].ch[1]int rt[N], node;stack bin;int newnode(int v){ int now = 0; if(bin.size()) now = bin-(), bin.pop(); else now = ++node; t[now].ch[0] = t[now].ch[1] = 0; t[now].siz = t[now]-t = 1; t[now].val = v; t[now].rnd = rnd(); return now;}void pushup(int x){ t[x].siz = t[ls].siz + t[rs].siz + t[x]-t;}void Lrot(int &x){ int y = ls; ls = t[y].ch[1]; t[y].ch[1] = x; t[y].siz = t[x].siz; pushup(x); x = y;}void Rrot(int &x){ int y = rs; rs = t[y].ch[0]; t[y].ch[0] = x; t[y].siz = t[x].siz; pushup(x); x = y;}void Insert(int &x, int v){ if(!x){ x = newnode(v); return;} t[x].siz++; if(v == t[x].val){ t[x]-t++; return;} if(v < t[x].val){ Insert(ls, v); if(t[ls].rnd < t[x].rnd) Lrot(x);} if(v > t[x].val){ Insert(rs, v); if(t[rs].rnd < t[x].rnd) Rrot(x);}}void Delete(int &x, int v){ if(!x) return; if(v == t[x].val){ if(t[x]-t > 1){ t[x]-t--; t[x].siz--; return;} if(!ls || !rs) bin.push(x), x = ls + rs; else{ if(t[ls].rnd < t[rs].rnd) Lrot(x); else Rrot(x); Delete(x, v);} return; } t[x].siz--; if(v < t[x].val) Delete(ls, v); else Delete(rs, v);}int Rank(int x, int k){ if(t[ls].siz >= k) return Rank(ls, k); if(t[ls].siz + t[x]-t < k) return Rank(rs, k - t[ls].siz - t[x]-t); return t[x].val;}void dfs1(int u, int f){ siz[u] = 1; for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == f) continue; fa[t] = u; dep[t] = dep[u] + 1; dfs1(t, u); siz[u] += siz[t]; if(siz[t] > siz[son[u]]) son[u] = t; }}void dfs2(int u, int Top){ top[u] = Top; id[u] = ++sign; Add(sign, a[u]); Add(sign+1, -a[u]); if(son[u]) dfs2(son[u], Top); for(int i = first[u]; i; i = nxt[i]){ int t = to[i]; if(t == fa[u] || t == son[u]) continue; Insert(rt[u], a[t]); dfs2(t, t); } }void change(int x, int v){ if(!fa[x]) return; int pre = Ask(id[x]); Delete(rt[fa[x]], pre); Insert(rt[fa[x]], pre + v);}void modify(int x, int y, int v){ while(top[x] != top[y]){ if(dep[top[x]] < dep[top[y]]) swap(x, y); change(top[x], v); Add(id[top[x]], v); Add(id[x]+1, -v); x = fa[top[x]]; } if(id[x] > id[y]) swap(x, y); if(top[x] == x) change(x, v); Add(id[x], v); Add(id[y]+1, -v);}int tmp[10];int main(){ srand(time(0)); srand(rand()); n = read(), m = read(); for(int i = 1; i <= n; i++) a[i] = read(); for(int i = 1; i < n; i++){ int x = read(), y = read(); add(x, y); add(y, x); } dep[1] = 1; dfs1(1, 0); dfs2(1, 1); while(m--){ int op = read(), x = read(), y = read(); if(op == 1){ int v = read(); modify(x, y, v);} if(op == 2){ int ret = 0; if(y <= t[rt[x]].siz)tmp[++ret] = Rank(rt[x], y); if(y > 1 && y-1 <= t[rt[x]].siz) tmp[++ret] = Rank(rt[x], y-1); if(y > 2 && y-2 <= t[rt[x]].siz) tmp[++ret] = Rank(rt[x], y-2); if(y > 3 && y-3 <= t[rt[x]].siz) tmp[++ret] = Rank(rt[x], y-3); tmp[++ret] = Ask(id[x]); if(fa[x]) tmp[++ret] = Ask(id[fa[x]]); if(son[x]) tmp[++ret] = Ask(id[son[x]]); sort(tmp+1, tmp+ret+1); if(y <= 3) cout << tmp[y] << "\n"; else cout << tmp[4] << "\n"; } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。