3123: [Sdoi2013]森林

Time Limit: 20 Sec  Memory Limit: 512 MB

Submit: 2738  Solved: 806

[][][]

Description

 

Input

第一行包含一个正整数testcase，表示当前测试数据的测试点编号。保证1≤testcase≤20。 

第二行包含三个整数N，M，T，分别表示节点数、初始边数、操作数。第三行包含N个非负整数表示 N个节点上的权值。 

 接下来 M行，每行包含两个整数x和 y，表示初始的时候，点x和点y 之间有一条无向边, 接下来 T行，每行描述一个操作，格式为“Q x y k”或者“L x y ”，其含义见题目描述部分。

Output

对于每一个第一类操作，输出一个非负整数表示答案。 

 

 

Sample Input

1

8 4 8

1 1 2 2 3 3 4 4

4 7

1 8

2 4

2 1

Q 8 7 3 Q 3 5 1

Q 10 0 0

L 5 4

L 3 2 L 0 7

Q 9 2 5 Q 6 1 6

Sample Output

2

2

1

4

2

HINT

 

对于第一个操作 Q 8 7 3，此时 lastans=0，所以真实操作为Q 8^0 7^0 3^0，也即Q 8 7 3。点8到点7的路径上一共有5个点，其权值为4 1 1 2 4。这些权值中，第三小的为 2，输出 2，lastans变为2。对于第二个操作 Q 3 5 1 ，此时lastans=2，所以真实操作为Q 3^2 5^2 1^2 ，也即Q 1 7 3。点1到点7的路径上一共有4个点，其权值为 1 1 2 4 。这些权值中，第三小的为2，输出2，lastans变为 2。之后的操作类似。 

 

 

Source

Solution

沃日..这题什么东西..

直接树上主席树启发式合并就好了...

然后我写了3遍..第一遍2&10~13RE其余AC..然后肉眼差错无果..重写第二遍，基本没变，10~13RE...MD再写AC..什么破玩意...

我觉得唯一需要注意的就是LCA合并后要清空，还好我注意到了...

Code

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;inline int read(){    int x=0,f=1; char ch=getchar();    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}    return x*f;}#define MAXN 100010int N,M,Q,ls[MAXN],top,val[MAXN],testcase,lastans;struct EdgeNode{    int next,to;}edge[MAXN<<1];int head[MAXN],cnt=1;inline void AddEdge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}inline void InsertEdge(int u,int v) {AddEdge(u,v); AddEdge(v,u);} namespace UF{    int f[MAXN],size[MAXN];    inline void init() {for (int i=1; i<=N; i++) f[i]=i,size[i]=1;}    inline int F(int x) {if (x==f[x]) return x; return f[x]=F(f[x]);}    inline void Merge(int x,int y) {x=F(x),y=F(y); size[y]+=size[x]; f[x]=y;}}using namespace UF;namespace PrTree{    int lson[MAXN*100],rson[MAXN*100],root[MAXN],sum[MAXN*100],sz;    inline void Insert(int l,int r,int &x,int y,int pos,int val)    {        x=++sz; sum[x]=sum[y]+val;        if (l==r) return;        lson[x]=lson[y],rson[x]=rson[y];        int mid=(l+r)>>1;        if (pos<=mid) Insert(l,mid,lson[x],lson[y],pos,val);            else Insert(mid+1,r,rson[x],rson[y],pos,val);    }    inline int Query(int l,int r,int kth,int a,int b,int c,int d)    {        if (l==r) return l;        int Sum=0,mid=(l+r)>>1;        Sum=sum[lson[a]]+sum[lson[b]]-sum[lson[c]]-sum[lson[d]];        if (Sum
          
           =(1<
           
            =0; i--) if (father[i][x]!=father[i][y]) x=father[i][x],y=father[i][y]; return x==y? x:father[0][x];}inline void Link(int x,int y){ int fx=F(x),fy=F(y); InsertEdge(x,y); if (size[fx]>size[fy]) father[0][y]=x,deep[y]=deep[x]+1,DFS(y,x); else father[0][x]=y,deep[x]=deep[y]+1,DFS(x,y); Merge(x,y);}int main(){// freopen("tree.in","r",stdin);// freopen("tree.out","w",stdout); testcase=read(); N=read(),M=read(),Q=read(); for (int i=1; i<=N; i++) ls[i]=val[i]=read(); sort(ls+1,ls+N+1); top=unique(ls+1,ls+N+1)-ls-1; for (int i=1; i<=N; i++) val[i]=lower_bound(ls+1,ls+top+1,val[i])-ls; UF::init(); for (int i=1,x,y; i<=M; i++) x=read(),y=read(),InsertEdge(x,y),Merge(x,y); for (int i=1; i<=N; i++) if (!root[i]) DFS(i,0); while (Q--) { char opt[2]; scanf("%s",opt+1); int x,y,z,lca; switch (opt[1]) { case 'Q': x=read(),y=read(),z=read(); x^=lastans,y^=lastans,z^=lastans; lca=LCA(x,y); printf("%d\n",lastans=ls[PrTree::Query(1,top,z,root[x],root[y],root[lca],root[father[0][lca]])]); break; case 'L': x=read(),y=read(); x^=lastans,y^=lastans; Link(x,y); break; } } return 0;}