社区讨论

蒟蒻打的权值线段树,60分,有一点小问题

P3369【模板】普通平衡树参与者 5已保存回复 11

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@mi6y8lec
此快照首次捕获于
2025/11/20 12:46
4 个月前
此快照最后确认于
2025/11/20 15:28
4 个月前
查看原帖
我用了meld文本比较器。
几千个输出里只有六七个不一样
而且全都比答案大
我个人觉得是前驱后继打错了
前驱的思想是找到比当前更小一位的数字的排名
然后直接输出当前排名的数字
后继是找到当前数字排名,然后输出当前排名+1的数字
求大佬查错
CPP
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int n,tot;
int b[N],q[N],ca[N];
int sum[N<<2],li,ro,vl;
inline int read()
{
    int x=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*w;
}
void update(int l,int r,int rt)
{
    if(r<li||l>ro) return;
    if(li<=l&&r<=ro) {sum[rt]+=vl;return;}
    int mid=(l+r)>>1;
    update(l,mid,rt<<1);
    update(mid+1,r,rt<<1|1);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
int query(int l,int r,int rt)
{
    if(r<li||l>ro) return 0;
    if(li<=l&&r<=ro) return sum[rt];
    int mid=(l+r)>>1;
    return query(l,mid,rt<<1)+query(mid+1,r,rt<<1|1);
}
inline int kth(int k)
{
    int l=1,r=tot,rt=1;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(k<=sum[rt<<1]) r=mid,rt=rt<<1;
        else l=mid+1,k-=sum[rt<<1],rt=rt<<1|1;
    }
    return l;
}
inline int pre(int v)
{
    ro=lower_bound(b+1,b+tot+1,v)-b-1,li=1;
    int num=query(1,tot,1);
    return b[kth(num)];
}
inline int bac(int v)
{
    ro=lower_bound(b+1,b+tot+1,v)-b,li=1;
    int num=query(1,tot,1);
    return b[kth(num+1)];
}
int main()
{
    freopen("1.in","r",stdin);
    freopen("1.ans","w",stdout);
    n=read();
    for(int i=1;i<=n;++i)
    {
        q[i]=read();ca[i]=read();
        if(q[i]!=4) b[++tot]=ca[i];
    }
    sort(b+1,b+tot+1);tot=unique(b+1,b+tot+1)-b-1;
    for(int i=1;i<=n;++i)
    {
        if(q[i]==1) li=lower_bound(b+1,b+tot+1,ca[i])-b,ro=li,vl=1,update(1,tot,1);
        else if(q[i]==2) li=lower_bound(b+1,b+tot+1,ca[i])-b,ro=li,vl=-1,update(1,tot,1);
        else if(q[i]==3) ro=lower_bound(b+1,b+tot+1,ca[i])-b,li=1,printf("%d\n",query(1,tot,1));
        else if(q[i]==4) printf("%d\n",b[kth(ca[i])]);
        else if(q[i]==5) printf("%d\n",pre(ca[i]));
        else printf("%d\n",bac(ca[i]));
    }
}

回复

11 条回复,欢迎继续交流。

正在加载回复...