T1 永无乡

初做：2017.3.8

现在：2017.3.30

大约2个半小时

许多点，点有点权，2个操作：连边、询问与某个点相连的点权的k值

#include
      
       #include
       
        #define N 100001using namespace std;int n,m,tot,cnt,fa[N];int sum[N*20],lc[N*20],rc[N*20],root[N];int key[N],hashh[N];int find(int i) { return fa[i]==i ? i: fa[i]=find(fa[i]); }void insert(int & now,int l,int r,int w){    if(!now) now=++cnt;    sum[now]++;    if(l==r) return;    int mid=l+r>>1;    if(w<=mid) insert(lc[now],l,mid,w);    else insert(rc[now],mid+1,r,w);}int query(int now,int l,int r,int w){    if(l==r) return hashh[l];    int mid=l+r>>1;    if(w<=sum[lc[now]]) return query(lc[now],l,mid,w);    else return query(rc[now],mid+1,r,w-sum[lc[now]]);}int unionn(int x,int y){    if(!x) return y;    if(!y) return x;    lc[x]=unionn(lc[x],lc[y]);    rc[x]=unionn(rc[x],rc[y]);    sum[x]=sum[lc[x]]+sum[rc[x]];    return x;}int main(){    scanf("%d%d",&n,&m);     for(int i=1;i<=n;i++)    {        scanf("%d",&key[i]);        fa[i]=i;        hashh[key[i]]=i;    }    int x,y,r1,r2;    while(m--)    {        scanf("%d%d",&x,&y);        r1=find(x);r2=find(y);        if(r1!=r2) fa[r2]=r1;    }    for(int i=1;i<=n;i++)     insert(root[find(i)],1,n,key[i]);    scanf("%d",&m);    char c[1];    while(m--)    {        scanf("%s%d%d",c,&x,&y);        if(c[0]=='B')        {            r1=find(x);r2=find(y);            if(r1!=r2)            {                fa[r2]=r1;                unionn(root[r1],root[r2]);            }        }        else        {            x=find(x);            if(y>sum[root[x]]) printf("-1\n");            else printf("%d\n",query(root[x],1,n,y));        }    }}
       
      

首先，自恃做过一遍不读完题，上来写了一个离散化点权

题目中写着点权1——n，所以不用离散化

 

顺手写的错误：

if(r1!=r2){    fa[r2]=r1;    unionn(r1,r2);}

应该是

unionn(root[r1],root[r2]);

并查集写太熟了，以后注意思考

 

本质错误：合并

错误合并1：

void unionn(int & x,int y){    if(!y) return;    if(!x) x=++cnt;    sum[x]+=sum[y];    unionn(lc[x],lc[y]);    unionn(rc[x],rc[y]);}

把y合并到x上，如果y为0，那么自y一下都不用合并，

如果x为0，建立新的x

分析：合并思路正确，代码也正确，但做了大量无用的合并

如果x为0，新建一系列节点，这些节点完全等于y以下的节点，所以与y公用即可

 

错误合并2：

void unionn(int & x,int y){    if(!y) return;    if(!x) x=y;    else sum[x]+=sum[y];    unionn(lc[x],lc[y]);    unionn(rc[x],rc[y]);}

思路错误，错误原因还不清楚

 

正确合并：

int unionn(int x,int y){    if(!x) return y;    if(!y) return x;    lc[x]=unionn(lc[x],lc[y]);    rc[x]=unionn(rc[x],rc[y]);    sum[x]=sum[lc[x]]+sum[rc[x]];    return x;}

自底向上的合并，公用节点

 

恕我无能，splay的没调出来

 

T2 森林

初做：2017.3.9 

现在：2017.3.31 第一遍就没写出来

 

给出一些点，点有点权，这些点构成一个森林。

有两种操作：连接点x和点y， 询问x和y路径上的k值

#include
      
       #include
       
        #define N 80001using namespace std;int n,m,t,tot,ans,cnt;int key[N],hash[N],F[N];int ancestor[N][18];int siz[N],deep[N];int sum[N*200],lc[N*200],rc[N*200],root[N];int front[N],next[N*4],to[N*4],tt;void add(int u,int v){    to[++tt]=v; next[tt]=front[u]; front[u]=tt;}int find(int i) {
    return F[i]==i ? i:F[i]=find(F[i]);}void discrete(){    sort(hash+1,hash+n+1);    tot=unique(hash+1,hash+n+1)-(hash+1);    for(int i=1;i<=n;i++) key[i]=lower_bound(hash+1,hash+n+1,key[i])-hash;}void insert(int pre,int &now,int l,int r,int w){    now=++cnt;    sum[now]=sum[pre]+1;    if(l==r) return;    int mid=l+r>>1;    if(w<=mid)     {        insert(lc[pre],lc[now],l,mid,w);        rc[now]=rc[pre];    }    else    {        insert(rc[pre],rc[now],mid+1,r,w);        lc[now]=lc[pre];    }}void dfs(int x){    insert(root[ancestor[x][0]],root[x],1,tot,key[x]);    for(int i=front[x];i;i=next[i])    {        if(to[i]==ancestor[x][0]) continue;        ancestor[to[i]][0]=x;        deep[to[i]]=deep[x]+1;        dfs(to[i]);    }}void query(int x,int y,int lca,int flca,int l,int r,int k){    if(l==r) {ans=hash[l];return;}    int mid=l+r>>1,tmp=sum[lc[x]]+sum[lc[y]]-sum[lc[lca]]-sum[lc[flca]];    if(k<=tmp) query(lc[x],lc[y],lc[lca],lc[flca],l,mid,k);    else query(rc[x],rc[y],rc[lca],rc[flca],mid+1,r,k-tmp);}void pre_lca(){    for(int i=1,k=2;i<=17;i++,k*=2)     for(int j=1;j<=n;j++)      ancestor[j][i]=ancestor[ancestor[j][i-1]][i-1];}int getsame(int x,int y){    for(int i=0;i<=17;i++)     if(y&(1<
        
         =0;i--)     if(ancestor[x][i]!=ancestor[y][i])      {           x=ancestor[x][i];y=ancestor[y][i];      }    return ancestor[x][0];}void unionn(int x,int y){    ancestor[y][0]=x;deep[y]=deep[x]+1;    insert(root[x],root[y],1,tot,key[y]);    for(int i=1;i<=17;i++) ancestor[y][i]=ancestor[ancestor[y][i-1]][i-1];    for(int i=front[y];i;i=next[i])        if(to[i]!=ancestor[y][0]) unionn(y,to[i]);}int main(){    scanf("%d",&t);    scanf("%d%d%d",&n,&m,&t);    for(int i=1;i<=n;i++) scanf("%d",&key[i]),hash[i]=key[i],F[i]=i,siz[i]=1;    discrete();    int x,y,z,r1,r2;    for(int i=1;i<=m;i++)    {        scanf("%d%d",&x,&y);        r1=find(x);r2=find(y);        if(r1==r2)  continue;        F[r1]=r2;siz[r2]+=siz[r1];        add(x,y);add(y,x);    }    for(int i=1;i<=n;i++) if(!ancestor[i][0]) dfs(i);    pre_lca();    char c[5];int s1,s2,lca;    for(int i=1;i<=t;i++)    {        scanf("%s",c);        if(c[0]=='L')        {            scanf("%d%d",&x,&y);            x^=ans; y^=ans;            r1=find(x);r2=find(y);            if(r1==r2) continue;            s1=siz[r1];s2=siz[r2];            if(s1
        
       
      

树上k值，主席树

由于要询问路径上的k值，所以并查集和主席树是相对独立的

因为路径压缩之后的并查集不能维护父子关系

并查集的作用仅仅是指示 要合并的 两棵树的大小，决定谁合并到谁

再就是动态维护lca比较棘手：

每合并2个点，都要更改一个点的lca。另y的ancestor[y][0]=x，然后倍增（利用ancestor[x][]）

得到一对点的lca：

先让深的点跳到与浅的点深度相同的位置，然后一起往上跳

 

 

小结：

线段树的启发式合并，仅仅涉及数量关系，对应位置的节点直接相加，所以他不能解决路径上的问题

也就是不需要维护形态

并查集的祖先节点与线段树合并的根节点是相对应的

对于开始就相连的点，并查集维护祖先节点，插点的时候直接插到祖先节点的那颗树里即可

 

主席树的启发式合并，可以通过lca维护数的形态，解决路径上的问题，

合并的时候要打散其中一颗树，（直接无视这棵树），

重新以y为根节点，组织与y相连的所有节点，插到另一颗树里（链表存储双向边，从y开始递归即可）

对于开始就相连的点，连边即可

然后以dfs序插入所有节点，顺带维护信息