https://www.luogu.org/record/25243849
by 取啥名好 @ 2019-10-15 21:17:25
您先开大数组试试
by Sweetie_Liu @ 2019-10-15 21:28:49
@[取啥名好](/space/show?uid=173397) 我先帮您调着
by Sweetie_Liu @ 2019-10-15 21:29:32
orz tql 表示至今只会splay
by 莫奈的崖径 @ 2019-10-15 21:37:12
@[神风OI队](/space/show?uid=165030) 开了十倍，应该不是这个问题
by 取啥名好 @ 2019-10-15 21:40:13
@[神风OI队](/space/show?uid=165030) 您要是调出来了代码放一下就好（没调出来也没事毕竟麻烦您了）
by 取啥名好 @ 2019-10-15 21:50:11
***昨天有点事没调，今天给您调了一个小时可算是过了***
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,tot=0,root=0,zz_temp=0;
int temp[5000001]={0},cnt[5000001]={0};
struct node{
int son[2],val,sum,re_sum;//re_sum?????,sum?val?????????
}poi[5000001];
void dfs(int now){
if(poi[now].son[0])dfs(poi[now].son[0]);
if(poi[now].sum) zz_temp++,temp[zz_temp]=now,cnt[zz_temp]=poi[now].sum;
if(poi[now].son[1])dfs(poi[now].son[1]);
}//???????????
void build(int l,int r,int &now){
if(l>r){
now = 0;
return;
}
int mid=(l+r)>>1;
now=temp[mid];
poi[now].sum=cnt[mid];
if(l==r){
poi[now].son[0]=poi[now].son[1]=0;
poi[now].re_sum=poi[now].sum;
return ;
}//????
if(l<mid) build(l,mid-1,poi[now].son[0]);
else poi[now].son[0]=0;
if(r>mid) build(mid+1,r,poi[now].son[1]);
else poi[now].son[1]=1;
poi[now].re_sum=poi[poi[now].son[0]].re_sum+poi[poi[now].son[1]].re_sum+poi[now].sum;
}
void rebuild(int &now){
zz_temp=0;
dfs(now);
if(zz_temp)
build(1,zz_temp,now);
else now = 0;
}
bool unbalance(int x){
return poi[x].re_sum*3<=max(poi[poi[x].son[0]].re_sum,poi[poi[x].son[1]].re_sum)*4;//????
}
/*
void insert(int &now,int x){
if(!now){
tot++;
now=tot;
poi[tot].val=x;
poi[tot].sum=poi[tot].re_sum=1;
return ;
}//??????
poi[now].re_sum++;
if(x==poi[now].val) {
poi[now].sum++;
return ;//????
}
insert(poi[now].son[x>poi[now].val],x);
if(unbalance(now)) rebuild(now);
}
*/
/*
???????root??????,?????????
????????????
EG:
????????,???????????,????????????,??????????
*/
void insert(int &now,int x,int flag){
if(!now){
tot++;
now = tot;
poi[tot].val = x;
poi[tot].sum = poi[tot].re_sum = 1;
return;
}
poi[now].re_sum ++;
if(x==poi[now].val){
poi[now].sum++;
return;
}
if(unbalance(now)) insert(poi[now].son[x>poi[now].val],x,flag|1);
else insert(poi[now].son[x>poi[now].val],x,flag|0);
if(unbalance(now)&&flag==0)rebuild(now);
}
int where(int x){//x???
int now=root,ans=1;
while(now){
// cout<<now<<endl;
if(poi[now].val==x){
// if(poi[now].sum)
ans+=poi[poi[now].son[0]].re_sum;
break;//??????
}
else if(x<poi[now].val) now=poi[now].son[0];
else if(x>poi[now].val) ans += poi[now].sum+poi[poi[now].son[0]].re_sum,now=poi[now].son[1];//?????????
}
return ans;
}
int find(int x){//???x
int now=root;
while(now){
if(poi[poi[now].son[0]].re_sum+poi[now].sum>=x&&x>poi[poi[now].son[0]].re_sum) return poi[now].val;//????
else if(poi[poi[now].son[0]].re_sum>=x) now=poi[now].son[0];
else{
x-=poi[poi[now].son[0]].re_sum+poi[now].sum;
now=poi[now].son[1];
}//??????
}
}
int upper(int x){
return find(where(x+1));
}
int lower(int x){
return find(where(x)-1);
}
void Mid(int x){
if(poi[x].son[0])Mid(poi[x].son[0]);
if(poi[x].sum==0)printf("QAQ\n");
if(poi[x].son[1])Mid(poi[x].son[1]);
}
void destory(int x){
int now=root;//flag = 0;
while(now){
poi[now].re_sum--;
if(poi[now].val==x&&poi[now].sum){
poi[now].sum--;
break;
}
now=poi[now].son[poi[now].val<x];
}//????
// rebuild(flag);
// Mid(root);
}
int read(){
int w=1,x=0,ch=getchar();
for(; ch<'0'||ch>'9'; ch=getchar())if(ch=='-')w=-1;
for(; ch>='0'&&ch<='9'; ch=getchar())x=x*10+ch-'0';
return x*w;
}
int main(){
// freopen("nb.in","r",stdin);
// freopen("nb.out","w",stdout);
n = read();
for(int i=1,a,b;i<=n;i++){
a = read(),b = read();
if(a==1) insert(root,b,0);
if(a==2) destory(b);
if(a==3) printf("%d\n",where(b));
if(a==4) printf("%d\n",find(b));
if(a==5) printf("%d\n",lower(b));
if(a==6) printf("%d\n",upper(b));
}
return 0;
}
```
by Sweetie_Liu @ 2019-10-16 07:50:29
@ 取啥名好
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,tot=0,root=0,zz_temp=0;
int temp[5000001]={0},cnt[5000001]={0};
struct node{
int son[2],val,sum,re_sum;//re_sum?????,sum?val?????????
}poi[5000001];
void dfs(int now){
if(poi[now].son[0])dfs(poi[now].son[0]);
if(poi[now].sum) zz_temp++,temp[zz_temp]=now,cnt[zz_temp]=poi[now].sum;
if(poi[now].son[1])dfs(poi[now].son[1]);
}//???????????
void build(int l,int r,int &now){
if(l>r){
now = 0;
return;
}
int mid=(l+r)>>1;
now=temp[mid];
poi[now].sum=cnt[mid];
if(l==r){
poi[now].son[0]=poi[now].son[1]=0;
poi[now].re_sum=poi[now].sum;
return ;
}//????
if(l<mid) build(l,mid-1,poi[now].son[0]);
else poi[now].son[0]=0;
if(r>mid) build(mid+1,r,poi[now].son[1]);
else poi[now].son[1]=1;
poi[now].re_sum=poi[poi[now].son[0]].re_sum+poi[poi[now].son[1]].re_sum+poi[now].sum;
}
void rebuild(int &now){
zz_temp=0;
dfs(now);
if(zz_temp)
build(1,zz_temp,now);
else now = 0;
}
bool unbalance(int x){
return poi[x].re_sum*3<=max(poi[poi[x].son[0]].re_sum,poi[poi[x].son[1]].re_sum)*4;//????
}
/*
/*
void insert(int &now,int x){
if(!now){
tot++;
now=tot;
poi[tot].val=x;
poi[tot].sum=poi[tot].re_sum=1;
return ;
}//找不到就新建
poi[now].re_sum++;
if(x==poi[now].val) {
poi[now].sum++;
return ;//找到就插
}
insert(poi[now].son[x>poi[now].val],x);
if(unbalance(now)) rebuild(now);
}
*/
/*
应该重构最靠近root的不平衡子树，否则复杂度不正确。
多段重构您就直接爆炸了。
EG：
我们在这里不平衡，到父节点之后仍然不平衡，您在父节点重构一次就完事，您这样写要重构两次。
*/
void insert(int &now,int x,int flag){
if(!now){
tot++;
now = tot;
poi[tot].val = x;
poi[tot].sum = poi[tot].re_sum = 1;
return;
}
poi[now].re_sum ++;
if(x==poi[now].val){
poi[now].sum++;
return;
}
if(unbalance(now)) insert(poi[now].son[x>poi[now].val],x,flag|1);
else insert(poi[now].son[x>poi[now].val],x,flag|0);
if(unbalance(now)&&flag==0)rebuild(now);
}
int where(int x){//x???
int now=root,ans=1;
while(now){
// cout<<now<<endl;
if(poi[now].val==x){
// if(poi[now].sum)
ans+=poi[poi[now].son[0]].re_sum;
break;//??????
}
else if(x<poi[now].val) now=poi[now].son[0];
else if(x>poi[now].val) ans += poi[now].sum+poi[poi[now].son[0]].re_sum,now=poi[now].son[1];//?????????
}
return ans;
}
int find(int x){//???x
int now=root;
while(now){
if(poi[poi[now].son[0]].re_sum+poi[now].sum>=x&&x>poi[poi[now].son[0]].re_sum) return poi[now].val;//????
else if(poi[poi[now].son[0]].re_sum>=x) now=poi[now].son[0];
else{
x-=poi[poi[now].son[0]].re_sum+poi[now].sum;
now=poi[now].son[1];
}//??????
}
}
int upper(int x){
return find(where(x+1));
}
int lower(int x){
return find(where(x)-1);
}
void Mid(int x){
if(poi[x].son[0])Mid(poi[x].son[0]);
if(poi[x].sum==0)printf("QAQ\n");
if(poi[x].son[1])Mid(poi[x].son[1]);
}
void destory(int x){
int now=root;//flag = 0;
while(now){
poi[now].re_sum--;
if(poi[now].val==x&&poi[now].sum){
poi[now].sum--;
break;
}
now=poi[now].son[poi[now].val<x];
}//????
// rebuild(flag);
// Mid(root);
}
int read(){
int w=1,x=0,ch=getchar();
for(; ch<'0'||ch>'9'; ch=getchar())if(ch=='-')w=-1;
for(; ch>='0'&&ch<='9'; ch=getchar())x=x*10+ch-'0';
return x*w;
}
int main(){
// freopen("nb.in","r",stdin);
// freopen("nb.out","w",stdout);
n = read();
for(int i=1,a,b;i<=n;i++){
a = read(),b = read();
if(a==1) insert(root,b,0);
if(a==2) destory(b);
if(a==3) printf("%d\n",where(b));
if(a==4) printf("%d\n",find(b));
if(a==5) printf("%d\n",lower(b));
if(a==6) printf("%d\n",upper(b));
}
return 0;
}
```
by Sweetie_Liu @ 2019-10-16 07:52:17
@[取啥名好](/space/show?uid=173397)
我看了一遍录像。
总结一下。
我只改了您子树的重构。
然后发现，您是死循，我和您的平衡树的写法战斗了40min，之后我发现，您的where加了poi[x].sum!=0时，如果我们的数被删了我们就不会再进入任何的if。这种情况会出现在查询前驱和后继时。把poi[x].sum!=0删了之后，代码的正确性时可以保证的，显然在查kth时题目保证的，无论您这个东西是否被插入过或是否被删除，我们都是求得比这个小的数，所以直接加上leftsize即可。
by Sweetie_Liu @ 2019-10-16 08:11:49
@[神风OI队](/space/show?uid=165030) 万分感谢
by 取啥名好 @ 2019-10-16 12:35:24