洛谷P3224 [HNOI二零一一]永无乡

作者: 王中王开奖结果计算机  发布:2019-09-24

主题素材陈述

永无乡含有 n 座岛,编号从 1 到 n,每座岛都有温馨的绝代的显要度,依照注重度可 以将那 n 座岛排行,排行用 1 到 n 来代表。有些岛之间由巨大的桥连接,通过桥得以从贰个岛 达到另多少个岛。如果从岛 a 出发经过多少座(含 0 座)桥得以达到岛 b,则称岛 a 和岛 b 是连 通的。

这段日子有三种操作:

B x y 表示在岛 x 与岛 y 之间修筑一座新桥。

Q x k 表示明白当前与岛 x连通的全体岛中第 k 首要的是哪座岛,即具备与岛 x 连通的岛中要害度排行第 k 小的岛是哪 座,请你输出那些岛的号子。

输入输出格式

输入格式:

 

输入文件首先行是用空格隔断的三个正整数 n 和 m,分别 表示岛的个数以及一开头存在的桥数。接下来的一行是用空格隔断的 n 个数,依次描述从岛 1 到岛 n 的主要度排名。随后的 m 行每行是用空格隔断的三个正整数 ai 和 bi,表示一发端就存 在一座连接岛 ai 和岛 bi 的桥。后边剩下的有的陈说操作,该片段的首先行是三个正整数 q, 表示一共有 q 个操作,接下去的 q 行依次描述每一个操作,操作的格式如上所述,以大写字母 Q 或B 最初,前边跟多少个不超越 n 的正整数,字母与数字以及四个数字之间用空格隔断。 对于 十分之二的数码 n<=一千,q<=一千 对于 百分百的多寡 n<=100000,m<=n,q<=三千00

 

输出格式:

 

对此各种 Q x k 操作都要挨个输出一行,个中满含贰个整数,表 示所理解岛屿的编号。要是该海岛子虚乌有,则输出-1。

 

输入输出样例

输入样例#1: 复制

5  1
4  3 2 5 1
1  2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3



对于联通性问题,我们可以用并查集维护
对于动态集合第k大,我们可以用平衡树维护
这样的话维护n个splay
然后每次暴力合并就好
注意要用启发式合并
只有这样插入点的复杂度才是严格 $O(logn)$

  1 #include<iostream>
  2 #include<cstdio>
  3 using namespace std;
  4 const int MAXN=1e6+10;
  5 const int maxn=0x7fffff;
  6 #define ls tree[k].ch[0]
  7 #define rs tree[k].ch[1]
  8 inline int read()
  9 {
 10     char c=getchar();int x=0,f=1;
 11     while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
 12     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
 13     return x*f;
 14 }
 15 struct node
 16 {
 17     int v,fa,ch[2],sum;
 18 }tree[MAXN];
 19 int pointnum,tot;
 20 int root[MAXN],val[MAXN],f[MAXN],n,m;
 21 char opt[10];
 22 int iden(int x){return tree[tree[x].fa].ch[0]==x?0:1;}
 23 inline void connect(int x,int fa,int how){tree[x].fa=fa;tree[fa].ch[how]=x;}
 24 inline void update(int x)
 25 {tree[x].sum=tree[tree[x].ch[0]].sum+tree[tree[x].ch[1]].sum+1;}
 26 inline void rotate(int x)
 27 {
 28     int y=tree[x].fa;
 29     int R=tree[y].fa;
 30     int Rson=iden(y);
 31     int yson=iden(x);
 32     int b=tree[x].ch[yson^1];
 33     connect(b,y,yson);
 34     connect(y,x,yson^1);
 35     connect(x,R,Rson);
 36     update(y);update(x);
 37 }
 38 void splay(int x,int to)// 把编号为pos的节点旋转到编号为to的节点 
 39 {
 40     while(tree[x].fa!=to)
 41     {
 42         int y=tree[x].fa,z=tree[y].fa;
 43         if(z!=to)
 44             (tree[z].ch[0]==y)^(tree[y].ch[0]==x)?rotate(x):rotate(y);
 45         rotate(x);
 46     }
 47     if(to<=n)    root[to]=x;
 48 }
 49 void insert(int v,int pos)
 50 {
 51     int now=root[pos],fa=pos;
 52     while(now&&tree[now].v!=v)
 53         fa=now,now=tree[now].ch[v>tree[now].v];
 54     now=++tot;
 55     tree[now].sum=1;
 56     tree[now].fa=fa;
 57     if(fa>n)    tree[fa].ch[v>tree[fa].v]=now;
 58     tree[now].v=v;tree[now].ch[0]=tree[now].ch[1]=0;
 59     splay(now,pos);
 60 }
 61 int rank(int pos,int k)
 62 {
 63     int now=root[pos];
 64     if(tree[now].sum<k)    return -1;
 65     while(1)
 66     {
 67         if(tree[tree[now].ch[0]].sum+1<k)    k-=tree[tree[now].ch[0]].sum+1,now=tree[now].ch[1];
 68         else    if(tree[tree[now].ch[0]].sum>=k)    now=tree[now].ch[0];
 69         else    return tree[now].v;
 70     }
 71     splay(now,root[pos]);
 72     return tree[now].v;
 73 }
 74 int Gets(int x)
 75 {
 76     if(f[x]==x)    return f[x];
 77     else return f[x]=Gets(f[x]);
 78 }
 79 void DFS(int k,int fa)
 80 {
 81     if(ls)    DFS(ls,fa);
 82     if(rs)    DFS(rs,fa);
 83     insert(tree[k].v,fa);
 84 }
 85 void Merge(int x,int y)
 86 {
 87     x=Gets(x),y=Gets(y);
 88     if(x==y)    return ;
 89     if(tree[root[x]].sum>tree[root[y]].sum)    swap(x,y);
 90     f[x]=y;
 91     DFS(root[x],y);
 92 }
 93 int main()
 94 {
 95     #ifdef WIN32
 96     freopen("a.in","r",stdin);
 97     #else
 98     #endif
 99     n=read(),m=read();
100     tot=n*2;
101     for(int i=1;i<=n;i++)
102     {
103         int p=read();
104         val[p]=i;
105         tree[i+n].v=p;
106         tree[i+n].sum=1;
107         tree[i+n].fa=i;
108         root[i]=i+n;        
109         f[i]=i;
110     }
111     for(int i=1;i<=m;i++)
112     {
113         int x=read(),y=read();
114         Merge(x,y);
115     }
116     int q=read();
117     while(q--)
118     {
119         int x,y;
120         scanf("%s",opt);
121         x=read();y=read();
122         if(opt[0]=='B')    
123             Merge(x,y);
124         else 
125         {
126             int ans=rank(Gets(x),y);
127             printf("%dn",ans==-1?ans:val[ans]);
128         }
129     }
130 } 

 

本文由王中王开奖结果发布于王中王开奖结果计算机,转载请注明出处:洛谷P3224 [HNOI二零一一]永无乡

关键词: