a066: HNOI2002 营业额统计

http://cat.nknush.kh.edu.tw/ShowProblem?problemid=a066

如果題目少輸入的話，用0去算！！！(害我debug了大約20min！！！)

很重要！！！

我放的code是如果測資是okay的code，直接貼上去是會吃NA(score : 80)的喔！

想法：開一個treap維護數字XDDD，數值線段樹也應該可以，不過最近發現treap比較好co ^_^

#include <iostream>
#include <stdio.h>
#include <ctime>
#include <cstdlib>
#include <cmath>
using namespace std;

struct Treap {
 Treap* lc;
 Treap* rc;
 int pri;
 int key;
 int mn,mx;
 Treap(int _key) {
  lc=rc=NULL;
  mn=mx=key=_key;
  pri=rand();
 }
};

const int INF = 1e9+7;

int Mx(Treap* t) {
 return t?t->mx:-INF;
}

int Mn(Treap* t) {
 return t?t->mn:INF;
}

void pull(Treap* t) {
 t->mx = max(Mx(t->lc),Mx(t->rc));
 t->mx = max(t->mx,t->key);
 t->mn = min(Mn(t->lc),Mn(t->rc));
 t->mn = min(t->mn,t->key);
}

Treap* merge(Treap* a,Treap* b) {
 if (!a || !b) return a?a:b;
 else if (a->pri > b->pri) {
  a->rc = merge(a->rc,b);
  pull(a);
  return a;
 }
 else {
  b->lc = merge(a,b->lc);
  pull(b);
  return b;
 }
}

void split(Treap* t,int k,Treap* &a,Treap* &b) {
 if (!t) a=b=NULL;
 else if (t->key <= k) {
  a=t;
  split(t->rc,k,a->rc,b);
  pull(a);
 }
 else {
  b=t;
  split(t->lc,k,a,b->lc);
  pull(b);
 }
}

int main () {
 srand(time(NULL));
 int n;
 while (scanf("%d",&n) != EOF) {
  Treap* root=NULL;
  long long int sum=0;
  for (int x=0;n>x;x++) {
   int i;
   scanf("%d",&i);
   if (x==0) {
    sum+=i;
    root = merge(root,new Treap(i));
   }
   else {
    Treap* tl;
    Treap* tr;
    split(root,i-1,tl,root);
    split(root,i,root,tr);
    if (tl) pull(tl);
    if (tr) pull(tr);
    int MX=Mx(tl);
    int MN=Mn(tr);
//    cout<<"mx = "<<MX<<" , mn = "<<MN<<endl;
    if (!root) sum+=min(abs(i-MX),abs(i-MN));
    root = merge(root,new Treap(i));
    root = merge(merge(tl,root),tr);
   }
  }
  printf("%lld\n",sum);
 }
}