代码
#include<iostream>
#include<vector>
using namespace std;
const __int64 MAXN = 10000;
struct NODE
{
__int64 l,r,cnt;
NODE *left_child,*right_child;
};
vector<__int64> hash[10001];
void build ( NODE *v , __int64 l , __int64 r )
{
NODE *p;
__int64 m;
if ( l>=r )
return ;
m=(l+r)>>1;
p=new NODE;
p>l=l,p>r=m,p>cnt=0,p>left_child=p>right_child=NULL;
v>left_child=p;
build(p,l,m);
p=new NODE;
p>l=m+1,p>r=r,p>cnt=0,p>left_child=p>right_child=NULL;
v>right_child=p;
build(p,m+1,r);
}
void ins ( __int64 d , NODE *v )
{
__int64 m;
if ( v==NULL )
return;
if ( v>l<=d && d<=v>r )
{
v>cnt++;
m=(v>l+v>r)/2;
if ( d<=m )
ins(d,v>left_child);
else
ins(d,v>right_child);
}
}
void del ( __int64 d , NODE *v )
{
__int64 m;
if ( v==NULL )
return;
if ( v>l<=d && d<=v>r )
{
if ( v>cnt>0 )
v>cnt;
m=(v>l+v>r)/2;
if ( d<=m )
del(d,v>left_child);
else
del(d,v>right_child);
}
}
__int64 max ( NODE *v )
{
if ( v>left_child==NULL ||v>right_child==NULL )
return v>r;
if ( v>right_child>cnt )
return max(v>right_child);
else
return max(v>left_child);
}
__int64 min ( NODE *v )
{
if ( v>left_child==NULL ||v>right_child==NULL )
return v>l;
if ( v>left_child>cnt )
return min(v>left_child);
else
return min(v>right_child);
}
__int64 hash_max ( __int64 f )
{
vector<__int64>::iterator p,q;
__int64 res;
for ( p=q=hash[f].begin() ; p!=hash[f].end() ; p++ )
if( *q<*p )
q=p;
res=*q;
hash[f].erase(q);
return res;
}
__int64 hash_min ( __int64 f )
{
vector<__int64>::iterator p,q;
__int64 res;
for ( p=q=hash[f].begin() ; p!=hash[f].end() ; p++ )
if( *q>*p )
q=p;
res=*q;
hash[f].erase(q);
return res;
}
int main ( )
{
NODE *head;
__int64 c,k,i,j,d,maxnum,minnum,res=0;
head=new NODE;
head>cnt=0,head>l=0,head>r=MAXN,head>left_child = head>right_child = NULL;
build(head,0,MAXN);
scanf("%I64d",&c);
for ( i=0 ; i<c ; i++ )
{
scanf("%I64d",&k);
for ( j=0 ; j<k ; j++ )
{
scanf("%I64d",&d );
hash[d/100].push_back(d);
ins(d/100,head);
}
maxnum=max(head);
minnum=min(head);
res+=hash_max(maxnum)hash_min(minnum);
del(maxnum,head);
del(minnum,head);
}
printf("%I64d\n",res);
}
刚开始接触线段树，还不会离散化~继续学习。
责任编辑：小草
