(TOJ) 80 / RMQ 練習(1) [treap 區間max,min]

http://sprout.tw/oj/pro/80/

Treap 解

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

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

const int INF= 1e9+7;

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

void pull(Treap* t) {
 t->mx = min(Mx(t->lc),Mx(t->rc));
 t->mx = min(t->mx,t->val);
}

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);
 }
}

void insert(Treap* root,int k,int val) {
 Treap* tl;
 Treap* tr;
 split(root,k-1,tl,root);
 split(root,k,root,tr);
 root->val = root->mx = val;
 merge(merge(tl,root),tr);
}

int query(Treap* root,int l,int r) {
 Treap* tl;
 Treap* tr;
 split(root,l-1,tl,root);
 split(root,r,root,tr);
 int ret=root->mx;
 merge(merge(tl,root),tr);
 return ret;
}

int main () {
 srand(time(NULL));
 int T,n;
 while (scanf("%d %d",&T,&n) != EOF) {
  Treap* root=NULL;
  for (int x=0;n>x;x++) {
//   cout<<"x="<<x<<endl;
   int i;
   scanf("%d",&i);
   root = merge(root,new Treap(i,x));
   
  }
  while (T--) {
   int i,j,k;
   scanf("%d %d %d",&i,&j,&k);
   if (i==1) {
    printf("%d\n",query(root,j,k));
   }
   else {
    insert(root,j,k);
   }
  }
 }
}