Query on a tree V VI VII [LCT]

Query on a tree V VI VII [LCT]

QTREE5

操作 : 反转某个点的颜色, 查询某个点的最近白点

我们维护Splay中, 最浅节点到最近白点的距离(lsum), 以及最深节点到它的最近白点的距离(rsum)

那么查询x的答案很明显 Accss(x), Splay(x), x -> rsum 就是答案

考虑如何 Pushup

Minson是虚子树答案, 用一个set维护

#include#define N 100050using namespace std;int read(){ int cnt = 0; char ch = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return cnt;}const int inf = 0x3fffffff;vector v[N];int n, m, col[N];int ch[N][2], fa[N], siz[N], lsum[N], rsum[N];multiset S[N]; void dfs(int u, int f){ for(int i=0; iroot(int x){ return ch[fa[x]][0] != x && ch[fa[x]][1] != x;}int Top(int x){ if(S[x].empty()) return inf; return *S[x].begin();}void Pushup(int x){ if(!x) return; lsum[x] = rsum[x] = inf; siz[x] = siz[ls] + siz[rs] + 1; lsum[x] = min(lsum[ls], siz[ls] + min(col[x] ? 0 : inf, min(Top(x), lsum[rs] + 1))); rsum[x] = min(rsum[rs], siz[rs] + min(col[x] ? 0 : inf, min(Top(x), rsum[ls] + 1)));}void rotate(int x){ int y = fa[x], z = fa[y], k = ch[y][1] == x; if(!isRoot(y)) ch[z][ch[z][1] == y] = x; fa[x] = z; ch[y][k] = ch[x][k^1]; fa[ch[x][k^1]] = y; ch[x][k^1] = y; fa[y] = x; Pushup(y); Pushup(x);}void Splay(int x){ while(!isRoot(x)){ int y = fa[x], z = fa[y]; if(!isRoot(y)) rotate((ch[y][0] == x) ^ (ch[z][0] == y) ? x : y); rotate(x); }}void Access(int x){ for(int y = 0; x; y = x, x = fa[x]){ Splay(x); if(rs) S[x].insert(lsum[rs] + 1); rs = y; if(rs) S[x].erase(S[x].find(lsum[rs] + 1)); Pushup(x); }}int main(){ n = read(); lsum[0] = rsum[0] = inf; for(int i=1; i

QTREE6

操作 : 反转颜色, 查询同色连通块的大小

首先开两颗LCT, 反转颜色相当于在一边暴力 Cut, 一边暴力Link

我们考虑只Cut x与它的fa, 也之Link x与它的fa, 这样一个连通块只有可能 rt与其颜色不同, 特判一下就好

然后就是维护虚子树的Siz

#include#define N 1000050using namespace std;int read(){ int cnt = 0; char ch = 0; while(!isdigit(ch)) ch = getchar(); while(isdigit(ch)) cnt = cnt*10 + (ch-'0'), ch = getchar(); return 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 n, m, col[N];struct LCT{ struct Node{ int ch[2], fa, siz; } t[N]; int si[N]; #define ls t[x].ch[0] #define rs t[x].ch[1] bool isRoot(int x){ int fa = t[x].fa; return t[fa].ch[0] != x && t[fa].ch[1] != x; } void Pushup(int x){ t[x].siz = t[ls].siz + t[rs].siz + si[x] + 1;} void rotate(int x){ int y = t[x].fa, z = t[y].fa, k = t[y].ch[1] == x; if(!isRoot(y)) t[z].ch[t[z].ch[1] == y] = x; t[x].fa = z; t[y].ch[k] = t[x].ch[k^1]; t[t[x].ch[k^1]].fa = y; t[x].ch[k^1] = y; t[y].fa = x; Pushup(y); Pushup(x); } void Splay(int x){ while(!isRoot(x)){ int y = t[x].fa, z = t[y].fa; if(!isRoot(y)) rotate((t[y].ch[0] == x) ^ (t[z].ch[0] == y) ? x : y); rotate(x); } Pushup(x); } void Access(int x){ for(int y=0; x; y=x, x=t[x].fa){ Splay(x); si[x] += t[rs].siz; rs = y; si[x] -= t[rs].siz; Pushup(x); } } void Link(int x, int y){ if(!y) return; Access(y); Splay(y); Splay(x); t[x].fa = y; si[y] += t[x].siz; Pushup(y); } void Cut(int x, int y){ if(!y) return; Access(x); Splay(x); t[ls].fa = 0; ls = 0; Pushup(x); } int Findroot(int x){ Access(x); Splay(x); while(ls) x = ls; Splay(x); return x; } int Quary(int x){ int c = col[x]; x = Findroot(x); return col[x] == c ? t[x].siz : t[rs].siz; }}lct[2]; int fa[N];void dfs(int u, int f){ for(int i=first[u];i;i=nxt[i]){ int t = to[i]; if(t == f) continue; fa[t] = u; lct[0].Link(t, u); dfs(t, u); }}int main(){ n = read(); for(int i=1; i

QTREE7

与上一道题类似, 维护同色连通块的最大值, multiset就可以了

#include#define N 200050using 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 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, col[N], f[N], w[N];struct Node{ int ch[N][2], fa[N], Max[N]; multiset S[N]; bool isRoot(int x){ return ch[fa[x]][0] != x && ch[fa[x]][1] != x;} void Pushup(int x){ Max[x] = max(w[x], max(Max[ch[x][0]], Max[ch[x][1]])); if(S[x].size()) Max[x] = max(Max[x], *S[x].rbegin()); } void rotate(int x){ int y = fa[x], z = fa[y], k = ch[y][1] == x; if(!isRoot(y)) ch[z][ch[z][1] == y] = x; fa[x] = z; ch[y][k] = ch[x][k^1]; fa[ch[x][k^1]] = y; ch[x][k^1] = y; fa[y] = x; Pushup(y); Pushup(x); } void Splay(int x){ while(!isRoot(x)){ int y = fa[x], z = fa[y]; if(!isRoot(y)) rotate((ch[y][1]==x) ^ (ch[z][1]==y) ? x : y); rotate(x); } Pushup(x); } void Access(int x){ for(int y = 0; x; y = x, x = fa[x]){ Splay(x); if(ch[x][1]) S[x].insert(Max[ch[x][1]]); ch[x][1] = y; if(ch[x][1]) S[x].erase(Max[ch[x][1]]); Pushup(x); } } int Findroot(int x){ Access(x); Splay(x); while(ch[x][0]) x = ch[x][0]; Splay(x); return x; } void Link(int x, int y){ if(!y) return; Access(y); Splay(y); Splay(x); fa[x] = y; S[y].insert(Max[x]); Pushup(y); } void Cut(int x, int y){ if(!y) return; Access(x); Splay(x); fa[ch[x][0]] = 0; ch[x][0] = 0; Pushup(x); } int Quary(int x){ int c = col[x]; x = Findroot(x); return col[x] == c ? Max[x] : Max[ch[x][1]]; } void Modify(int x){ Access(x); Splay(x); w[x] = read(); Pushup(x); }}T[2];void dfs(int u, int ff){ for(int i=first[u];i;i=nxt[i]){ int t = to[i]; if(t == ff) continue; T[col[t]].Link(t, u); f[t] = u; dfs(t, u); }}int main(){ n = read(); for(int i=1; i

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