都说叫分段HASH。。
我觉得还是有点块状数组的感觉。。
用stl写平衡数很方便不过还是块状数组爽。。
可以是负数的阿。。好贱。。。
Code。。
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=1000001,maxv=maxn*2,maxsize=1000,maxL=maxv/maxsize+10;
int C[maxv]={0};
int D[maxL]={0};
int n,Blocks;
void insert(int n)
{
C[n]++;
D[n/maxsize]++;
}
void del(int n)
{
C[n]–;
D[n/maxsize]–;
}
int getMin()
{
int i,j;
for(i=0;i<maxL;i++)
if(D[i]) break;
for(j=i*maxsize;;j++)
if(C[j]) break;
return j;
}
int getMax()
{
int i,j;
for(i=maxL-1;i>=0;i–)
if(D[i]) break;
for(j=(i+1)*maxsize-1;;j–)
if(C[j]) break;
return j;
}
int main()
{
cin>>n;int k,t;
long long ans=0;
while(n–)
{
scanf("%d",&k);
while(k–)
scanf("%d",&t),insert(t+maxn);
int Max=getMax(),Min=getMin();
ans+=Max-Min;
del(Max);del(Min);
}
cout<<ans<<endl;
}