注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

neverland 完整版  

2013-11-28 20:18:21|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
知道了线段树合并
当年的一个大坑也就完结了
http://ydcydcy1.blog.163.com/blog/static/21608904020131951136986/
写起来非常轻松顺手
两天连挖两坑的感觉实在是爽

感觉那个时候的自己和现在真的有很多的不同呢
那时比现在自信多了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 100010
using namespace std;
struct Node
{
Node *lc,*rc;
int size;
}*Root[maxn];
Node* Insert(int l,int r,int x)
{
Node *p=new Node;
p->size=1,p->lc=0,p->rc=0;
if(l==r)
return p;
int mid=(l+r)>>1;
if(x<=mid)
p->lc=Insert(l,mid,x);
else
p->rc=Insert(mid+1,r,x);
return p;
}
Node* merge(Node* a,Node *b)
{
if(a==0)
return b;
if(b==0)
return a;
Node *p=new Node;
p->size=a->size+b->size;
p->lc=merge(a->lc,b->lc),p->rc=merge(a->rc,b->rc);
return p;
}
int Query(Node *p,int l,int r,int k)
{
if(l==r)
return l;
int s=p->lc?p->lc->size:0,mid=(l+r)>>1;
if(s>=k)
return Query(p->lc,l,mid,k);
else
return Query(p->rc,mid+1,r,k-s);
}
int n,father[maxn],id[maxn];
void Read(int &digit)
{
digit=0;
char c;
for(c=getchar();(c<'0'||c>'9');c=getchar());
for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
}
int Find(int p)
{
if(father[p]!=p)
father[p]=Find(father[p]);
return father[p];
}
void read()
{
int m;
Read(n),Read(m);
for(int i=1,p;i<=n;++i)
{
Read(p);
Root[i]=Insert(1,n,p);
father[i]=i,id[p]=i;
}
for(int i=1,a,b;i<=m;++i)
{
Read(a),Read(b);
a=Find(a),b=Find(b);
if(a==b)
continue;
father[a]=b,Root[b]=merge(Root[b],Root[a]);
}
}
void Query()
{
int m;
Read(m);
char task[3];
for(int i=1,a,b;i<=m;++i)
{
scanf("%s",task+1);
Read(a),Read(b);
if(task[1]=='Q')
{
int x=Find(a);
if(Root[x]->size<b)
printf("-1\n");
else
printf("%d\n",id[Query(Root[x],1,n,b)]);
}
else
{
a=Find(a),b=Find(b);
if(a==b)
continue;
father[a]=b,Root[b]=merge(Root[b],Root[a]);
}
}
}
int main()
{
read();
Query();
return 0;
}



  评论这张
 
阅读(300)| 评论(4)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017