权值线段树求找错,谢谢TT

回复帖子

@ღ觊觎微凉月 2019-08-17 17:04 回复
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 500000
using namespace std;
int root[maxn],k,fa[maxn],size[maxn],pos[maxn],n,m,q,data[maxn];
char opt;
struct node{
    int l,r,size;
}tree[maxn*16];
int find(int x)
{
    while(x!=fa[x]) x=fa[x]=fa[fa[x]];
    return x;
}
void update(int &id,int l,int r,int pos)
{
    if(!id) id=++k;
    tree[id].size++;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(mid>=pos) update(tree[id].l,l,mid,pos);
    else update(tree[id].r,mid+1,r,pos);
}
void merge(int &now,int &del,int l,int r,int id)
{
    if(id==1358) printf("%d %d\n",l,r);
    if(!now) now=++k;
    if(!del) del=++k;
    if(l==r) {tree[now].size++; return ;}
    int mid=l+r>>1;
    if(tree[tree[del].l].size) merge(tree[now].l,tree[del].l,l,mid,id);
    if(tree[tree[del].r].size) merge(tree[now].r,tree[del].r,mid+1,r,id);
    tree[now].size=tree[tree[now].l].size+tree[tree[now].r].size;
}
void MERGE(int u,int v,int id)
{
    int fx=find(u);
    int fy=find(v);
    if(fx==fy) return;
//  if(size[fx]<size[fy]) swap(fx,fy);
    size[fx]+=size[fy];
    fa[fy]=fx;
    merge(root[fx],root[fy],1,n,id); 
}
int query(int id,int l,int r,int pos)
{
    if(l==r) return l;
    int mid=l+r>>1;
    if(tree[tree[id].l].size>=pos) return query(tree[id].l,l,mid,pos);
    else return query(tree[id].r,mid+1,r,pos-tree[tree[id].l].size);
}
int main()
{
    freopen("data.in","r",stdin);
    freopen("wa.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) fa[i]=i,size[i]=1;
    for(int i=1,temp;i<=n;i++) scanf("%d",&temp),pos[temp]=i,update(root[i],1,n,temp);
    for(int i=1,u,v;i<=m;i++) 
    scanf("%d %d",&u,&v),MERGE(u,v,i);
    scanf("%d",&q);
    for(int i=1,x,y;i<=q;i++)
    {
        scanf("\n%c %d %d",&opt,&x,&y);
        if(opt=='Q') size[find(x)]>=y?printf("%d\n",pos[query(root[find(x)],1,n,y)]):printf("-1\n");
        else MERGE(x,y,i);
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。