权值线段树 WA37求调
查看原帖
权值线段树 WA37求调
305928
zhoumurui楼主2024/7/27 14:35

发现这个题可以用权值线段树做,就写了一个,结果挂了

#include<bits/stdc++.h>
#define int long long
#define ls t[rt].lson
#define rs t[rt].rson
using namespace std;
struct node{
    int l,r,lson,rson,sum;
}t[5000005];
int idx;
void build(){
    idx=1;
    t[1].l=-1e7,t[1].r=1e7;
}
void pushup(int rt){
    t[rt].sum=t[ls].sum+t[rs].sum;
}
void add(int rt,int k){
    if (t[rt].l>k||t[rt].r<k)return;
    if (t[rt].l==k&&t[rt].r==k){
        t[rt].sum++;
        return;
    }
    if (!ls){
        ls=++idx;
        int mid=floor((double)(t[rt].l+t[rt].r)/2.0);
        t[ls].l=t[rt].l;
        t[ls].r=mid;
        rs=++idx;
        t[rs].l=mid+1;
        t[rs].r=t[rt].r;
    }
    add(ls,k);
    add(rs,k);
    pushup(rt);
}
void del(int rt,int k){
    if (t[rt].l>k||t[rt].r<k)return;
    if (t[rt].l==k&&t[rt].r==k){
        t[rt].sum--;
        return;
    }
    if (!ls){
        return;
    }
    del(ls,k);
    del(rs,k);
    pushup(rt);
}
int query(int rt,int l,int r){
    if (t[rt].l>r||t[rt].r<l)return 0;
    if (t[rt].l>=l&&t[rt].r<=r){
        return t[rt].sum;
    }
    if (!ls){
        return 0;
    }
    return query(ls,l,r)+query(rs,l,r);
}
int grank(int rt,int k){
    if (t[rt].sum<k)return -1;
    if (t[rt].l==t[rt].r)return t[rt].l;
    if (t[ls].sum>=k)return grank(ls,k);
    else return grank(rs,k-t[ls].sum);
}
int qq(int k){
    int t=query(1,-1e7,k-1);
    return grank(1,t);
}
int hj(int k){
    int t=query(1,-1e7,k);
    return grank(1,t+1);
}
signed main(){
    int n;
    cin>>n;
    build();
    for (int i=1;i<=n;i++){
        int op,x;
        cin>>op>>x;
        switch(op){
            case 1:
            add(1,x);
            break;
            case 2:
            add(2,x);
            break;
            case 3:
            cout<<query(1,-1e7,x-1)+1<<endl;
            break;
            case 4:
            cout<<grank(1,x)<<endl;
            break;
            case 5:
            cout<<qq(x)<<endl;
            break;
            case 6:
            cout<<hj(x)<<endl;
        }
    }
    return 0;
}
2024/7/27 14:35
加载中...