POJ2761---Feed the dogs (Treap求区间第k大)

题意 就是求区间第k大，区间 不互相包含。

尝试用treap解决一下 第k大的问题。

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef unsigned long long ull;

 typedef long long ll;

 const int inf = 0x3f3f3f3f;

 const double eps = 1e-;

 const int maxn = 1e5+;

 struct Node

 {

     Node *ch[];

     int key, siz, r;

     Node (int val)

     {

         ch[] = ch[] = NULL;

         siz = ;

         key = val;

         r = rand();

     }

     bool operator < (const Node &rhs)const

     {

         return r < rhs.r;

     }

     int cmp(int x)const

     {

         if (key == x)

             return -;

         return key > x ?  : ;

     }

     void maintain()

     {

         siz = ;

         if (ch[] != NULL)

             siz += ch[] -> siz;

         if (ch[] != NULL)

             siz += ch[] -> siz;

     }

 };

 void rotate(Node* &root, int d)

 {

     Node *tmp = root -> ch[d^];

     root -> ch[d^] = tmp -> ch[d];

     tmp -> ch[d] = root;

     root -> maintain();

     tmp -> maintain();

     root = tmp;

 }

 void insert (Node* &root, int x)

 {

     if (root == NULL)

         root = new Node (x);

     else

     {

         int d = x < root -> key ?  : ;

         insert(root -> ch[d], x);

         if (root -> ch[d] -> r > root -> r)

             rotate(root, d^);

     }

     root -> maintain();

 }

 void dele(Node* &root, int x)

 {

     int d = root -> cmp(x);

     if (d == -)

     {

         Node* tmp = root;

         if (root -> ch[] != NULL && root -> ch[] != NULL)

         {

             int d1 = (root -> ch[] -> r > root -> ch[] -> r  ?  : );

             rotate(root, d1);

             dele(root -> ch[d1], x);

         }

         else

         {

             if (root -> ch[] == NULL)

                 root = root -> ch[];

             else

                 root = root -> ch[];

             delete tmp;

         }

     }

     else

         dele(root -> ch[d], x);

     if (root != NULL)

         root -> maintain();

 }

 int Get_kth(Node* root,int k)

 {

     if (root == NULL || k <=  || k > root -> siz)

         return ;

     int s = (root -> ch[] == NULL ?  : root -> ch[] ->siz);

     if (s +  == k)

         return root -> key;

     else if (s >= k)

         return Get_kth(root -> ch[], k);

     else

         return Get_kth(root -> ch[], k - s -);

 }

 struct Query

 {

     int l, r, k,idx;

     bool operator < (const Query &rhs)const

     {

         return r < rhs.r;

         //return l < rhs.l || (l == rhs.l&&r < rhs.r);

     }

 }Q[];

 int a[], ans[];

 Node* treap;

 int main()

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt","r",stdin);

     #endif

     int n, m;

     while  (~scanf ("%d%d",&n, &m))

     {

         for (int i = ; i < n; i++)

             scanf ("%d", a+i+);

         for (int i = ; i < m; i++)

         {

             scanf ("%d%d%d",&Q[i].l, &Q[i].r, &Q[i].k);

             Q[i].idx = i;

             if (Q[i].l > Q[i].r)

                 swap(Q[i].l,Q[i].r);

         }

         sort (Q, Q+m);

         int index = Q[].l, lidx = ;

         for (int i = ; i < m; i++)

         {

             for (int j = lidx; j && j < min(Q[i].l, Q[i-].r+); j++)

                 dele(treap, a[j]);

             lidx = Q[i].l;

             for (int j = max(Q[i].l,index); j <= Q[i].r; j++)

             {

                 insert(treap, a[j]);

             }

             index = Q[i].r+;

             ans[Q[i].idx] = Get_kth(treap, Q[i].k);

         }

         for (int i = ; i < m; i++)

         {

             printf("%d\n",ans[i]);

         }

     }

     return ;

 }