BZOJ 2947 [Poi2000]促销

题目大意

维护一个序列，支持：删除最大和最小值并做差求和；插入一些数。

这题一看就知道可以用权值线段树维护。连动态开点都不用美滋滋qwq

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxN 1000000
#define lson pos<<1
#define rson pos<<1|1
int n,k,inx,siz[maxN*20+10],tx,ty;
long long ans;
void add(int pos,int l,int r,int tx)
{
    siz[pos]++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(tx<=mid) add(lson,l,mid,tx);
    else add(rson,mid+1,r,tx);
}
int del(int pos,int l,int r,int tx)
{
    siz[pos]--;
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(tx<=siz[lson]) return del(lson,l,mid,tx);
    else return del(rson,mid+1,r,tx-siz[lson]);
}
int readin()
{
    int ret=0;
    char tmp=getchar();
    while(tmp<'0'||tmp>'9') tmp=getchar();
    while(tmp>='0'&&tmp<='9') {ret=(ret*10)+(tmp-'0');tmp=getchar();}
    return ret;
}
int main()
{
    n=readin();
    while(n--)
    {
        k=readin();
        while(k--) {inx=readin();add(1,1,maxN,inx);}
        tx=del(1,1,maxN,1);ty=del(1,1,maxN,siz[1]);
        if(tx<ty) swap(tx,ty);
        ans+=tx-ty;
    }
    printf("%lld\n",ans);
    return 0;
}