Wannafly挑战赛16 #E 弹球弹弹弹 splay+基环树+各种思维

链接：https://ac.nowcoder.com/acm/problem/16033
来源：牛客网

有n个位置，标号为1到n的整数，m次操作，第i次操作放置一个弹球在b[i] xor c[i-1]处，并询问b[i] xor c[i-1]处弹球个数c[i]
每次操作后，在x处的弹球被弹到a[x]，规定c[0]=0

把球弹来弹去的位置关系刻画出来的话是一个基环树森林的结构.
每个不在环里的点会逐渐走向环，最终循环地在环里不停的转.
然后你发现如果查询不在环上的点可以用一个 $splay$ 来维护每个联通块中每一个 $dep[u]+time[u]$ 的 $dfs$ 序.
其实就是对于每一条链都以连续区间插入，这样查询的时候是区间查询.
然后对于环上的点如何查询什么时候到就自己 $yy$ 一下吧，这个我实在是想不起来了，细节多的要命.

#include<bits/stdc++.h>

#include <unordered_map>

using namespace std;

#define rg register

#define O2 __attribute__((optimize("-O2")))

char *p1,*p2,buf[100000];

#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

int rd() {int x=0; char c=nc(); while(c<48) c=nc(); while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x;}

const int maxn=500003;

const int inf=10000000;

void setIO(string s) {

    string in=s+".in";

    freopen(in.c_str(),"r",stdin);

    freopen("tt.out","w",stdout);

}

struct Splay {

    #define lson ch[x][0]

    #define rson ch[x][1]

    int cnt;

    int ch[maxn][2],siz[maxn],f[maxn],mn[maxn],mx[maxn],pos[maxn];

    O2 inline void init() {

        cnt=0,mx[0]=-inf,mn[0]=inf;

    }

    O2 inline int get(int x) {

        return ch[f[x]][1]==x;

    }

    O2 inline void pushup(int x) {

        siz[x]=siz[lson]+siz[rson]+1;

        mx[x]=mn[x]=pos[x];

        mx[x]=max(mx[x],mx[rson]);

        mn[x]=min(mn[x],mn[lson]);

    }

    O2 inline void rotate(int x) {

        int old=f[x],fold=f[old],which=get(x);

        ch[old][which]=ch[x][which^1],f[ch[old][which]]=old;

        ch[x][which^1]=old,f[old]=x,f[x]=fold;

        if(fold) ch[fold][ch[fold][1]==old]=x;

        pushup(old), pushup(x);

    }

    O2 inline void splay(int x,int &tar) {

        int u=f[tar],fa;

        for(;(fa=f[x])^u;rotate(x))

            if(f[fa]^u)

                rotate(get(fa)==get(x)?fa:x);

        tar=x;

    }

    O2 void insert(int &x,int p,int ff) {

        if(!x) {

            x=++cnt,f[x]=ff,pos[x]=p;

            pushup(x);

            return;

        }

        insert(ch[x][p>pos[x]],p,x), pushup(x);

    }

    O2 int query(int x,int l,int r) {

        if(!x||mx[x]<l||mn[x]>r) return 0;

        if(mn[x]>=l&&mx[x]<=r) return siz[x];

        int re=0;

        if(pos[x]>=l&&pos[x]<=r) ++re;

        return re+query(lson,l,r)+query(rson,l,r);

    }

    #undef lson

    #undef rson

}tr;

struct Graph {

    int edges;

    int hd[maxn],to[maxn],nex[maxn];

    O2 inline void addedge(int u,int v) {

        nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;

    }

}G,V;

int oo[maxn];

vector<int>mm[maxn<<1];

vector<int>cir[maxn];

unordered_map<int, vector<int> >ins[maxn];

int n,m,id,tim;

int idx[maxn],dep[maxn],dfn[maxn],st[maxn],ed[maxn],top[maxn],dis[maxn];

unordered_map<int,int>rt[maxn];

unordered_map<int,int>bu[maxn];

namespace prepare {

    int du[maxn];

    queue<int>Q;

    O2 void dfs(int u) {

        cir[idx[u]].push_back(u);

        for(rg int i=V.hd[u];i;i=V.nex[i])

        {

            int v=V.to[i];

            if(du[v]&&!idx[v]) {

                idx[v]=idx[u];

                dfs(v);

                break;

            }

        }

    }

    O2 inline void work() {

        for(rg int i=1;i<=V.edges;++i) ++du[V.to[i]];

        for(rg int i=1;i<=n;++i) if(!du[i]) Q.push(i);

        while(!Q.empty()) {

            int u=Q.front(); Q.pop();

            for(rg int i=V.hd[u];i;i=V.nex[i]) {

                int v=V.to[i];

                --du[v];

                if(!du[v]) Q.push(v);

            }

        }

        for(rg int i=1;i<=n;++i) {

            if(!du[i]) continue;

            if(!idx[i]) idx[i]=++id, dfs(i);

        }

    }

};

O2 void dfs(int u,int ff) {

    dep[u]=dep[ff]+1,st[u]=++tim,dfn[tim]=u;

    for(rg int i=G.hd[u];i;i=G.nex[i]) {

        int v=G.to[i];

        if(v==ff||idx[v]) continue;

        top[v]=top[u],dfs(v,u);

    }

    ed[u]=tim;

}

O2 int main() {

    // setIO("input");

    n=rd();

    memset(oo, -1, sizeof(oo));

    for(rg int i=1;i<=n;++i) {

        int x=rd();

        V.addedge(i,x);      // 基环树

        G.addedge(x,i);      // 建树

    }

    prepare::work(), tr.init();

    for(rg int i=1;i<=id;++i)

        for(rg int j=0;j<cir[i].size();++j) {

            top[cir[i][j]]=cir[i][j],dep[0]=-1,dfs(cir[i][j], 0);

            dis[cir[i][j]]=j;

        }

    m=rd();

    int lastans=0;

    for(rg int i=0;i<m;++i) {

        int b,cur,cur_id,cur_siz;

        b=rd(), b^=lastans, lastans=0;

        cur_id=idx[top[b]];

        cur_siz=cir[cur_id].size();

        int x1 = (dis[top[b]] - (i%cur_siz) + cur_siz) % cur_siz;

        int x2 = dep[b]%cur_siz;

        int tmp = (x1 - x2 + cur_siz) % cur_siz;

        ins[cur_id][i+dep[b]].push_back(tmp), mm[i+dep[b]].push_back(cur_id);

        for(rg int o=0;o<mm[i].size();++o) {

            int uu=mm[i][o];

            if(oo[uu]!=i) {

                oo[uu]=i;

                for(rg int j=0;j<ins[uu][i].size();++j) bu[uu][ins[uu][i][j]]+=1;

            }

        }

        if(idx[b]) lastans+=bu[cur_id][(dis[b]-(i%cur_siz)+cur_siz)%cur_siz];

        else {

            cur=dep[b]+i;

            tr.insert(rt[cur_id][cur], st[b], 0) , tr.splay(tr.cnt, rt[cur_id][cur]);

            int a=tr.query(rt[cur_id][cur],st[b],ed[b]);

            lastans+=a;

        }

        printf("%d\n",lastans);

    }

    return 0;

}