BZOJ 1588 [HNOI2002]营业额统计

treap的入门题，虽然在splay的论文里看到过这题。。。

遇到2个奇葩问题：1：BZOJ 上用srand(time(NULL))会RE 2：这题的数据不完整

Description

Input

Output

Sample Input

Sample Output

HINT

Source

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <ctime>

using namespace std;

const int INF=0x3f3f3f3f;

struct Node
{
    int r,v,s;
    Node* ch[2];

    int cmp(int x)
    {
        if(v==x) return -1;
        return (x<v)?0:1;
    }

    void maintain()
    {
        s=ch[0]->s+1+ch[1]->s;
    }
};

Node* nill;

void init()
{
    nill=new Node();
    nill->s=0;
    nill->ch[0]=nill->ch[1]=nill;
    //srand(time(NULL));
}

void rotate(Node* &o,int d)
{
    Node* k=o->ch[1^d];
    o->ch[1^d]=k->ch[d];
    k->ch[d]=o;

    o->maintain();
    k->maintain();

    o=k;
}

void insert(Node* &o,int x)
{
    if(o==nill)
    {
        o=new Node();
        o->v=x;o->r=rand();o->s=1;
        o->ch[0]=o->ch[1]=nill;
    }
    else
    {
        int d=o->cmp(x);
        if(d==-1) d=0;
        insert(o->ch[d],x);
        if(o->ch[d]->r>o->r) rotate(o,1^d);
    }
    o->maintain();
}

void remove(Node* &o,int x)
{
    int d=o->cmp(x);
    if(d==-1)
    {
        Node* u=o;
        if(o->ch[0]!=nill&&o->ch[1]!=nill)
        {
            int d2=(o->ch[0]->r>o->ch[1]->r)?1:0;
            rotate(o,d2);
            remove(o->ch[d2],x);
        }
        else
        {
            if(o->ch[1]==nill) o=o->ch[0]; else o=o->ch[1];
            delete u;
        }
    }
    else
    {
        remove(o->ch[d],x);
    }
    if(o!=nill) o->maintain();
}

int find(Node* o,int x)
{
    while(o!=nill)
    {
        int d=o->cmp(x);
        if(d==-1) return 1;
        o=o->ch[d];
    }
    return 0;
}

int Kth(Node* o,int x)///kth small
{
    while(o!=nill)
    {
        int s=o->ch[0]->s;
        if(x==s+1) return o->v;
        else if(x<=s) o=o->ch[0];
        else
        {
            o=o->ch[1];x=x-s-1;
        }
    }
    return -INF;
}

int Rank(Node* o,int x)
{
    int ret=0;
    while(o!=nill)
    {
        int s=o->ch[0]->s;
        if(o->v<=x)
        {
            ret+=s+1;
            o=o->ch[1];
        }
        else
        {
            o=o->ch[0];
        }
    }
    return ret;
}

int main()
{
    int n;
while(scanf("%d",&n)!=EOF)
{
    int ret;
    scanf("%d",&ret);
    init();
    Node* root=nill;
    insert(root,ret);
    for(int i=2;i<=n;i++)
    {
        int a,temp1=-INF,temp2=INF;
        if(scanf("%d",&a)==EOF) a=0;

        int rk=Rank(root,a);

        if(rk) temp1=Kth(root,rk);

        if(rk+1<=i-1) temp2=Kth(root,rk+1);

        ret+=min(a-temp1,temp2-a);

        insert(root,a);
    }

    printf("%d\n",ret);
}
    return 0;
}

BZOJ 1588 [HNOI2002]营业额统计

原文：http://blog.csdn.net/u012797220/article/details/19302665