替罪羊树
y2823774827y
2019-11-24 17:31:03
P3369写了道模板题
- 不需要记录父亲节点
- 替罪羊树查询排名较方便，多利用这个去进行其他操作
- 一次插入时仅重构一个子树
在压行的道路上一去不复返
```cpp
#include<bits/stdc++.h>
typedef int LL;
typedef double dl;
#define opt operator
const LL maxn=1e5+9;
const dl eps=1e-12,pi=acos(-1.0),wyn=0.7;
LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1; c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<3)+(x<<1)+c-'0'; c=getchar();
}return x*f;
}
struct node{
LL v,son[2],size,tag,cnt;
}a[maxn];
LL m,top,nod,root,tmp;
LL cal[maxn];
void Build(LL &nw,LL l,LL r){
if(l>r) return; LL mid(l+r>>1); nw=cal[mid]; a[nw].size=r-l+1; Build(a[nw].son[0],l,mid-1); Build(a[nw].son[1],mid+1,r); a[nw].cnt=a[a[nw].son[0]].cnt+a[a[nw].son[1]].cnt+a[nw].tag;
}
void Recyle(LL &nw){ if(!nw) return; Recyle(a[nw].son[0]); cal[++top]=nw; Recyle(a[nw].son[1]); nw=0; }
void Rebuild(LL &nw){ top=0; Recyle(nw); Build(nw,1,top); }
bool Check(LL &nw){ LL zz(a[nw].size*wyn); if(a[a[nw].son[0]].size>=zz || a[a[nw].son[1]].size>=zz) return true; return false; }
void Insert(LL &nw,LL x){
if(!nw){ nw=++nod; a[nw].size=a[nw].cnt=1; a[nw].v=x; a[nw].tag=1; return; }
a[nw].size++; a[nw].cnt++;
if(a[nw].v>=x) Insert(a[nw].son[0],x);
else Insert(a[nw].son[1],x);
if(Check(nw)) tmp=nw;
}
void Rept(LL &nw,LL x){
if(nw==tmp){
Rebuild(nw); return;
}
if(a[nw].v>=x) Rept(a[nw].son[0],x);
else Rept(a[nw].son[1],x);
}
void Erase(LL &nw,LL x){
--a[nw].cnt;
if(a[nw].tag && a[a[nw].son[0]].cnt==x-1){
a[nw].tag=0; return;
}
if(a[a[nw].son[0]].cnt>=x) Erase(a[nw].son[0],x);
else Erase(a[nw].son[1],x-a[a[nw].son[0]].cnt-a[nw].tag);
}
LL Q_rk(LL nw,LL x){
if(!nw) return 0;
if(a[nw].v>=x) return Q_rk(a[nw].son[0],x);
return a[a[nw].son[0]].cnt+a[nw].tag+Q_rk(a[nw].son[1],x);
}
LL Q_v(LL nw,LL x){
if(a[a[nw].son[0]].cnt+a[nw].tag==x && a[nw].tag) return a[nw].v;
if(a[a[nw].son[0]].cnt>=x) return Q_v(a[nw].son[0],x);
else return Q_v(a[nw].son[1],x-a[a[nw].son[0]].cnt-a[nw].tag);
}
LL Q_pre(LL nw,LL x){ return Q_v(root,Q_rk(root,x)); }
LL Q_nxt(LL nw,LL x){ return Q_v(root,Q_rk(root,x+1)+1); }
int main(){
m=Read();
LL ret(0);
while(m--){
LL op(Read()),x(Read());
switch (op){
case 1:tmp=0; Insert(root,x); if(tmp) Rept(root,x); break;
case 2:Erase(root,Q_rk(root,x)+1); break;
case 3:printf("%d\n",Q_rk(root,x)+1); break;
case 4:printf("%d\n",Q_v(root,x)); break;
case 5:printf("%d\n",Q_pre(root,x)); break;
case 6:printf("%d\n",Q_nxt(root,x)); break;
}
}
return 0;
}
```