【BZOJ3123】【SDOI2013】森林

做法还是比较simple的主席树+启发式合并

然后怎么感觉卡常卡空间啊。。

// <3123.cpp> - Wed Mar  8 09:18:15 2017
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
#define next NEXT
template<typename T>
inline void gg(T &res){
    res=0;T fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    res*=fh;
}
inline int gi(){int x;gg(x);return x;}
inline lol gl(){lol x;gg(x);return x;}
const int MAXN=80010;
const int MAXM=160010;
const int MAXK=MAXN<<8;
const int K=18;
const int INF=1e9;
int u[MAXN],a[MAXN],id[MAXN];
bool cmp(int x,int y){return a[x]<a[y];}
char ch[3];
int n,tot,rt[MAXN],val[MAXK],s[MAXK][2];
int build(int p,int k,int l=1,int r=n){
    int x=++tot;
    val[x]=val[p]+1;
    s[x][0]=s[p][0];s[x][1]=s[p][1];
    if(l==r)return x;
    int m=l+r>>1;
    if(k<=m)s[x][0]=build(s[x][0],k,l,m);
    else s[x][1]=build(s[x][1],k,m+1,r);
    return x;
}
int ask(int a,int b,int c,int d,int k,int l=1,int r=n){
    if(l==r)return l;
    int m=l+r>>1;
    int suml=val[s[a][0]]+val[s[b][0]]-val[s[c][0]]-val[s[d][0]];
    if(suml>=k)return ask(s[a][0],s[b][0],s[c][0],s[d][0],k,l,m);
    return ask(s[a][1],s[b][1],s[c][1],s[d][1],k-suml,m+1,r);
}
int bt,b[MAXN],next[MAXM],to[MAXM];
inline void add(int x,int y){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;
}
int dep[MAXN],f[K][MAXN],size[MAXN],F[MAXN];
void kill(int x,int y){
    F[x]=y;
    for(int i=b[x];i;i=next[i])
        if(F[to[i]]!=y)kill(to[i],y);
    f[0][x]=0;
}
void dfs(int x){
    size[x]=1;
    for(int j=1;j<K;j++)f[j][x]=f[j-1][f[j-1][x]];
    rt[x]=build(rt[f[0][x]],a[x]);
    for(int i=b[x];i;i=next[i]){
        if(to[i]==f[0][x])continue;
        f[0][to[i]]=x;
        dep[to[i]]=dep[x]+1;
        dfs(to[i]);
        size[x]+=size[to[i]];
    }
}
void link(int x,int y){
    if(size[F[x]]>size[F[y]])swap(x,y);
    size[F[y]]+=size[F[x]];
    kill(F[x],F[y]);
    add(x,y);
    f[0][x]=y;
    dep[x]=dep[y]+1;
    dfs(x);
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    int d=dep[x]-dep[y];
    for(int i=0,p=1;i<K;i++,p<<=1)
        if(d&p)x=f[i][x];
    if(x==y)return x;
    for(int i=K-1;i>=0;i--){
        if(f[i][x]==f[i][y])continue;
        x=f[i][x];y=f[i][y];
    }
    return f[0][x];
}
int main(){
    gi();n=gi();int m=gi(),q=gi();
    for(int i=1;i<=n;i++)u[i]=a[i]=gi(),id[i]=i;
    sort(u+1,u+n+1);
    sort(id+1,id+n+1,cmp);
    for(int i=1;i<=n;i++)a[id[i]]=i;
    for(int i=1;i<=n;i++)rt[i]=build(0,a[i]);
    for(int i=1;i<=m;i++)add(gi(),gi());
    for(int i=1;i<=n;i++)if(!F[i]){kill(i,i);dfs(i);}
    int ans=0;
    while(q--){
        scanf("%s",ch);
        if(ch[0]=='Q'){
            int x=gi()^ans,y=gi()^ans,z=lca(x,y),k=gi()^ans;
            printf("%d\n",ans=u[ask(rt[x],rt[y],rt[z],rt[f[0][z]],k)]);
        }else link(gi()^ans,gi()^ans);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

// <3123.cpp> - Wed Mar 8 09:18:15 2017

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

#define next NEXT

template<typename T>

inline void gg(T &res){

res=0;T fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

res*=fh;

}

inline int gi(){int x;gg(x);return x;}

inline lol gl(){lol x;gg(x);return x;}

const int MAXN=80010;

const int MAXM=160010;

const int MAXK=MAXN<<8;

const int K=18;

const int INF=1e9;

int u[MAXN],a[MAXN],id[MAXN];

bool cmp(int x,int y){return a[x]<a[y];}

char ch[3];

int n,tot,rt[MAXN],val[MAXK],s[MAXK][2];

int build(int p,int k,int l=1,int r=n){

int x=++tot;

val[x]=val[p]+1;

s[x][0]=s[p][0];s[x][1]=s[p][1];

if(l==r)return x;

int m=l+r>>1;

if(k<=m)s[x][0]=build(s[x][0],k,l,m);

else s[x][1]=build(s[x][1],k,m+1,r);

return x;

}

int ask(int a,int b,int c,int d,int k,int l=1,int r=n){

if(l==r)return l;

int m=l+r>>1;

int suml=val[s[a][0]]+val[s[b][0]]-val[s[c][0]]-val[s[d][0]];

if(suml>=k)return ask(s[a][0],s[b][0],s[c][0],s[d][0],k,l,m);

return ask(s[a][1],s[b][1],s[c][1],s[d][1],k-suml,m+1,r);

}

int bt,b[MAXN],next[MAXM],to[MAXM];

inline void add(int x,int y){

next[++bt]=b[x];b[x]=bt;to[bt]=y;

next[++bt]=b[y];b[y]=bt;to[bt]=x;

}

int dep[MAXN],f[K][MAXN],size[MAXN],F[MAXN];

void kill(int x,int y){

F[x]=y;

for(int i=b[x];i;i=next[i])

if(F[to[i]]!=y)kill(to[i],y);

f[0][x]=0;

}

void dfs(int x){

size[x]=1;

for(int j=1;j<K;j++)f[j][x]=f[j-1][f[j-1][x]];

rt[x]=build(rt[f[0][x]],a[x]);

for(int i=b[x];i;i=next[i]){

if(to[i]==f[0][x])continue;

f[0][to[i]]=x;

dep[to[i]]=dep[x]+1;

dfs(to[i]);

size[x]+=size[to[i]];

}

void link(int x,int y){

if(size[F[x]]>size[F[y]])swap(x,y);

size[F[y]]+=size[F[x]];

kill(F[x],F[y]);

add(x,y);

f[0][x]=y;

dep[x]=dep[y]+1;

dfs(x);

}

int lca(int x,int y){

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

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

for(int i=0,p=1;i<K;i++,p<<=1)

if(d&p)x=f[i][x];

if(x==y)return x;

for(int i=K-1;i>=0;i--){

if(f[i][x]==f[i][y])continue;

x=f[i][x];y=f[i][y];

}

return f[0][x];

}

int main(){

gi();n=gi();int m=gi(),q=gi();

for(int i=1;i<=n;i++)u[i]=a[i]=gi(),id[i]=i;

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

sort(id+1,id+n+1,cmp);

for(int i=1;i<=n;i++)a[id[i]]=i;

for(int i=1;i<=n;i++)rt[i]=build(0,a[i]);

for(int i=1;i<=m;i++)add(gi(),gi());

for(int i=1;i<=n;i++)if(!F[i]){kill(i,i);dfs(i);}

int ans=0;

while(q--){

scanf("%s",ch);

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

int x=gi()^ans,y=gi()^ans,z=lca(x,y),k=gi()^ans;

printf("%d\n",ans=u[ask(rt[x],rt[y],rt[z],rt[f[0][z]],k)]);

}else link(gi()^ans,gi()^ans);

}

return 0;

}

6 评论

最旧