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 AFO_9 @ 2019-11-19 20:39:26
走好
by _SeeleVollerei_ @ 2019-11-19 20:43:59
@skywang 泪别
by tobie @ 2019-11-19 20:49:53
你牛,A+B Problem 能写成玄学代码
by 梦里调音 @ 2019-11-19 20:52:43
加油!
by tobie @ 2019-11-19 20:52:44
牛牪犇
by 谬悠 @ 2019-11-19 20:58:14
走好qwq
by QAQQWQ @ 2019-11-19 20:58:53
走好qaq
by ____OccDreamer @ 2019-11-19 21:09:27
走好......
by __wfx @ 2020-01-03 20:17:13
走好
by kkk的脑残粉 @ 2020-01-24 10:46:55
走好