[LibreOJ #2341]【WC2018】即时战略【交互】【LCT】

Description

有一棵n个点的结构未知的树，初始时只有1号点是已被访问的。

你可以调用交互库的询问函数explore(x,y)，其中x是已访问的点，y是任意点。
它会返回x向y方向走第一步的点，如果该点未被访问，则将其标记为已访问。

你需要实现一个函数，它通过接口得到n和T，需要在T次explore操作内将所有的点标记（也就是说走完这棵树）。
要求最严格的两档数据：
n<=300000,T<=300020，且原树为一条链（1号点不一定是端点）。

n<=300000,T<=5000000

Solution

显然我们要将链的情况分开讨论
考虑这样一个做法，我们将编号随机排列，每次找到排列中第一个尚未被访问的点，从当前所在的链端开始explore，若走到的点是未访问的说明这个点就在这一侧，直接一直扩展到目标点。否则说明这个点在链的另一侧，跳到链的另一端一直扩展到目标点。

这样的出错（即链两边跳）的期望次数是\(\log n\)的
大概是因为每次期望都会消掉某一条链的一半这样。

考虑一棵树怎么做。
我们用一个LCT来维护已经扩展出来的树，将1作为根，每一次访问从1开始，在当前所在的prefer链上二分然后explore，若扩展出的点是未访问点则一直怼下去，否则就修改二分区间（实际上在splay上走），如果不在同一条prefer链上就跳到那一条去。

每次找到目标点就access
注意这里需要尽量保持splay的平衡，每次搞出新点都access一下。
具体可以看代码（有些地方可能比较谜，改一点就差很远）

均摊次数就是\(O(n\log n)\)的

Code

#include <bits/stdc++.h>
#include "rts.h"
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 300005
using namespace std;

int cnt;
bool bz[N];
namespace LCT
{
    int sz[N],r[N],f[N],fn[N],dep[N],t[N][2],li[N],ri[N];
    void up(int k) 
    {
        sz[k]=sz[t[k][0]]+sz[t[k][1]]+1;
        li[k]=(t[k][0])?li[t[k][0]]:k;
        ri[k]=(t[k][1])?ri[t[k][1]]:k;
    }
    void hb(int p,int x,int y)
    {
        if(x&&p>=0) t[x][p]=y;
        if(y) fn[y]=p,f[y]=x;
    }
    void rot(int k)
    {
        int fa=f[k],p=fn[k];
        hb(p,fa,t[k][1-p]);
        hb(fn[fa],f[fa],k);
        hb(1-p,k,fa);
        up(fa),up(k);
    }
    int d[N];
    void splay(int k,int x)
    {
        while(f[k]!=x&&fn[k]!=-1&&f[k]!=0) 
        {   
            if(f[f[k]]==x||fn[f[k]]==-1||f[f[k]]==0) rot(k);
            else if(fn[k]==fn[f[k]]) rot(f[k]),rot(k);
            else rot(k),rot(k);
        }
        up(k);
    }
    void access(int k)
    {
        int r=k;
        splay(k,0);
        fn[t[k][1]]=-1,t[k][1]=0;
        up(k);
        while(f[k]!=0)
        {
            int fa=f[k];
            splay(fa,0);
            fn[t[fa][1]]=-1,hb(1,fa,k);
            up(fa),k=fa;
        }
        splay(r,0);
    }
    void link(int x,int y)
    {
        access(x);f[y]=x,fn[y]=-1,up(y);
    }
    void fd(int x,int y)
    {
        splay(x,0);
        while(x!=y)
        {
            cnt++;
            int p=explore(x,y);
            if(p==ri[t[x][0]]) x=t[x][0];
            else if(p==li[t[x][1]]) x=t[x][1];
            else
            {
                if(bz[p]) splay(p,0);
                else up(p),link(x,p),bz[p]=1;
                x=p;
            }
        }
        access(y);
    }
}
using namespace LCT;

int de[N];
void solve3(int n,int T)
{
    int x=1,y=1;
    int i=1;
    while(i<=n-1)
    {
        int w=explore(x,de[i]);
        if(bz[w]) swap(x,y),w=explore(x,de[i]),cnt++;
        bz[w]=1;
        while(w!=de[i]) w=explore(w,de[i]),bz[w]=1,cnt++; 
        x=w;
        while(i<=n-1&&bz[de[i]]) i++;
    }
}

void play(int n, int T, int dataType) 
{
    memset(bz,0,sizeof(bz));
    bz[1]=sz[1]=dep[1]=1;
    up(1);
    fo(i,2,n) de[i-1]=i,sz[i]=1;
    random_shuffle(de+1,de+n);
    if(dataType==3) {solve3(n,T);return;}
    int i=1,w=1;
    while(i<=n-1)
    {
        fd(1,de[i]);
        while(i<=n-1&&bz[de[i]]) i++;
    }
    n++,n--;
}

[LibreOJ #2341]【WC2018】即时战略【交互】【LCT】

原文：https://www.cnblogs.com/BAJimH/p/10689756.html