求助,权值线段树过不了样例

回复帖子

@nofind 2019-05-02 15:06 回复
#include<bits/stdc++.h>
using namespace std;
#define ls(_o) (tree[_o].lc)
#define rs(_o) (tree[_o].rc)
const int maxn=100010;
struct seg
{
    int lc,rc;
    int sum;
}tree[maxn<<10];
int n,m,q,tot;
int val[maxn],id[maxn],root[maxn],fa[maxn];
char op[3];
int get(int x)
{
    return fa[x]==x?x:fa[x]=get(fa[x]);
}
void up(int p)
{
    tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum;
}
void insert(int &p,int l,int r,int d)
{
    if(!p) p=++tot;
    if(l==r)
    {
        tree[p].sum++;
        return;
    }
    int mid=(l+r)>>1;
    if(d<=mid) insert(ls(p),l,mid,d);
    else insert(rs(p),mid+1,r,d);
    up(p); 
}
int merge(int p,int q)
{
    if(!p||!q) return p+q;
    ls(p)=merge(ls(p),ls(q));
    rs(p)=merge(rs(p),rs(q));
    up(p);
    return p;
}
int query(int p,int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(tree[ls(p)].sum>=k) return query(ls(p),l,mid,k);
    else return query(rs(p),mid+1,r,k-tree[ls(p)].sum);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
    }
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        id[val[i]]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        int p=get(u),q=get(v);
        if(p!=q) fa[p]=q; 
    }
    for(int i=1;i<=n;i++)
        insert(root[get(i)],1,n,val[i]);
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%s",op);
        if(op[0]=='Q')
        {
            int x,k;
            scanf("%d%d",&x,&k);
            int p=get(x);
            if(tree[root[p]].sum<k)
            {   
                printf("-1\n");
                continue;
            }
            int t=query(root[p],1,n,k);
            printf("%d\n",id[t]); 
        }
        else
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int p=get(x),q=get(y);
            if(p!=q)
                fa[p]=q,merge(root[p],root[q]);
        }
    }
    return 0;
}

过不了样例,求挑错。

@i207M 2019-05-02 20:20 回复 举报

!?连样例都没过,手玩查错啊。这都不能自己调,考试时怎么办

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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