[WC2018] 即时战略

分享一下全局平衡二叉树的做法。

先讲下部分分。

\(n\le 100,T\le 10000\)

从 \(1\) 开始 DFS，对于当前 \(u\)，枚举点 \(v\)，如果 \(\text{explore}(u,v)\) 不为 \(fa_u\)，则 \(v\) 为 \(u\) 子结点，向 \(v\) 拓展即可。询问次数 \(O(n^2)\)，可得 \(20pts\)。

\(\texttt{datatype}=2\)

完全二叉树树高 \(O(\log n)\)，子树大小之和为 \(O(n\log n)\)。给每个点开一个 vector 记录子树结点。对于 \(u\) 遍历子树结点 \(v\) 并询问 \(\text{explore}(u,v)=p\)。将 \(v\) 加入 \(p\) 的子树。最后 DFS 所有出现过的 \(p\) 即可。询问次数 \(O(n\log n)\)，可得 \(35pts\)。

\(\texttt{datatype}=1\)

次数是 \(n+\log n\) 的。当前已访问结点必然是一段链 \([l,r]\)。随机取一个未访问点 \(u\)，询问 \(\text{explore}(l,u)=p\)。如果 \(p\) 已被访问，则不断询问 \(\text{explore}(r,u)\) 拓展链；否则不断询问 \(\text{explore}(l,u)\)。注意更新 \(l,r\)。考虑 “\(p\) 已被访问”发生的次数是期望 \(O(\log n)\) 的。因为期望下 \(r\) 右边的链每次缩短一半。询问次数 \(n+\log n\)，可得 \(65pts\)。

正解

先随机一个 \(u\)，拉出一条 \(1\to u\) 的链。然后再随机一个 \(v\)，在链上二分确定它挂在 \(p\)。然后再拉出一条 \(p\to v\) 的链。这些链的深度都是严格递增的，不难想到重链剖分，这样可以做到 \(O(n\log^2n)\) 的询问次数。问题在于我们无法确定哪个是重儿子。如果你做过 「EZEC-8」猜树 加强版，重子树的点总是比较多，我们随机一个点就可以把它所在的子树当作重子树。

然而我们要做到 \(O(n\log n)\) 的询问次数。考虑优化在链上二分的过程，把它换成全局平衡二叉树就能做到 \(O(n\log n)\) 了。但是老问题又来了，我们不知道每个点的外挂子树大小。没关系，我们无需建出全局平衡二叉树，每次找到带权重心即可。

注意外挂子树大小 \(sz_i\) 的更新相当于每次跳重链并单点修改，每次要查询重链连续的一段 \([l,r]\)，找到第一个位置 \(p\) 满足 \(\sum_{i=l}^psz_i>\frac 12\sum_{i=l}^r sz_i\)，然后选取 \(p\) 为重心。

在每条重链上开一个 fhq treap 即可维护。时间复杂度 \(O(n\log^2n)\)，询问次数 \(O(n\log n)\)，可以通过。

还是比较好写的。细节的注释在代码里：

#include "rts.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ls u<<1
#define rs u<<1|1
#define mid ((l+r)>>1)
#define lp ch[x][0]
#define rp ch[x][1]
int n;
const int N=300005;
mt19937 rd(time(0));
namespace pool{//随机池int tr[4*N];void build(int l,int r,int u){tr[u]=r-l+1-(l==1);if(l==r) return;build(l,mid,ls),build(mid+1,r,rs);}void del(int l,int r,int u,int p){if(l==r) {tr[u]=0;return;}p<=mid?del(l,mid,ls,p):del(mid+1,r,rs,p);tr[u]=tr[ls]+tr[rs];}int kth(int l,int r,int u,int k){if(l==r) return l;if(k<=tr[ls]) return kth(l,mid,ls,k);return kth(mid+1,r,rs,k-tr[ls]);}void bk(int u){del(1,n,1,u);}//删除已访问点int get(){return kth(1,n,1,rd()%tr[1]+1);}//随机一个未访问点
}
namespace ghf{//链int l[N],r[N];void lk(int x,int y){r[x]=y,l[y]=x;}void solve(){int nl=1,nr=1;while(pool::tr[1]){int u=pool::get(),v;if((v=explore(nl,u))==r[nl]){while(nr!=u){v=explore(nr,u),lk(nr,v),nr=v,pool::bk(v);}}else{lk(v,nl),nl=v,pool::bk(v);while(nl!=u) v=explore(nl,u),lk(v,nl),nl=v,pool::bk(v);}}}
}
namespace thy{int fa[N],son[N],top[N],bot[N],goal,dep[N],lst;//fa[u]:父结点，son[u]:重儿子，top[u]:重链链顶，bot[u]:重链链底，goal:随机出来的 u，dep[u]:深度，lst:上一个点int idx,rt[2*N],tr[N],val[N],sz[N],p[N],ch[N][2];//idx:分配临时根，rt[u]:平衡树根结点，tr[u]:平衡树子树外挂子树大小和，val[u]:u 的外挂子树大小，sz[u]:平衡树子树结点数，p[u]:随机优先值，ch[u][0/1]:左右儿子void up(int x){//fhq treaptr[x]=tr[lp]+tr[rp]+val[x];sz[x]=sz[lp]+sz[rp]+1;}int merge(int x,int y){if(!x||!y) return x+y;if(p[x]<p[y]) return rp=merge(rp,y),up(x),x;return ch[y][0]=merge(x,ch[y][0]),up(y),y;}void split(int x,int &l,int &r,int k){//分裂为排名 [1,k],[k+1,n]if(!x){l=r=0;return;}if(sz[lp]+1<=k) l=x,split(rp,rp,r,k-sz[lp]-1);else r=x,split(lp,l,lp,k);up(x);}void add(int x,int k,int w){if(sz[lp]+1<k) add(rp,k-sz[lp]-1,w);else if(k<=sz[lp]) add(lp,k,w);else val[x]+=w;up(x);}int findrt(int x,int k){//找到第一个前缀和 >=k 的点if(k>tr[lp]+val[x]) return findrt(rp,k-(tr[lp]+val[x]));if(k<=tr[lp]) return findrt(lp,k);return x;}int GBT(int u,int up,int dn){//全局平衡二叉树（动态找重心）int g=findrt(rt[u],(tr[rt[u]]+1)/2),to=explore(g,goal),res;//g 为带权重心if(top[to]==u){//仍在重链里if(dep[to]>dep[g]){//往下找split(rt[u],rt[++idx],rt[u],dep[g]-dep[up]+1);res=GBT(u,son[g],dn),rt[u]=merge(rt[idx--],rt[u]);//回溯，把分裂出去的点合并回来}else{//往上找split(rt[u],rt[u],rt[++idx],dep[g]-dep[up]);res=GBT(u,up,fa[g]),rt[u]=merge(rt[u],rt[idx--]);}}else res=to,lst=g;return res;}void upd(int x,int w){//跳重链更新 valwhile(x){add(rt[top[x]],dep[x]-dep[top[x]]+1,w);x=fa[top[x]];}}void solve(){rt[top[1]=bot[1]=1]=1,idx=n;p[1]=rand(),sz[1]=val[1]=tr[1]=1;while(pool::tr[1]){goal=pool::get();int nw=1;while(nw=GBT(nw,nw,bot[nw]),top[nw]);fa[nw]=lst,dep[nw]=dep[lst]+1;val[nw]=tr[nw]=sz[nw]=1,p[nw]=rand(),rt[nw]=nw;if(top[lst]==bot[top[lst]]){//lst 还没有重儿子，把 nw 定为重儿子top[nw]=top[lst],bot[top[nw]]=nw,son[lst]=nw;rt[top[nw]]=merge(rt[top[nw]],rt[nw]);}else top[nw]=bot[nw]=nw;//另开一条重链pool::bk(nw);int w=1;while(nw!=goal){//拉出一条 nw->goal 的链lst=nw,nw=explore(nw,goal),w++,pool::bk(nw);dep[nw]=dep[lst]+1,fa[nw]=lst,son[lst]=nw,top[nw]=top[lst],bot[top[nw]]=nw;val[nw]=tr[nw]=sz[nw]=1,p[nw]=rand(),rt[nw]=nw;rt[top[nw]]=merge(rt[top[nw]],rt[nw]);}upd(fa[top[nw]],w);}}
}
void play(int num, int T, int dataType) {srand(time(0));n=num,pool::build(1,n,1);if(dataType==3) ghf::solve();//链的限制比较紧，特判else thy::solve();
}