社区讨论
蒟蒻打的权值线段树,60分,有一点小问题
P3369【模板】普通平衡树参与者 5已保存回复 11
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 11 条
- 当前快照
- 1 份
- 快照标识符
- @mi6y8lec
- 此快照首次捕获于
- 2025/11/20 12:46 4 个月前
- 此快照最后确认于
- 2025/11/20 15:28 4 个月前
我用了meld文本比较器。
几千个输出里只有六七个不一样
而且全都比答案大
我个人觉得是前驱后继打错了
前驱的思想是找到比当前更小一位的数字的排名
然后直接输出当前排名的数字
后继是找到当前数字排名,然后输出当前排名+1的数字
求大佬查错
CPP几千个输出里只有六七个不一样
而且全都比答案大
我个人觉得是前驱后继打错了
前驱的思想是找到比当前更小一位的数字的排名
然后直接输出当前排名的数字
后继是找到当前数字排名,然后输出当前排名+1的数字
求大佬查错
#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 条回复,欢迎继续交流。
正在加载回复...