题解：UVA11136 Hoax or what

#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n,k,x;
ll ans;
namespace SegmentTree{
	struct node{
		int l,r,sum;
	} tri[N << 2];
	void build(int p,int l,int r){
		tri[p].l = l;
		tri[p].r = r;
		tri[p].sum = 0;
		if(l == r){
			return;
		}
		int mid = (l + r) >> 1;
		build(p << 1,l,mid);
		build(p << 1 | 1,mid + 1,r);
	}
	void update(int p,int pos,int val){
		tri[p].sum += val;
		if(tri[p].l == tri[p].r){
			return;
		}
		int mid = (tri[p].l + tri[p].r) >> 1;
		if(pos <= mid){
			update(p << 1,pos,val);
		}else{
			update(p << 1 | 1,pos,val);
		}
	}
	int query_min(int p){
		if(tri[p].l == tri[p].r){
			return tri[p].l;
		}
		if(tri[p << 1].sum > 0){
			return query_min(p << 1);
		}else{
			return query_min(p << 1 | 1);
		}
	}
	int query_max(int p){
		if(tri[p].l == tri[p].r){
			return tri[p].l;
		}
		if(tri[p << 1 | 1].sum > 0){
			return query_max(p << 1 | 1);
		}else{
			return query_max(p << 1);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	while(true){
		cin >> n;
		if(n == 0){
			break;
		}
		SegmentTree::build(1,0,N - 10);
		ans = 0;
		while(n --){
			cin >> k;
			while(k --){
				cin >> x;
				SegmentTree::update(1,x,1);
			}
			int minn = SegmentTree::query_min(1),maxx = SegmentTree::query_max(1);
			ans += (ll)(maxx - minn);
			SegmentTree::update(1,minn,-1);
			SegmentTree::update(1,maxx,-1);
		}
		cout << ans << '\n';
	}
	return 0;
}