skywang @ 2019-11-19 20:36:58
//A+B Problem 2019.11.19
//从哪里开始,从哪里结束
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define int long long
using namespace std;
struct tree_point{
int lson,rson,size,heap,v;
}t[400001];
int root=0,cnt=0;
struct son{
int lson,rson;
};
void update(int k){
t[k].size=t[t[k].lson].size+t[t[k].rson].size+1;
}
int Rank(int k,int x){
if (!k) return 0;
int rt=root;
if (x>t[k].v) return Rank(t[k].rson,x)+t[t[k].lson].size+1;
else return Rank(t[k].lson,x);
}/*
int Rank(int k,int x){
int tmp=root,ans=0;
while(tmp){
if(x>t[tmp].v){
ans+=t[t[tmp].lson].size+1;
tmp=t[tmp].rson;
}
else tmp=t[tmp].lson;
}
return ans;
}*/
int merge(int Lson,int Rson){
if (Lson==0) return Rson;
if (Rson==0) return Lson;
if(t[Lson].heap<t[Rson].heap){
t[Lson].rson=merge(t[Lson].rson,Rson);
update(Lson);
return Lson;
}else{
t[Rson].lson=merge(Lson,t[Rson].lson);
update(Rson);
return Rson;
}
}
son cut(int k,int x){
son ans={0,0};
if (k==0) return ans;
if (x>=t[t[k].lson].size+1){
ans=cut(t[k].rson,x-t[t[k].lson].size-1);
t[k].rson=ans.lson;
ans.lson=k;
}else{
ans=cut(t[k].lson,x);
t[k].lson=ans.rson;
ans.rson=k;
}
update(k);
return ans;
}
void ins(int x){
t[++cnt].v=x;
t[cnt].heap=rand();
t[cnt].size=1;
son s=cut(root,Rank(root,x));
int rt=merge(s.lson,cnt);
root=merge(rt,s.rson);
}
void del(int x){
son s=cut(root,Rank(root,x));
son ss=cut(s.rson,1);
root=merge(s.lson,ss.rson);
}
int find(int k,int x){
if (x==t[t[k].lson].size+1) return t[k].v;
if (x<t[t[k].lson].size+1) return find(t[k].lson,x);
if (x>t[t[k].lson].size+1) return find(t[k].rson,x-1-t[t[k].lson].size);
}
int smaller(int x){
son s=cut(root,Rank(root,x));
int tt=find(s.lson,t[s.lson].size);
root=merge(s.lson,s.rson);
return tt;
}
int bigger(int x){
son s=cut(root,Rank(root,x+1));
int tt=find(s.rson,1);
root=merge(s.lson,s.rson);
return tt;
}
signed main(){
int opt=1,x;
for (int i=1;i<=2;i++){
cin>>x;
switch(opt){
case 1:ins(x);break;
case 2:del(x);break;
case 3:cout<<Rank(root,x)+1<<endl;break;
case 4:cout<<find(root,x)<<endl;break;
case 5:cout<<smaller(x)<<endl;break;
case 6:cout<<bigger(x)<<endl;break;
}
}
cout<<find(root,1)+find(root,2)<<endl;
return 0;
}
by X_r_G @ 2020-02-08 10:07:50
走好
by jijidawang @ 2020-02-20 13:54:00
走好
by bigju @ 2020-03-29 14:39:48
这是线段树?
by _lzh_ @ 2021-02-04 17:23:47
这是平衡树?