# [HDU3031]To Be Or Not To Be（可并堆，左偏树）

### Description

That's a question. Now Happy (Xi Yangyang) has been caught by Wolffy (Hui Tailang). As Wolffy is busy preparing the big meal, a good idea comes to Happy. He proposes a game that only Wolffy had won, he can eat Happy. Wolffy always believes he is the cleverest one, so they reach a consensus. And they both agree with Wolnie (Hong Tailang) when the referee. A theater will be beat to die by Wolnie's pan.

The game is defined as follow.
There are multiple test cases.
In each case there are R (R < 10) rounds of the game, R is an odd number to guarantee that there must be a winner in the end.
In each round: There is a pile of n (10 <= n <= 200) Special-cards and m (1 <= m <= 100) piles of Point-card on the table. The Point-card piles are ordered from 1 to m. Wolffy and Happy take turns to get one card from the top of Special-cards pile. Wolffy always takes first in the game. When all the Special-cards have been taken, the round is over and the one with more cards in the hands gains one point. If there is a tie, Wolffy gains one point.(Wolffty and Happy both have 0 point before the game).
There are 5 kinds of Special-cards besides the Point-card in the game.
0) Point-card: a card with a point X (1 <= X <= 2000000).
1) Challenge-card: no matter who takes this card, they both take one card with the maximum point from their own hands. After a comparison, if Happy's card has a larger point, He takes all the Wolffy's in-hands cards, vice versa; If there is a tie no more operation.
2) Loss-card: the one who takes this card, He must throw a card with the maximum point.
3) Add-card: a card with P point, the one who gets this card will make the card with maximum point P point larger, i.e. if a Point-card with X point is the maximum, its point will change to X + P. An Add-card can only work on one Point-card.
4) Exchange-card: a card with Q point. The one who gets this card must change one maximum-point card's point to Q.
5) Take-card: a card with a integer K, indicates one can get the all the cards of Kth Point-card pile. In one round no two Take-card have the same K.
You can assume that when one gets the Loss-card, Add-card, Exchange-card, He has at least one card in the hands, when one gets a Challenge-card, they both have at least one card in the hands.

HDU

## 题目大意

$$Challenge-card$$，不管是谁抽到这一张，将两人分别数值最大的卡牌比较，分值大的一方获得另一方的所有卡牌。
$$Loss-card$$，抽到这一张卡牌的人要弃掉他分值最大的卡牌。
$$Add-card$$，抽到这一张卡牌的人将他分值最大的卡牌加上$$Add-card$$上对应的数值。
$$Exchange-card$$，抽到这一张卡牌的人将他分值最大的卡牌的分值变成$$Exchange-card$$上对应的分值。
$$Take-card$$，抽到这一张卡牌的人获得$$Take-card$$上数值对应的第几堆分值卡牌。

## 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100*10000+100;
const int inf=2147483647;

class Heap
{
public:
int key;
int ls,rs,dis;
void init(){
ls=rs=dis=0;return;
}
};

int R;
int n,m,Pile[maxN],Pnum[maxN];//Pile维护第i堆分值卡牌对应在可并堆中的堆顶，Pnum维护第i堆分值卡牌中卡牌的数量。
Heap H[maxN];//左偏树

int Merge(int r1,int r2);

int main()
{
ios::sync_with_stdio(false);
while (cin>>R)
{
int hap=0,wof=0;//统计两人的得分
while (R--)
{
int nodecnt=0;mem(Pile,0);
cin>>n>>m;
for (int i=1;i<=m;i++) cin>>Pnum[i];//输入，并把每一堆初始分值卡牌构造成堆的形式
for (int i=1;i<=m;i++)
for (int j=1;j<=Pnum[i];j++)
{
++nodecnt;H[nodecnt].init();
cin>>H[nodecnt].key;
Pile[i]=Merge(Pile[i],nodecnt);
}
int Id[3];Id[1]=Id[2]=0;//记录两个人当前手中牌的堆顶
int Size[3];Size[1]=Size[2]=0;//记录两人手中当前牌的数量
for (int now=1;now<=n;now++)
{
int pl=(now-1)%2+1;//当前操作的人
char opt;cin>>opt;
if (opt=='T')//Take-card
{
int kth;cin>>kth;
Id[pl]=Merge(Id[pl],Pile[kth]);
Size[pl]+=Pnum[kth];
}
if (opt=='C')//Challenge-card
{
if (H[Id[2]].key>H[Id[1]].key){
Id[2]=Merge(Id[1],Id[2]);Id[1]=0;
Size[2]+=Size[1];Size[1]=0;
}
else if (H[Id[1]].key>H[Id[2]].key){
Id[1]=Merge(Id[1],Id[2]);Id[2]=0;
Size[1]+=Size[2];Size[2]=0;
}
}
if (opt=='L'){//Lost-card
Id[pl]=Merge(H[Id[pl]].ls,H[Id[pl]].rs);Size[pl]--;
}
int key;cin>>key;H[Id[pl]].key+=key;
}
if (opt=='E')//Exchange-card
{
int key;cin>>key;
int id=Id[pl];Id[pl]=Merge(H[Id[pl]].ls,H[Id[pl]].rs);
H[id].key=key;Id[pl]=Merge(Id[pl],id);
}
}
printf("%d:%d\n",Size[1],Size[2]);
if (Size[1]>=Size[2]) wof++;
else hap++;
}
if (wof>hap) printf("Hahaha...I win!!\n");
else printf("I will be back!!\n");
}
return 0;
}

int Merge(int r1,int r2)
{
if (r1==0) return r2;
if (r2==0) return r1;
if (H[r1].key<H[r2].key) swap(r1,r2);
H[r1].rs=Merge(H[r1].rs,r2);
if (H[H[r1].ls].dis<H[H[r1].rs].dis) swap(H[r1].ls,H[r1].rs);
if (H[r1].rs) H[r1].dis=H[H[r1].rs].dis+1;
else H[r1].dis=0;
return r1;
}


HNCJ OIer