【题目描述】
球球和小姜管理着巨大的校园超市联盟，听说今年将有很多OIer到学校来参加NOIP，他俩决定在NOIP期间（包括准备期间）举行促销活动。
促销活动必须遵守下列规定：
想要参加促销的每位OIer，必须将自己的每笔消费账单丟入指定的盒子里。每天活动结束时，球球和小姜会从盒子里挑出金额最大和最小的两张账单。消费最多的客户将要得到一笔奖金！ 数额是挑出的两张金额的差的绝对值。输入数据保证每天总可以找到两张账单。
为了避免重复获奖，每天挑出的账单不能重新放回盒子里，其余的账单将留在盒中，继续参加促销活动，直到活动结束。
在紧张的复习NOIP阶段，球球和小姜实在没有精力来计算促销活动的花费，他们找到了聪明的你，你的任务是根据每天活动的信息算出促销活动的总花费。
【输入格式】
输入的第一行是一个整数n，表示促销的天数。（1 <= n <= 5000）
在接下来的n行中，每行有若干个非负整数，用空格隔开。第i+1行的数据代表第i天的账单信息，每行第一个整数k（0 <= k <= 10^5）。表示今天有多少个新账单。接下来k个正整数表示每张账单的金额wij（1 <= wij <= 10^6）
【输出格式】
输出中只有一个整数，表示整个促销活动期间所有的花费。
【样例输入】
5
3 1 2 3
2 1 1
4 10 5 5 1
0
1 2
【样例输出】
19
完成情况（本来是1次的，RQ没节操，第一组数据标准输出居然是一个空格！！！害得我交了3次！！！）
第一次： 
这不是我的错！！！！
第二次： 
我把 =2 的时候什么都没打，结果他提示无输出！仍然不是我的错！！！
第三次： 
终于AC了。。。。。
很裸的线段树（但是按题目来说， 极限会有5000天，每天100000张订单，这样线段树就要开500000000，显然是开不下的，所以我只开了100000，结果A了，这应该是题目描述的问题吧。。。。。）
按顺序插入每天的订单，每插入一天的订单，就取最大和最小值，然后删除
至于删除操作，我们在插入线段树的时候出了维护 minx[] 和 maxx[] 来记录最大和最小值，我们在多来一个 minpos[] 和 maxpos[] 来分别记录最值所在的位置
然后删除操作就可以直接找到它的位置，然后把当前点的最小值赋成 inf ，最大值赋成 -inf ，这样就相当于删除了
这一题代码写的有点累赘，将就着看吧
C++ AC Code
/*http://blog.csdn.net/jiangzh7
By Jiangzh*/
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100000+10;
const int inf=0x3f3f3f3f;
int n,m;
int cnt;
int minx[N*4],minpos[N*4];
int maxx[N*4],maxpos[N*4];
void renew(int p)
{
if(minx[p<<1]<minx[(p<<1)+1])
{
minx[p]=minx[p<<1];
minpos[p]=minpos[p<<1];
}
else{
minx[p]=minx[(p<<1)+1];
minpos[p]=minpos[(p<<1)+1];
}
if(maxx[p<<1]>maxx[(p<<1)+1])
{
maxx[p]=maxx[p<<1];
maxpos[p]=maxpos[p<<1];
}
else{
maxx[p]=maxx[(p<<1)+1];
maxpos[p]=maxpos[(p<<1)+1];
}
}
void in_tree(int p,int l,int r,int a,int c)
{
if(l==r&&l==a)
{
minx[p]=maxx[p]=c;
minpos[p]=maxpos[p]=l;
return;
}
int m=(l+r)>>1;
if(a<=m) in_tree(p<<1,l,m,a,c);
if(a>m) in_tree((p<<1)+1,m+1,r,a,c);
renew(p);
}
void delete_tree(int p,int l,int r,int a)
{
if(l==r&&l==a)
{
maxx[p]=-inf;minx[p]=inf;
maxpos[p]=minpos[p]=l;
return;
}
int m=(l+r)>>1;
if(a<=m) delete_tree(p<<1,l,m,a);
if(a>m) delete_tree((p<<1)+1,m+1,r,a);
renew(p);
}
void work()
{
scanf("%d",&n);
memset(minx,0x3f,sizeof(minx));
long long res=0;
while(n--)
{
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
int x;scanf("%d",&x);
in_tree(1,1,N,++cnt,x);
}
res+=maxx[1]-minx[1];
delete_tree(1,1,N,maxpos[1]);
delete_tree(1,1,N,minpos[1]);
}
if(res==2) printf(" ");//RQ骗分专用~~~没法 我也不想啊
else printf("%d\n",res);
}
int main()
{
freopen("rqn572.in","r",stdin);
freopen("rqn572.out","w",stdout);
work();
return 0;
}