求助,线段树合并RE

回复帖子

@S1rius  2019-01-28 16:23 回复

样例第二个询问RE,找了半天不知道为什么QAQ

#include <bits/stdc++.h>
using namespace std;
int const N=1e5+1;
int fa[N],ans[N];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
struct node
{
    int sum;
    node *ls,*rs;
}*root[N];
void modify(node* &x,int l,int r,int a,int b)
{
    if(x==NULL)x=new node();
    x->sum+=b;
    if(l==r)return;
    int mid=(l+r)/2;
    if(a<=mid)modify(x->ls,l,mid,a,b);
    else modify(x->rs,mid+1,r,a,b);
}
void merge(node* &x,node* &y,int l,int r)
{
    if(y==NULL)return;
    if(x==NULL)x=new node();
    x->sum+=y->sum;
    if(l==r)
    {
        delete y;
        return;
    }
    int mid=(l+r)/2;
    merge(x->ls,y->ls,l,mid);
    merge(x->rs,y->rs,mid+1,r);
    delete y;
}
int ask(node* &x,int l,int r,int a,int b)
{
    if(l>=a&&r<=b)return x->sum;
    int mid=(l+r)/2,ans=0;
    if(a<=mid)ans+=ask(x->ls,l,mid,a,b);
    if(b>mid)ans+=ask(x->rs,mid+1,r,a,b);
    return ans;
}
int getans(node* &x,int l,int r,int k)
{
    if((x->ls==NULL)&&(x->rs==NULL))cout<<l<<" "<<r<<" "<<k<<endl;
    if((x->sum)<k)return 0;
    int mid=(l+r)/2;
    if((x->ls->sum)>=k)return getans(x->ls,l,mid,k);
    else return getans(x->rs,mid+1,r,(k-(x->ls->sum)));
}
int main()
{
    int n,m,q,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        modify(root[i],1,n,x,1);
        ans[x]=i;
    }
    for(int i=1;i<=n;i++)fa[i]=i;
    ans[0]=-1;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        int fx=find(x),fy=find(y);
        if(fx!=fy)fa[fy]=fx,merge(root[fx],root[fy],1,n);
        //printf("%d\n",ask(root[fx],1,n,1,n));
    }
    scanf("%d",&q);
    char c;
    for(int i=1;i<=q;i++)
    {
        cin>>c>>x>>y;
        if(c=='B')
        {
            int fx=find(x),fy=find(y);
            if(fx!=fy)fa[fy]=fx,merge(root[fx],root[fy],1,n);
            //printf("%d\n",ask(root[fx],1,n,1,n));
        }
        else
        {
            //printf("%d %d ",find(x),ask(root[find(x)],1,n,1,n));
            printf("%d\n",ans[getans(root[find(x)],1,n,y)]);
        }
    }
    return 0;
 } 
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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