bzoj 3123 可持久化线段树启发式合并

　　首先没有连边的操作的时候，我们可以用可持久化线段树来维护这棵树的信息，建立权值可持久化线段树，那么每个点继承父节点的线段树，当询问为x,y的时候我们可以询问rot[x]+rot[y]-rot[lca(x,y)]-rot[lca(x,y)->father]这棵树来得知这个链的信息。

　　那么对于连边操作，相当于合并两棵树，我们可以将树的节点数小的树全部拆掉连到节点大的树中，这样每个点最多会被操作logn次，每次操作的时间复杂度为logn，所以是mlog^2n的。

　　反思：对于树的连通性我是用并查集维护的，对于合并操作还需要dfs一次小的树来维护各种信息，但是忘记对x,y点连边了，导致一直RE.(RE是因为某次值不正确，导致下一次^的点超过n)。

　　　　各种慢= =。

/**************************************************************

    Problem: 3123

    User: BLADEVIL

    Language: C++

    Result: Accepted

    Time:16612 ms

    Memory:81512 kb

****************************************************************/

//By BLADEVIL

#include <cstdio>

#include <cstring>

#include <algorithm>

#define maxn 100010

#define maxm 200010

using namespace std;

struct rec {

    int key,num;

    rec() {

        key=num=;

    }

}a[maxn];

struct segment {

    int left,right,cnt;

    int son[];

    segment() {

        left=right=cnt=;

        memset(son,,sizeof son);

    }

}t[maxn<<];

int n,m,l,N,tot;

int pre[maxm<<],last[maxm<<],other[maxm<<];

int ans[maxn],rot[maxn];

int dep[maxn],jump[maxn][],father[maxn],size[maxn],que[maxn];

void connect(int x,int y) {

    pre[++l]=last[x];

    last[x]=l;

    other[l]=y;

}

int getfather(int x) {

    if (father[x]==x) return x;

    return father[x]=getfather(father[x]);

}

void dfs(int x,int fa) {

    jump[x][]=fa; dep[x]=dep[fa]+;

    for (int p=last[x];p;p=pre[p]) {

        if (other[p]==fa) continue;

        dfs(other[p],x);

    }

}

bool cmp1(rec x,rec y) {

    return x.key<y.key;

}

bool cmp2(rec x,rec y) {

    return x.num<y.num;

}

int lca(int x,int y) {

    if (dep[x]>dep[y]) swap(x,y);

    int d=dep[y]-dep[x];

    for (int i=;i<=;i++) if (d&(<<i)) y=jump[y][i];

    if (x==y) return x;

    for (int i=;i>=;i--) if (jump[x][i]!=jump[y][i]) x=jump[x][i],y=jump[y][i];

    return jump[x][];

}

void build(int &x,int l,int r) {

    if (!x) x=++tot;

    t[x].left=l; t[x].right=r;

    if (t[x].left==t[x].right) return ;

    int mid=t[x].left+t[x].right>>;

    build(t[x].son[],l,mid); build(t[x].son[],mid+,r);

}

void insert(int &x,int rot,int key) {

    if (!x) x=++tot;

    t[x].left=t[rot].left; t[x].right=t[rot].right;

    if (t[x].left==t[x].right) {

        t[x].cnt=t[rot].cnt+;

        return ;

    }

    int mid=t[x].left+t[x].right>>;

    if (key>mid) {

        t[x].son[]=t[rot].son[];

        insert(t[x].son[],t[rot].son[],key);

    } else {

        t[x].son[]=t[rot].son[];

        insert(t[x].son[],t[rot].son[],key);

    }

    t[x].cnt=t[rot].cnt+;

}

int query(int x,int y,int l1,int l2,int k) {

    //printf("%d %d %d ",x,t[x].left,t[x].right);

    if (t[x].left==t[x].right) return t[x].left;

    int cur=t[t[x].son[]].cnt+t[t[y].son[]].cnt-t[t[l1].son[]].cnt-t[t[l2].son[]].cnt;

    //printf("%d\n",cur);

    if (k>cur) return query(t[x].son[],t[y].son[],t[l1].son[],t[l2].son[],k-cur); else

        return query(t[x].son[],t[y].son[],t[l1].son[],t[l2].son[],k);

}

void make(int x,int fa) {

    insert(rot[x],rot[fa],a[x].key);

    for (int p=last[x];p;p=pre[p]) {

        if (other[p]==fa) continue;

        make(other[p],x);

    }

}

void update(int x,int fa,int j) {

    jump[x][j]=jump[jump[x][j-]][j-];

    for (int p=last[x];p;p=pre[p]) {

        if (other[p]==fa) continue;

        update(other[p],x,j);

    }

}

void merge(int x,int y) {

    int fx=getfather(x),fy=getfather(y);

    //if (x==1) printf("%d %d\n",fx,fy);

    if (size[fx]<size[fy]) swap(x,y);

    fx=getfather(x),fy=getfather(y);

    father[fy]=fx; size[fx]+=size[fy];

    dfs(y,x); make(y,x);

    for (int i=;i<=;i++) update(y,x,i);

    //for (int i=1;i<=n;i++) printf("%d %d\n",i,jump[i][0]);

}

int main() {

    //freopen("3123.in","r",stdin); freopen("3123.out","w",stdout);

    int task; scanf("%d",&task);

    scanf("%d%d%d",&n,&m,&task);

    for (int i=;i<=n;i++) scanf("%d",&a[a[i].num=i].key); 

    sort(a+,a++n,cmp1);

    int cur; ans[]=cur=a[].key;

    for (int i=,j=;i<=n;i++)

        if (a[i].key==cur) a[i].key=j; else ans[++j]=cur=a[i].key,a[i].key=j,N=j;

    sort(a+,a++n,cmp2);

    //for (int i=1;i<=n;i++) printf("%d ",ans[i]); printf("\n");

    //for (int i=1;i<=n;i++) printf("%d ",a[i].key); printf("\n");

    for (int i=;i<=n;i++) father[i]=i,size[i]=;

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

        int x,y; scanf("%d%d",&x,&y);

        connect(x,y); connect(y,x);

        int fx=getfather(x),fy=getfather(y);

        father[fx]=fy; size[fy]+=size[fx];

    }

    for (int i=;i<=n;i++) if (!jump[i][]) dfs(i,);

    //for (int i=1;i<=n;i++) printf("%d %d\n",i,father[i]);

    //for (int i=1;i<=n;i++) if (i==getfather(i)) printf("%d %d\n",i,size[i]);

    for (int j=;j<=;j++)

        for (int i=;i<=n;i++) jump[i][j]=jump[jump[i][j-]][j-];

    build(rot[],,N);

    for (int i=;i<=n;i++) if (!jump[i][]) make(i,);

    int ANS=; char Q[];

    while (task--) {

        scanf("%s",Q);

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

            int x,y,k; scanf("%d%d%d",&x,&y,&k);

            x^=ANS; y^=ANS; k^=ANS;

            //printf("|%d %d %d\n",x,y,k);

            int rr=lca(x,y); //printf("%d\n",rr);

            //for (int i=1;i<=n;i++) printf("%d %d\n",i,jump[i][0]);

            printf("%d\n",ANS=ans[query(rot[x],rot[y],rot[rr],rot[jump[rr][]],k)]);

            //for (int i=1;i<=n;i++) if (i==getfather(i)) printf("%d %d\n",i,size[i]);

        } else {

            int x,y; scanf("%d%d",&x,&y);

            x^=ANS; y^=ANS; connect(x,y); connect(y,x);

            //printf("|%d %d\n",x,y);

            merge(x,y);

        }

    }

    return ;

}

巴特西

bzoj 3123 可持久化线段树启发式合并

最新文章

热门文章