BZOJ3123：[SDOI2013]森林

浅谈主席树：https://www.cnblogs.com/AKMer/p/9956734.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3123

如果是一棵树，维护树上路径第\(k\)大，我们令\(rt[i]\)为加入\(i\)号结点之后主席树的根，若我们在\(rt[fa[i]]\)的基础上建\(rt[i]\)这棵树，那么从每个结点的\(rt[i]\)开始，即可访问原树的根到自己这一条路径上所有权值的\(cnt\)，那么\(cnt[u]+cnt[v]-cnt[lca]-cnt[fa[lca]]\)就是路径上在该权值区间内的结点个数。由于题目保证\(u,v\)联通并且路径上的点大于等于\(k\)，所以询问就迎刃而解了。

我们考虑对于合并，如果运用启发式合并的思想，每次将大小比较小的树接在大的树上，然后重构小的树，每个点最多会被这样操作\(logn\)次，每次需要更新主席树上对应的根和倍增数组，是\(logn\)复杂度的，所以最后就是\(log^2n\)的。因为每个点最多会被建\(logn\)次，每次会建\(logn\)个节点，所以主席树大小也要开到\(log^2n\)去。

时间复杂度：\(O(nlog^2n)\)

空间复杂度：\(O(nlog^2n)\)

代码如下：

#include <cmath>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=8e4+5;

int tmp[maxn],a[maxn],rt[maxn];

int n,m,q,cnt,tot,lstans,testcase;

int now[maxn],pre[maxn*2],son[maxn*2];

int dep[maxn],belong[maxn],siz[maxn],f[maxn][18];

int read() {

    int x=0,f=1;char ch=getchar();

    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

    for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

    return x*f;

}

struct tree_node {

    int cnt,ls,rs;

};

struct chairman_tree {

    int tot;

    tree_node tree[maxn*17*17];

    void ins(int lst,int &now,int l,int r,int pos) {

        now=++tot;tree[now]=tree[lst];tree[now].cnt++;

        if(l==r)return;

        int mid=(l+r)>>1;

        if(pos<=mid)ins(tree[lst].ls,tree[now].ls,l,mid,pos);

        else ins(tree[lst].rs,tree[now].rs,mid+1,r,pos);

    }

    int query(int fa1,int fa2,int u,int v,int l,int r,int rk) {

        if(l==r)return tmp[l];

        int mid=(l+r)>>1;

        int sum=tree[tree[u].ls].cnt+tree[tree[v].ls].cnt;

        sum-=(tree[tree[fa1].ls].cnt+tree[tree[fa2].ls].cnt);//sum就是路径上值在[l,mid]的节点的个数

        if(sum>=rk)return query(tree[fa1].ls,tree[fa2].ls,tree[u].ls,tree[v].ls,l,mid,rk);

        return query(tree[fa1].rs,tree[fa2].rs,tree[u].rs,tree[v].rs,mid+1,r,rk-sum);

    }

}T;

void add(int a,int b) {

    pre[++tot]=now[a];

    now[a]=tot;son[tot]=b;

}

void dfs(int fa,int u,int id) {

    siz[id]++,belong[u]=id;

    f[u][0]=fa,dep[u]=dep[fa]+1;

    for(int i=1;i<=17;i++)

        f[u][i]=f[f[u][i-1]][i-1];

    T.ins(rt[fa],rt[u],1,cnt,a[u]);//每个点建主席树都在父亲主席树基础上建

    for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

        if(v!=fa)dfs(u,v,id);

}

int lca(int u,int v) {

    if(dep[u]<dep[v])swap(u,v);

    for(int i=17;~i;i--)

        if(dep[f[u][i]]>=dep[v])

            u=f[u][i];

    if(u==v)return u;

    for(int i=17;~i;i--)

        if(f[u][i]!=f[v][i])

            u=f[u][i],v=f[v][i];

    return f[u][0];

}

int main() {

    testcase=read();

    n=read();m=read();q=read();

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

        tmp[i]=a[i]=read();

    sort(tmp+1,tmp+n+1);

    cnt=unique(tmp+1,tmp+n+1)-tmp-1;

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

        a[i]=lower_bound(tmp+1,tmp+cnt+1,a[i])-tmp;

    for(int i=1;i<=m;i++) {

        int x=read(),y=read();

        add(x,y);add(y,x);

    }

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

        if(!dep[i])dfs(0,i,i);

    for(int i=1;i<=q;i++) {

        char s[5];scanf("%s",s+1);

        int u=read()^lstans,v=read()^lstans;

        if(s[1]=='Q') {

            int k=read()^lstans;

            int fa=lca(u,v);

            lstans=T.query(rt[f[fa][0]],rt[fa],rt[u],rt[v],1,cnt,k);

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

        }

        else {

            int x=belong[u],y=belong[v];

            if(siz[x]>siz[y])swap(x,y),swap(u,v);

            add(u,v),add(v,u),dfs(v,u,y);//把小的往大的上合并

        }

    }

    return 0;

}

巴特西

BZOJ3123：[SDOI2013]森林

最新文章

热门文章