题解 P2073 【送花】
斯德哥尔摩
2017-12-07 23:34:26
啊,身为只是拿到了省一的蒟蒻,我,经过4天的艰苦奋战,终于A了此题。。。
按捺不住内心喜悦,给后来人一个借鉴
经典 平衡树 问题,用 Treap 或 Splay 都可以。
第一天:(RE 0)\*4
第二天:(RE 0)\*2+(RE 60)\*2
第三天:(WA 0)\*2+(WA 40)\*3
第四天:(WA 0)\*1+(WA 40)\*1+(AC 100)\*1
实在是丧心病狂的题目。。。
注意:
1.不要将 操作2 与 操作3 弄反,题目有毒。。。
2.每种价格的花只有一个。。。
结构体指针型 Treap ,貌似没有人写,来一发。。。(奇丑无比)
每个节点维护:本身的价格,美丽值,子树的价格和值,美丽值和值,两个儿子节点
之后就是套模板,改一改就好了。
附上苦心敲出的AC代码:
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
struct node{
node* son[2];
int v,data,sum1,sum2,w;
node(){//节点初始化
son[0]=son[1]=NULL;
w=rand();
v=data=sum1=sum2=0;
}
};
node* rt;
inline int read(){//读优。。。
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void maintain(node* &u){//结点维护
u->sum1=u->v;u->sum2=u->data;
if(u->son[0]!=NULL){//第一天忘了判断,RE 。。。
u->sum1+=u->son[0]->sum1;
u->sum2+=u->son[0]->sum2;
}
if(u->son[1]!=NULL){
u->sum1+=u->son[1]->sum1;
u->sum2+=u->son[1]->sum2;
}
}
void turn(node* &u,int f){//旋转
node* t=u->son[f^1];
u->son[f^1]=t->son[f];
t->son[f]=u;
maintain(u);
maintain(t);
u=t;
}
bool insert(node* &u,int w,int c){//插入
if(u==NULL){
u=new node;
u->v=c;u->data=w;
maintain(u);//第三天忘了维护,WA 40 。。。
return true;
}
else if(u->v==c)return false;//判重
int y=c>u->v?1:0;
bool f=insert(u->son[y],w,c);
if(u->son[y]->w>u->w)turn(u,y^1);
if(u!=NULL)maintain(u);
return f;
}
void remove(node* &u,int x,int y){//删除
if(u==NULL)return;
if(u->v==x){
if(u->son[0]==NULL&&u->son[1]==NULL)u=NULL;
else if(u->son[0]!=NULL&&u->son[1]!=NULL){
if(u->son[0]->w>u->son[1]->w){
turn(u,1);
remove(u->son[1],x,y);
}
else{
turn(u,0);
remove(u->son[0],x,y);
}
}
else{
if(u->son[0]==NULL)u=u->son[1];
else u=u->son[0];
}
if(u!=NULL)maintain(u);
return;
}
u->sum1-=x;u->sum2-=y;
if(x<u->v)remove(u->son[0],x,y);
else if(x>u->v)remove(u->son[1],x,y);
if(u!=NULL)maintain(u);
}
void find(node* u,int k,int &x,int &y){//查询
if(k)while(u->son[0]!=NULL)u=u->son[0];
else while(u->son[1]!=NULL)u=u->son[1];
x=u->v;y=u->data;
}
int main(){
srand(987);//随机种子
int x,y,z,m=0;
while(1){
scanf("%d",&x);
if(x==-1)break;
if(x==1){
scanf("%d%d",&y,&z);
if(insert(rt,y,z))m++;
continue;//感觉这样好低端,然而能过就行了。。。
}
if(m==0)continue;//第二天没有这句,WA 60 。。。
m--;
find(rt,(x==3?1:0),y,z);
remove(rt,y,z);
}
if(rt==NULL)printf("0 0\n");//第二天也忘了这句,RE 0 。。。
else printf("%d %d\n",rt->sum2,rt->sum1);
return 0;//终于打完了(累死我了。。。)
}
```