题解 P2073 【送花】
YoungNeal
2018-05-06 09:39:19
## Solution
$\mathcal{fhq-Treap}$ 了解一下
$\mathcal{fhq-Treap}$ 入门可以看我的这篇[博客](http://www.cnblogs.com/YoungNeal/p/8977328.html)
讲一下这题怎么搞
对于插入操作，假设权值为 $\mathcal{k}$。我们按照权值先 $\mathcal{split}$ 出小于等于 $\mathcal{k}$ 的一棵树 $\mathcal{x}$，再把 $\mathcal{x}$ $\mathcal{split}$ 出小于等于 $\mathcal{k-1}$ 的一棵树 $\mathcal{y}$。如果 $\mathcal{y}$ 这棵子树不为空，也就是说已经有了权值为 $\mathcal{k}$ 的节点，那么我们不插入即可。
对于删除操作，我们可以按照子树大小 $\mathcal{split}$ 出我们要删除的值，然后不 $\mathcal{merge}$ 即可。
最后 $\mathcal{dfs}$ 一遍求出答案即可。
最慢的点 $\mathcal{30ms}$，比 $\mathcal{STL}$ 快了不知道多少。
## Code
```cpp
#include<cstdio>
#include<cstdlib>
#define N 100005
#define int long long
int tot,Root;
int ans1,ans2;
int beauty[N];
int val[N],sze[N];
int ch[N][2],prio[N];
void pushup(int o){
sze[o]=sze[ch[o][0]]+sze[ch[o][1]]+1;
}
void split(int o,int k,int &x,int &y){
if(!o) x=y=0;
else{
if(sze[ch[o][0]]>=k){
y=o;
split(ch[o][0],k,x,ch[o][0]);
pushup(o);
}
else{
x=o;
split(ch[o][1],k-sze[ch[o][0]]-1,ch[o][1],y);
pushup(o);
}
}
}
int merge(int x,int y){
if(!x or !y) return x+y;
if(prio[x]<prio[y]){
ch[x][1]=merge(ch[x][1],y);
pushup(x);
return x;
}
else{
ch[y][0]=merge(x,ch[y][0]);
pushup(y);
return y;
}
}
void split2(int o,int k,int &x,int &y){
if(!o) x=y=0;
else{
if(val[o]<=k){
x=o;
split2(ch[o][1],k,ch[o][1],y);
} else{
y=o;
split2(ch[o][0],k,x,ch[o][0]);
}
pushup(o);
}
}
int newnode(int a,int b){
sze[++tot]=1;
prio[tot]=rand();
beauty[tot]=a;
val[tot]=b;
return tot;
}
void insert(int o,int a,int b){
int x,y,z;
split2(Root,b,x,y);
split2(x,b-1,x,z);
if(sze[z]!=0)
Root=merge(x,merge(z,y));
else
Root=merge(x,merge(newnode(a,b),y));
}
void delex(){
int siz=sze[Root];
int a;
split(Root,siz-1,Root,a);
}
void delch(){
int a;
split(Root,1,a,Root);
}
void dfs(int now){
//printf("now=%d\n",now);
if(!now) return;
ans1+=beauty[now];
ans2+=val[now];
dfs(ch[now][0]);
dfs(ch[now][1]);
}
signed main(){
int opt,a,b;
while(scanf("%lld",&opt)){
if(opt==-1) break;
if(opt==1){
scanf("%lld%lld",&a,&b);
insert(Root,a,b);
}
if(opt==2)
delex();
if(opt==3)
delch();
}
dfs(Root);
printf("%lld %lld\n",ans1,ans2);
return 0;
}
```