第二十三届全国信息学奥林匹克竞赛
NOI 2006
第一试

题目名称	生日快乐
可执行文件名	happybirthday
输入文件名	N/A
输出文件名	N/A
时限	4 秒
测试点数目	10
每测试点分值	10
是否有部分分	无
题目类型	交互

生日快乐

【任务描述】

今天是栋栋的生日，他邀请了N 个好友参加Party 。朋友们都知道，栋栋最喜欢吃果冻。因此, 每个朋友带来的生日礼物全是一包果冻.。

在每个朋友送他一包果冻的同时，栋栋还要这个朋友送他一个幸运号码L（1 ≤ L ≤ N）。然后栋栋会先把这包果冻放在一旁，并且把之前的所有果冻包按照果冻的数量从小到大排序（如果果冻数量相等，先后顺序任意）。接着，栋栋再把当前这包果冻插入到有序的果冻包队列中，使得这个队列仍然有序（如果存在其他的果冻包与该果冻包数量相等，则把该果冻包放在它们的前面）。完成这个操作后，栋栋就会进行如下操作：

“如果这个朋友是男生，栋栋会从他送的包的后一个包开始向后数L 个（该朋友的幸运号码），从那个包里取出一个果冻，吃掉。

“如果这个朋友是女生，栋栋会从她送的包的前一个包开始向前数L 个（该朋友的幸运号码），从那个包里取出一个果冻，吃掉。

栋栋实在是太粗心了，以至于他收完所有的礼物后，都不知道吃过哪些朋友的果冻，现在，他希望你帮他一下，当他每吃一个果冻后马上告诉他可能吃的是谁送的(由于排序不是确定的，所以栋栋只要你给他一种可能的答案就行了)。

这是一个交互式的题目，你必须调用库函数来完成所有操作而不能访问任何文件。

【数据规模和约定】

对于所有的数据，我们保证：1 ≤ n ≤ 500000，0 ≤ count ≤ 10^8 ，1 ≤ luckynumber ≤ n.在测试时，你的数据也应该满足我们的数据范围，否则有可能运行异常。

【题解】

平衡树的的典型应用。我这里对SBT(Size Balanced Tree)进行2处改写来做这题：首先是在Insert过程中返回插入节点的秩，这是一个顺便的改动，非常简单；再就是在Delete和Select的基础上改写出了SBT_Select_Delete，即选择指定秩的节点删除，并返回此节点。这个也不难，看看我的代码就知道了。只是注意，既然删除的节点要回收利用，那么从树中删除后就需要处理清楚size和ch[]域。

BTW，题目中给的count范围包括0，这是不负责任的。仔细想想就发现一旦出现这样的节点你就无法确定该如何处理了。当然了，评测时并没有给出这样的数据，否则鬼知道怎么处理呢。

时空开销：

代码：

#include "happybirthday_lib_c.cpp"
struct SBTNode{
	SBTNode *ch[2];
	long size, key, id;
	SBTNode(long _key, long _id, long _size);
}NIL=SBTNode(0,0,0);
SBTNode::SBTNode(long _key, long _id, long _size=1){
	key=_key,id=_id,size=_size;
	ch[0]=ch[1]=&NIL;
}
typedef SBTNode* SBTree;
void SBT_Rotate(SBTree &x, bool flag){
	SBTNode *y = x->ch[!flag];
	x->ch[!flag]=y->ch[flag],y->ch[flag]=x;
	y->size=x->size;
	x->size=x->ch[0]->size+x->ch[1]->size+1;
	x=y;
}
void SBT_Maintain(SBTree &T,bool flag){
	if(T->ch[flag]->ch[flag]->size>T->ch[!flag]->size)
		SBT_Rotate(T,!flag);
	else if(T->ch[flag]->ch[!flag]->size>T->ch[!flag]->size)
		SBT_Rotate(T->ch[flag],flag),SBT_Rotate(T,!flag);
	else return;
	SBT_Maintain(T->ch[0],0),SBT_Maintain(T->ch[1],1);
	SBT_Maintain(T,0),SBT_Maintain(T,1);
}
long SBT_Insert(SBTree &T, SBTNode *toAdd){
	if(T==&NIL){
		T=toAdd;
		return 1;
	}else{
		T->size++;
		bool flag=toAdd->key>T->key;
		long r=SBT_Insert(T->ch[flag],toAdd)+(flag?T->ch[0]->size+1:0);
		SBT_Maintain(T,flag);
		return r;
	}
}
SBTNode *SBT_Select_Delete(SBTree &T,long i){
	if(T==&NIL)	return &NIL;
	T->size--;
	unsigned long r = T->ch[0]->size + 1;
	if(i==r){
		SBTNode *toDel = NULL;
		if(T->ch[0]==&NIL||T->ch[1]==&NIL){
			toDel=T;
			T=T->ch[T->ch[1]!=&NIL];
		}else{
			toDel = SBT_Select_Delete(T->ch[1],1);
			swap(T->key,toDel->key),swap(T->id,toDel->id);
		}
		toDel->ch[0]=toDel->ch[1]=&NIL;
		toDel->size=1;
		return toDel;
	}
	else return SBT_Select_Delete(T->ch[i>r],i>r?i-r:i);
}
int main(){
	long c,l,r,id=1; bool isboy;
	SBTNode *toEat; SBTree T=&NIL;
	for(init();getpresent(c,l,isboy);id++){
		SBTNode *toAdd = new SBTNode(c,id);
		r = SBT_Insert(T,toAdd);
		if(isboy)	r+=l;
		else r-=l;
		if(r<=0||r>T->size) tell(-1);
		else{
			toEat = SBT_Select_Delete(T,r);
			tell(toEat->id);
			if(--toEat->key>0)	SBT_Insert(T,toEat);
			else delete toEat;
		}
	}
	return 0;
}

P.S.有一件事情很郁闷，那就是……这题用不着平衡树-_-|||

因为数据都是random的，普通BST表现反倒会更好。。。（但是比赛时谁知道呢）

Parity Game

Time Limit:1000MS

Memory Limit:65536K

Description

Now and then you play the following game with your friend. Your friend writes down a sequence consisting of zeroes and ones. You choose a continuous subsequence (for example the subsequence from the third to the fifth digit inclusively) and ask him, whether this subsequence contains even or odd number of ones. Your friend answers your question and you can ask him about another subsequence and so on. Your task is to guess the entire sequence of numbers.

You suspect some of your friend’s answers may not be correct and you want to convict him of falsehood. Thus you have decided to write a program to help you in this matter. The program will receive a series of your questions together with the answers you have received from your friend. The aim of this program is to find the first answer which is provably wrong, i.e. that there exists a sequence satisfying answers to all the previous questions, but no such sequence satisfies this answer.

Input

The first line of input contains one number, which is the length of the sequence of zeroes and ones. This length is less or equal to 1000000000. In the second line, there is one positive integer which is the number of questions asked and answers to them. The number of questions and answers is less or equal to 5000. The remaining lines specify questions and answers. Each line contains one question and the answer to this question: two integers (the position of the first and last digit in the chosen subsequence) and one word which is either ‘even’ or ‘odd’ (the answer, i.e. the parity of the number of ones in the chosen subsequence, where ‘even’ means an even number of ones and ‘odd’ means an odd number).

Output

There is only one line in output containing one integer X. Number X says that there exists a sequence of zeroes and ones satisfying first X parity conditions, but there exists none satisfying X+1 conditions. If there exists a sequence of zeroes and ones satisfying all the given conditions, then number X should be the number of all the questions asked.

Example

Example 1:

PARITY.IN

10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd

PARITY.OUT

3

Example 2:

PARITY.IN

10
5
1 2 even
1 4 even
2 4 odd
1 10 even
3 10 even

PARITY.OUT

5

Solution

挖个坑先……要是比赛中的话我怎么可能想到这题是并查集呢！

终于搞定。

首先有一步关键转化要做。我们同时处理一个范围内数字1的个数的奇偶比较麻烦。如果a到b之间有n个1，那么可以看成0到b之间1的个数减去0到a-1之间1的个数为n。我们假想知道了所有1的位置，那么0到任意i之间1的个数就是确定的。也就是说，通过这种转化，数据范围内每个数都对应了一个确定的数，它表示0到此数之间数字1的个数。

而我们事实上并不知道这些数确切是什么。我们知道的是一些数对之间奇偶性的关系。而这种关系是可以传递转移的。我们需要判断在给出关系的过程中是否出现矛盾。

于是就可以用并查集来解决这个问题了。它与我前面做过的食物链相比，本质上是一样的，但是处理起来还简单。你可以参照那个题的题解来理解这个题。

除了这步转化以外，对我而言处理起来比较麻烦的就是离散化了。这题串最大长度为10亿，而仅仅给出最多5千条询问，明显不离散化是不行了。我用的Hash。Hash和并查集的联合我从前是没搞过的。

P.S.这题其实是个骗分的好题（ACMer们别打我。。。）。不离散化最少70分。如果内存放宽一点就有80分。即使奇偶搞反了都有50分……总之怎么着都能得分的。CEOI的标程好像不是用并查集做的，但是要慢一些。就不管它了。

时空开销：

URAL的数据ms有问题，就再不管了。

源码：

#include <fstream>
#include <string>
using namespace std;
const long P=29989;
const string odd="odd";
long N,K;
struct elem{
	long key,rank;
	bool p_r;//false means same
	elem *next,*p;
	elem(long _key){key=_key,rank=0,p=this,p_r=false,next=NULL;}
}*set[P];
elem* Hash_Search(long key){
	elem* p=set[key%P];
	while(p&&p->key!=key)	p=p->next;
	return p;
}
void Hash_Insert(elem* toAdd){
	long h = toAdd->key%P;
	toAdd->next=set[h];
	set[h]=toAdd;
}
elem *Set_Find(elem* A, bool &ch_r){
	if(A->p!=A){
		A->p=Set_Find(A->p,A->p_r);
		ch_r=(ch_r!=A->p_r);
	}
	return A->p;
}
bool istrue(long a,long b, bool flag){
	bool tmp=0;
	elem *A=Hash_Search(a),*B=Hash_Search(b);
	if(!A)	A = new elem(a),Hash_Insert(A);
	if(!B)	B = new elem(b),Hash_Insert(B);
	if(Set_Find(A,tmp)!=Set_Find(B,tmp)) return true;
	if(!flag) return A->p_r==B->p_r;
	else return A->p_r!=B->p_r;
}
void Set_Union(long a,long b, bool flag){
	elem *A=Hash_Search(a),*B=Hash_Search(b);
	if(!A)	A = new elem(a),Hash_Insert(A);
	else A=Set_Find(A,flag);
	if(!B)	B = new elem(b),Hash_Insert(B);
	else B=Set_Find(B,flag);
	if(A==B)	return;
	if(A->rank<B->rank)	A->p=B,A->p_r=flag;
	else{
		B->p=A,B->p_r=flag;
		if(A->rank==B->rank)	A->rank++;
	}
}
int main(){
	ifstream fin("PARITY.IN");
	ofstream fout("PARITY.OUT");
	fin >> N >> K;
	unsigned long a,b,ans=0;
	string parity;
	for(ans=1;ans<=K;ans++){
		fin >> a >> b >> parity;
		bool flag = parity==odd;//false means same
		if(istrue(a-1,b,flag))	Set_Union(a-1,b,flag);
		else break;
	}
	fout << --ans << endl;
	fin.close(),fout.close();
	return 0;
}

银河英雄传说

时限：2s

【问题描述】

公元五八○一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。

宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。

杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成30000列，每列依次编号为1, 2, …, 30000。之后，他把自己的战舰也依次编号为1, 2, …, 30000，让第i号战舰处于第i列(i = 1, 2, …, 30000)，形成“一字长蛇阵”，诱敌深入。这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

然而，老谋深算的莱因哈特早已在战略上取得了主动。在交战中，他可以通过庞大的情报网络随时监听杨威利的舰队调动指令。

在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

作为一个资深的高级程序设计员，你被要求编写程序分析杨威利的指令，以及回答莱因哈特的询问。

最终的决战已经展开，银河的历史又翻过了一页……

【输入文件】

输入文件galaxy.in的第一行有一个整数T（1<=T<=500,000），表示总共有T条指令。

以下有T行，每行有一条指令。指令有两种格式：

1. M i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特窃听到的杨威利发布的舰队调动指令，并且保证第i号战舰与第j号战舰不在同一列。
2. C i j ：i和j是两个整数（1<=i , j<=30000），表示指令涉及的战舰编号。该指令是莱因哈特发布的询问指令。

【输出文件】

输出文件为galaxy.out。你的程序应当依次对输入的每一条指令进行分析和处理：

如果是杨威利发布的舰队调动指令，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；

如果是莱因哈特发布的询问指令，你的程序要输出一行，仅包含一个整数，表示在同一列上，第i号战舰与第j号战舰之间布置的战舰数目。如果第i号战舰与第j号战舰当前不在同一列上，则输出-1。

【题解】
并查集。把每个战舰队列作为一个集合。两个战舰队列的合并就可以看作两个集合的合并。
这里我们需要处理集合内元素间的关系：得到两个元素之间的元素个数。把所有元素按顺序储存需要的时候再数显然是不划算的。我们可以为每个节点维护一个dist域，记录此元素到到父节点的距离。显然如果要求两个元素i、j间的距离，我们需要先通过路径压缩使得他们的父节点统一为根，然后只要|dist[i]-dist[j]|-1就行了。
但是在合并两个集合时怎么维护dist呢？我们这里再引入一个size域，仅当i为战舰队列的头头时才有效。它表示集合中元素的个数。这样，在做合并时，就很容易维护dist了。问题解决。

代码：

#include <cstdio>
#include <cstdlib>
using namespace std;
struct Set_elem{ int p,size,dist; }set[30000+1];
int Root(int i){
	if(set[i].p!=i){
		int root=Root(set[i].p);
		set[i].dist+=set[set[i].p].dist;
		set[i].p=root;
	}
	return set[i].p;
}
int main(){
	for(int i=1;i<=30000;i++)	set[i].p=i,set[i].size=1;
	FILE *fin = fopen("galaxy.in","r"), *fout = fopen("galaxy.out","w");
	int T,i,j,ir,jr;	char oper;
	for(fscanf(fin,"%d\n",&T);T>0;T--){
		fscanf(fin,"%c %d %d\n",&oper,&i,&j);
		ir=Root(i), jr=Root(j);
		switch(oper){
			case 'M':
				set[ir].p=jr;
				set[ir].dist=set[jr].size;
				set[jr].size+=set[ir].size;
				break;
			case 'C':
				fprintf(fout,"%d\n",ir==jr?abs(set[i].dist-set[j].dist)-1:-1);
		}
	}
	fclose(fin),fclose(fout);
	return 0;
}

食物链

时限：3s

空间限制：64MB

eat.pas/c/cpp

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。

现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这N个动物所构成的食物链关系进行描述：

第一种说法是“1 X Y”，表示X和Y是同类。

第二种说法是“2 X Y”，表示X吃Y。

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1.当前的话与前面的某些真的话冲突，就是假话；

2.当前的话中X或Y比N大，就是假话；

3.当前的话表示X吃X，就是假话。

你的任务是根据给定的N（1<=N<=50,000）和K句话（0<=K<=100,000），输出假话的总数。

输入文件（eat.in）

第一行是两个整数N和K，以一个空格分隔。

以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。

若D=1，则表示X和Y是同类。

若D=2，则表示X吃Y。

输出文件（eat.out）

只有一个整数，表示假话的数目。

输入样例

输入文件  对7句话的分析
100 7
1 101 1  假话
2 1 2  真话
2 2 3  真话
2 3 3   假话
1 1 3  假话
2 3 1  真话
1 5 5  真话

输出样例

3

题解

郁闷死了……这本来是个弱题，我也想着两下搞定算了，结果从昨天下午搞到今晚才搞定。关系想不清楚就会越写越乱。

显然并查集。把已知的每一类动物看成一个集合。当我们得到（或推断出）两只动物是同类的信息时，我们需要合并它们所在的集合。

但是当我们处理捕食关系时怎么办呢？这就需要处理各个集合间的关系了。我这里使用了两个额外的域分别指向它的天敌和猎物集合中的一个元素（名字分别是killer和food……可见我英语很烂，给变量起名字也不在行）。每三个相关的集合构成一个关系组。我们就可以通过对这两个域的维护来处理一个集合与关系组内另外两个集合的关系了。

注意，我们不能一上来得到一组关系就说“好，那你就是A，你就是B吧”。因为我们在得到两个关系组中某两个集合的关系（包括同类和捕食）时需要合并两个关系组，而这时很明显会挂得很惨。我们只能维护各个关系组内的关系，在合并组时才不会出错。当关系组合并时，两个关系组将合二为一，我们就需要分别合并关系组内对应集合，并且维护它们的那两个额外的域。

在维护这两个域时需要想清楚，有没有漏掉的。不清楚就开写，只能像我一样越搞越乱。

我把文件IO改成stdio后交poj后得到的时空开销：

修改后还算清晰的代码：

#include <cstdio>
using namespace std;
struct Set{	long rank,p,food,killer; }set[50001];
long lie_sum,N,K;
long root(long x){
	if(set[x].p!=x)	set[x].p=root(set[x].p);
	return set[x].p;
}
long unite(long x, long y){
	x=root(x),y=root(y);
	if(x==y||x==0||y==0)	return x!=0?x:y;
	if(set[x].rank>set[y].rank)	set[y].p=x;
	else{
		set[x].p=y;
		if(set[x].rank==set[y].rank)	set[y].rank++;
	}
	set[x].food=set[y].food=unite(set[x].food,set[y].food);
	set[x].killer=set[y].killer=unite(set[x].killer,set[y].killer);
	return set[x].p;
}
void eat(long x, long y){
	x=root(x),y=root(y);
	if(root(set[x].food)==y)	return;
	set[y].killer=unite(x,set[y].killer);
	set[x].food=unite(y,root(set[x].food));
	set[x].killer=set[y].food=unite(set[x].killer,set[y].food);
	long z=set[x].killer;
	if(z!=0){
		set[z].killer=y;
		set[z].food=x;
	}
}
bool istrue(long oper, long x, long y){
	if(x>N||y>N)	return false;
	x=root(x),y=root(y);
	long xk=root(set[x].killer),xf=root(set[x].food);
	switch(oper){
		case 1:	return(x==0||y==0||x==y||xk!=y&&xf!=y);
		case 2:	return(x!=y&&(xk==0||xk!=y));
	}
}
int main(){
	FILE *fin=fopen("eat.in","r"),*fout=fopen("eat.out","w");
	fscanf(fin,"%ld%ld",&N,&K);
	for(long i=1;i<=N;i++)	set[i].p=i;
	for(long i=1,oper,x,y;i<=K;i++){
		fscanf(fin,"%ld%ld%ld",&oper,&x,&y);
		if(istrue(oper,x,y))
			switch(oper){
				case 1:	unite(x,y);	break;
				case 2:	eat(x,y);
			}
		else lie_sum++;
	}
	fprintf(fout,"%ld\n",lie_sum);
	fclose(fin),fclose(fout);
	return 0;
}

下面是另外一种解法，同样使用了并查集。这是我在思考Parity Game时得到启发想出来的。我们上面处理三种动物关系时是通过处理各类动物组成的集合之间的关系来进行的。这种方法的实质其实是并查集“套”并查集。这种方法在关系较为简单时还有效，但如果关系较复杂呢？显然会因过于复杂而力不从心。

这就需要我下面要说的这种方法了。

其实很简单。只要稍稍变换一下思路就行了。我们避免处理集合间的关系，而是把它处理成集合内部的问题。我们把所有发生关系的动物看成一个集合，它们不需要是同类的。因为我们知道，这样形成的整个集合中各个动物间的关系都是密切相关的，任何一个动物身份的确定都会使得整个集合确定下来。我们为了维持这种关系，只需维护每个动物与其父节点之间的捕食关系就行了(通过简单维护一个p_r域实现)。而任意两个在同一集合中的动物都可以通过根节点联系起来。路径压缩也很好实现。当两个动物发生关系时，我们只需要合并两个集合就可以处理所有的关系了。就这么简单。

时空开销（都比第一种方法小）：

代码：

//#define NDEBUG
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
using namespace std;
const long max_n = 50000;
long N,K,lie_sum;
struct set_elem{
	long p,rank;
	long p_r;//the relationship between the node and its father
	//1 means equal, 2 mean it eat it's father,
	//3 means its father eats it
}set[max_n];
long Find(long x,long &ch_r){
	if(set[x].p!=x){
		set[x].p=Find(set[x].p,set[x].p_r);
		if(ch_r==1)	ch_r=set[x].p_r;
		else if(ch_r!=set[x].p_r) ch_r=1;
		else ch_r=(ch_r==2?3:2);
	}
	return set[x].p;
}
void Union(long oper,long x,long y){
	//we should be sure that x and y are not in one same set
	assert(oper==1||oper==2||oper==3);
	y=Find(y,oper);
	if(oper!=1) oper=(oper==2?3:2);
	x=Find(x,oper);
	assert(x!=y);
	if(set[x].rank>set[y].rank){
		set[y].p=x;
		set[y].p_r=oper;
	}else{
		set[x].p=y;
		if(oper!=1) oper=(oper==2?3:2);
		set[x].p_r=oper;
		if(set[x].rank==set[y].rank) set[y].rank++;
	}

}
int main(){
	FILE *fin = fopen("eat.in","r"),*fout = fopen("eat.out","w");
	fscanf(fin,"%ld%ld",&N,&K);
	for(int i=1;i<=N;i++)	set[i].p=i; //initialize the set
	for(long i=1,oper,x,y,tmp;i<=K;i++){
		fscanf(fin,"%ld%ld%ld",&oper,&x,&y);
		if(x>N||y>N){
			//cout << i << endl;
			lie_sum++;
			continue;
		}
		tmp=1;Find(y,tmp);
		tmp=1;Find(x,tmp);
		if(set[x].p!=set[y].p) Union(oper,x,y);
		else if(oper==1&&set[x].p_r==set[y].p_r) continue;
		else if(oper==2&&
              (set[x].p_r==2&&set[y].p_r==1||
               set[x].p_r==1&&set[y].p_r==3||
               set[x].p_r==3&&set[y].p_r==2)
             ) continue;
		else {
			//cout << i << endl;
			lie_sum++;
		}
		/*
		if(istrue(oper,x,y))	Union(short(oper),x,y);
		else lie_sum++;
		*/
	}
	fprintf(fout,"%ld\n",lie_sum);
	fclose(fin),fclose(fout);
	system("pause");
	return 0;
}

Great Bytelandish net of supermarkets asked you for writing a program simulating costs of the promotion being prepared.

The promotion has to obey the following rules:

• A customer, who wants to participate in the promotion, writes on the bill, paid by himself, his personal details and throws it to a special ballot box.
• At the end of every day of the promotion, two bills are taken out from the ballot box:
  • the first bill amounting to the greatest sum is chosen,
  • then the bill amounting to the least sum is chosen;

  The customer, who has paid the greatest bill, gets a money prize equal to the difference between the sum on his bill and the sum on the bill amounting to the least sum.

• To avoid multiple prizes for one purchase, both bills selected accordingly to the above rules, do not return to the ballot box, but all remaining bills still participate in promotion.

Turnovers of the supermarket are very big, thus an assumption can be made, that at the end of every day, before taking out bills amounting to the greatest and the least sum, there are at least 2 bills in the ballot box.

Your task is to compute on the basis of information about prices on bills thrown to the ballot box on each day of promotion, what will be the total cost of prizes during the whole promotion.

Task

Write a program, which:

• reads from the text file PRO.IN a list of prices on bills thrown to the ballot box on each day of the promotion,
• computes the total cost of prizes paid in consecutive days of promotion,
• writes the result to the text file PRO.OUT.

Input

The first line of the text file PRO.IN contains one positive integer n, where 1 <= n <= 5000, which is the duration of promotion in days.

Each of the next n lines consists of a sequence of non-negative integers separated by single spaces. Numbers in the (i+1)-th line of the file represent prices on bills thrown to the ballot box on the i-th day of promotion. The first integer in the line is k, 0 <= k <= 10^5, the number of bills from the day, and the next k numbers are positive integers standing for the prices on bills; none of these numbers is greater than 10^6.

The total number of bills thrown to the ballot box during the whole promotion does not exceed 10^6.

Output

The text file PRO.OUT should contain exactly one integer, which is equal to the total cost of prizes paid during the whole promotion.

Example

 5 3 1 2 3 2 1 1 4 10 5 5 1 0 1 2

 the correct answer is the output file PRO.OUT 

 19

Solution

这是一个坑，为了催促我快点搞定这题……这破题已经搞了好几天了，已经写了5个版本，用了sbt、静态bst、堆，现在正在调试的是第6个版本，应该也是最后一个版本了……我的效率太低，太低……

没心再写了，反正最后已经不TLE了……

写了7遍还是没写过Ghost……但是还是学到了不少东西的。这题本来是出现在一个线段树论文中作为例题的，我就想，用bst不是更方便么。然后就写了个SBT，稍微改进了下Delete过程，然后就出现了1号夸张的结果。Ghost写了个treap比我快n多，发现原来是因为他合并了相同的节点。改进后效果非常明显，得到了2号代码。但是仍然不够快，就写了3号的静态BST，应该和线段树的速度差不多的，但仍然不够快。说明那个论文里说用线段树解是扯的……

CQF大牛说要用堆解这题。Ghost牛解释说要同时维护一个大根堆和一个小根堆，并通过维护指针来实现在从一个堆中取出最值后能在另一个堆中同时移除这个值。这样就可以同时支持取最大和最小了。据此我写出了4号代码。下面我解释下维护过程：

首先对指针的维护要确保对于一个堆中的节点能直接找到另一个堆中具有相同关键字的节点，它的实现其实很方便，这里就不说了。每次插入一个节点时，只要在每个堆中都像普通堆一样进行维护就行了，只是同时要维护指针而已。而取最值也不麻烦。比如要取最大值，对于大根堆的维护只是和平常一样就行了。至于小根堆，由于我们取走的是最大值，那它一定小于等于小根堆的最后一个节点，这样我们只要用减小小根堆中某节点值的方法来维护它就行了。取最小值则与此对称。这样我就写出了5号代码。

但还是不够快。Ghost的一个优化又是合并相同节点。由于数据范围不大，又都是整数而无需离散化，那直接就可以通过稍微修改一下指针域并加上计数域count来支持O(1)查找和计数修改。这样就得到了6号代码。可见合并相同节点是BST、Heap等ds中一种很有效的优化手段。它可以降低树的高度，减少节点数目，从而减少旋转次数、heapify次数等等。

剩下的就是纯粹的代码优化了。始终搞不过Ghost，郁闷……

代码不帖了。