[科技] 假装是ETT的ETT

[科技] 假装是ETT的ETT

[科技] 假装是ETT的ETT

Codechef 的 April Challenge 2019 Division 1 的 Sonya and Queries 这题的\(45\)分部分分，似乎是一个出栈入栈序\(ETT\)，看着似乎还挺好的，就写了写。那么这里就讲一讲这个假装是\(ETT\)的\(ETT\)。

\(ETT\)，全称\(Euler-Tour-Tree\)。实际上真实的\(ETT\)是用树上的欧拉回路来写的，但是也有这种省略欧拉回路为入栈出栈序列的\(ETT\)，个人感觉可能后者更容易实现，但是与前者的不同就是似乎后者不能换根，但是可以进行链上操作……如果要学欧拉回路的\(ETT\)的话可以看这个文章。

首先出栈入栈序列，或者叫做括号序这个东西，用处还是挺多的，比较常见的就是用在\(RMQ\ LCA\)的问题上，可以做到\(O(nlogn)\)预处理，\(O(1)\)查询\(LCA\)的优秀复杂度。其主要的性质就是对于每一个点的出栈与入栈时间\(in[x]\)和\(out[x]\)，都有\([in[x], out[x]]\)中所有的节点都是\(x\)的子树中的节点。这个还是比较显然的，这也是\(ETT\)能够在某些地方代替\(LCT\)维护动态树的基础。

于是我们尝试用括号序\(ETT\)实现一些\(LCT\)的操作。

首先是最基础的\(Link / Cut\)：

考虑到\(Link / Cut\)就是把\(x\)的子树和\(x\)的父亲断开或者接到另一个节点\(y\)上，而这个操作在括号序上的表现即是序列上一个连续段的平移。这个操作我们再熟悉不过了，利用平衡树就可以优秀地解决了。

然后是一些基础的子树操作，例如子树加，子树赋值，子树求和，子树求\(Max\)等等：

还是考虑括号序的性质，\(x\)的子树都在\([in[x], out[x]]\)这个区间中，在平衡树中将这个区间分裂出来之后找到根节点，就可以得到区间的信息了，或者打一些子树的标记了。不过需要注意的是，在子树求和的时候，由于区间中的数实际上有\(2 * sz\)个，所以答案应该要除以\(2\)。

还有一写单点的操作也是和子树操作类似的，就不赘述了。但是有一个细节也是和子树求和差不多的，就是单点操作的时候要操作两个点，这点不要忘记。

然后是一些链上的操作：

（注：这里的链上操作，博主似乎都只会那种直接到根节点的操作，并且这种方法似乎不能求链上\(\min, \max\)，如果有什么更为优秀的实现方式，欢迎评论） 考虑括号序的实质是入栈出栈序列，假设我们需要操作是\(x\)到根的一条链，那么我们考虑\([1, out[x]]\)这个区间，如果对于一个节点\(u\)，\(in[u]\)和\(out[u]\)都在这个区间里的话，那么说明这个节点\(u\)并不在需要操作的链上。 以链求和为例，我们就可以在平衡树插入的节点进行一些修改。对于节点\(x\)，我们在\(in[x]\)出插入\(val[x]\)，在\(out[x]\)出插入\(-val[x]\)。那么链求和就是\([1, out[x]]\)中的所有节点的和，这个平衡树也是可以优秀的解决的。唯一不怎么优秀的就是需要开两个平衡树……

这些大概就是一些\(ETT\)能够满足的操作了。可能博主学的并不精，勿喷……

给一道例题吧：例题 代码应该还好写的，就不放出来了……

至于Codechef么……emm……反正比赛也快结束了……\(45\)分的部分分也应该没什么人要的样子啊，我就直接放出来了吧嘿嘿嘿……反正没多少人看……

Code：

用的是\(fhq \ Treap\)来实现的……

大致就是需要支持:\(Link / Cut\)（保证操作的为原树上的边），子树求和，子树赋值，单点加，单点查询，子树加。 还算好写吧……

#include <bits/stdc++.h> using namespace std; const int N = 3E5 + 50; typedef long long ll; typedef pair<int, int> P; typedef vector<int> Vec; #define fi first #define se second #define mk make_pair int n, m, ID, clck; struct edge { int u, v; }E[N << 2]; ll a[N]; Vec G[N], t; int in[N], out[N]; char s[N]; namespace Treap { struct node { int ls, rs, sz, zero, fa; ll v, sum, Rnd, tag; }t[N << 1]; int tot, rt; #define ls(o) t[o].ls #define rs(o) t[o].rs #define pa(o) t[o].fa int Newnode(ll V) { t[++tot].ls = t[tot].rs = t[tot].zero = t[tot].fa = t[tot].tag = 0; t[tot].sz = 1; t[tot].Rnd = 1ll * rand() * rand(); t[tot].sum = t[tot].v = V; return tot; } void Update(int o) { t[o].sz = 1; t[o].sum = t[o].v; t[o].sz += ( ls(o) ? t[ls(o)].sz : 0 ) + ( rs(o) ? t[rs(o)].sz : 0 ); t[o].sum += ( ls(o) ? t[ls(o)].sum : 0) + ( rs(o) ? t[rs(o)].sum : 0 ); } void Apply1(int o) { t[o].sum = t[o].v = 0; t[o].zero = 1; t[o].tag = 0; } void Apply2(int o, ll V) { t[o].sum += t[o].sz * V; t[o].v += V; t[o].tag += V; } void Push(int o) { if(t[o].zero) { if(ls(o)) Apply1(ls(o)); if(rs(o)) Apply1(rs(o)); t[o].zero = 0; } if(t[o].tag) { if(ls(o)) Apply2(ls(o), t[o].tag); if(rs(o)) Apply2(rs(o), t[o].tag); t[o].tag = 0; } } int Merge(int x, int y) { if(!x || !y) return x | y; Push(x); Push(y); if(t[x].Rnd < t[y].Rnd) { int k = Merge(t[x].rs, y); t[k].fa = x; t[x].rs = k; Update(x); return x; } else { int k = Merge(x, t[y].ls); t[k].fa = y; t[y].ls = k; Update(y); return y; } } P Split(int o, int k) { if(!o) return mk(0, 0); Push(o); if(t[ls(o)].sz == k) { int Ls = ls(o); ls(o) = 0; t[Ls].fa = 0; Update(o); return mk(Ls, o); } if(t[ls(o)].sz + 1 == k) { int Rs = rs(o); rs(o) = 0; t[Rs].fa = 0; Update(o); return mk(o, Rs); } if(t[ls(o)].sz < k) { P tmp = Split(rs(o), k - t[ls(o)].sz - 1); int Rs = t[o].rs; t[Rs].fa = 0; t[o].rs = tmp.fi; t[tmp.fi].fa = o; Update(o); return mk(o, tmp.se); } P tmp = Split(ls(o), k); int Ls = t[o].ls; t[Ls].fa = 0; t[o].ls = tmp.se; t[tmp.se].fa = o; Update(o); return mk(tmp.fi, o); } P Findroot(int o) { int las = 0, Rnk = ls(o) ? t[ls(o)].sz : 0; while(pa(o)) { if(rs(pa(o)) == o) Rnk += t[ls(pa(o))].sz + 1; o = pa(o); } return mk(o, Rnk); } void Insert(ll V) { int o = Newnode(V); rt = Merge(rt, o); } void Cut(int x, int y) { int L1 = in[x], R1 = out[x], L2 = in[y], R2 = out[y]; if(L1 <= L2 && R2 <= R1) swap(x, y), swap(L1, L2), swap(R1, R2); P L = Findroot(L1), R = Findroot(R1); P tmp1 = Split(L.fi, R.se + 1); P tmp2 = Split(tmp1.fi, L.se); Merge(tmp2.fi, tmp1.se); } void Link(int x, int y) { int L1 = in[x], R1 = out[x], L2 = in[y], R2 = out[y]; if(L1 <= L2 && R2 <= R1) swap(x, y), swap(L1, L2), swap(R1, R2); int o = Findroot(L1).fi; P R = Findroot(R2); P tmp1 = Split(R.fi, R.se + 1); P tmp2 = Split(tmp1.fi, R.se); int p = Merge(tmp2.fi, o); int k = Merge(p, tmp2.se); Merge(k, tmp1.se); } } void Dfs(int o, int fa) { in[o] = ++clck; t.push_back(o); for(int i = 0; i < (int)G[o].size(); i++) { int to = G[o][i]; if(to == fa) continue; Dfs(to, o); } out[o] = ++clck; t.push_back(o); } int main() { Treap::rt = Treap::tot = 0; scanf("%d%d%d", &ID, &n, &m); if(ID == 4 || ID == 5) return puts("nmdwsm"), 0; for(int i = 1, u, v; i < n; i++) { scanf("%d%d", &u, &v); E[i] = (edge) { u, v }; G[u].push_back(v); G[v].push_back(u); } scanf("%s", s + 1); for(int i = 1; i <= n; i++) scanf("%lld", &a[i]); Dfs(1, 1); for(int i = 0; i < (int)t.size(); i++) Treap::Insert(a[t[i]]); for(int i = 1; i < n; i++) { if(s[i] == '0') continue; Treap::Cut(E[i].u, E[i].v); } while(m--) { int tp; scanf("%d", &tp); if(tp == 1) { int x; scanf("%d", &x); if(s[x] == '0') s[x] = '1', Treap::Cut(E[x].u, E[x].v); else s[x] = '0', Treap::Link(E[x].u, E[x].v); } else if(tp == 2) { int x; ll y; scanf("%d%lld", &x, &y); P p = Treap::Findroot(in[x]); Treap::Apply2(p.fi, y); } else if(tp == 3) { int x; scanf("%d", &x); P p = Treap::Findroot(in[x]); ll Sum = Treap::t[p.fi].sum; Sum >>= 1; Treap::Apply1(p.fi); P tmp1 = Treap::Split(p.fi, p.se + 1); P tmp2 = Treap::Split(tmp1.fi, p.se); Treap::t[tmp2.se].sum = Treap::t[tmp2.se].v = Sum; Treap::Merge(Treap::Merge(tmp2.fi, tmp2.se), tmp1.se); p = Treap::Findroot(out[x]); tmp1 = Treap::Split(p.fi, p.se + 1); tmp2 = Treap::Split(tmp1.fi, p.se); Treap::t[tmp2.se].sum = Treap::t[tmp2.se].v = Sum; Treap::Merge(Treap::Merge(tmp2.fi, tmp2.se), tmp1.se); } else if(tp == 4) { int x; scanf("%d", &x); P p = Treap::Findroot(in[x]); P tmp1 = Treap::Split(p.fi, p.se + 1); P tmp2 = Treap::Split(tmp1.fi, p.se); ll ans = Treap::t[tmp2.se].v; printf("%lld\n", ans); Treap::Merge(Treap::Merge(tmp2.fi, tmp2.se), tmp1.se); } else if(tp == 5) { int x; scanf("%d", &x); P p = Treap::Findroot(in[x]); ll ans = Treap::t[p.fi].sum; ans >>= 1; printf("%lld\n", ans); } else if(tp == 6) { int x; scanf("%d", &x); P p = Treap::Findroot(in[x]); Treap::Apply1(p.fi); } } return 0; }

转载于:https://www.cnblogs.com/Apocrypha/p/10701713.html

相关资源：JAVA上百实例源码以及开源项目