编程知识 购物 网址 新闻 笑话 | 软件 日历 阅读 图书馆 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
   -> C++ -> 洛谷P3224 [HNOI2012]永无乡 -> 正文阅读

[C++]洛谷P3224 [HNOI2012]永无乡

题目描述
永无乡包含 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 的正整数,字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 n<=1000,q<=1000 对于 100%的数据 n<=100000,m<=n,q<=300000
输出格式:
对于每个 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("%d\n",ans==-1?ans:val[ans]);
128         }
129     }
130 } 






  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
POJ 2987 Firing
树的重心
第一章 作业7.
【左神算法课】超经典:求两单向链表交点(
上一篇文章      下一篇文章      查看所有文章
加:2017-12-05 23:23:29  更:2017-12-05 23:23:35 
 
360图书馆 软件开发资料 购物精选 新闻资讯 Chinese Culture 龙发科技 开发 中国文化 阅读网 日历 万年历 2020年10日历
2020-10-27 10:54:34
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程知识