题解 P2073 【送花】

斯德哥尔摩

2017-12-07 23:34:26

Solution

啊,身为只是拿到了省一的蒟蒻,我,经过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;//终于打完了(累死我了。。。) } ```