poj2761（treap入门）

给n个数，然后m个询问，询问任意区间的第k小的数，特别的，任意两个区间不存在包含关系，
也就是说，将所有的询问按L排序之后，对于i<j , Li < Lj 且 Ri < Rj
所以只要每次查询的时候，treap都是对应区间[Li,Ri] ，那么查找第k小就很简单了
  1 #include <iostream>
  2 #include <string.h>
  3 #include <stdio.h>
  4 #include <time.h>
  5 #include <algorithm>
  6 using namespace std;
  7 const int INF = 1<<30;
  8 const int N = 100001 + 10;
  9 struct Treap
 10 {
 11     int ch[2];
 12     int fix,key;
 13     int same,cnt;
 14 }treap[N*40];
 15 struct Node
 16 {
 17     int l, r,k,id;
 18     bool operator<(const Node&rhs)const
 19     {
 20         return l < rhs.l;
 21     }
 22 }q[N*5];
 23 int tot;
 24 int val[N];
 25 int ans[N*5];
 26 void maintain(int o)
 27 {
 28     int lCnt = treap[o].ch[0] == 0 ? 0 : treap[treap[o].ch[0]].cnt;
 29     int rCnt = treap[o].ch[1] == 0 ? 0 : treap[treap[o].ch[1]].cnt;
 30     treap[o].cnt = treap[o].same + lCnt + rCnt;
 31 }
 32 void rotate(int &o, int d)
 33 {
 34     int t = treap[o].ch[d^1];
 35     treap[o].ch[d^1] = treap[t].ch[d];
 36     treap[t].ch[d] = o;
 37     maintain(o);
 38     maintain(t);
 39     o = t;
 40 }
 41 void insert(int &o, int tkey)
 42 {
 43     if(o==0)
 44     {
 45         o = ++tot;
 46         if(tot>=N*60) while(true);;
 47         treap[o].ch[0] = treap[o].ch[1] = 0;
 48         treap[o].cnt = treap[o].same = 1;
 49         treap[o].key = tkey;
 50         treap[o].fix = rand();
 51         maintain(o);
 52     }
 53     else if(tkey < treap[o].key)
 54     {
 55         insert(treap[o].ch[0],tkey);
 56         maintain(o);
 57         if(treap[treap[o].ch[0]].fix > treap[o].fix)
 58             rotate(o,1);
 59     }
 60     else if(tkey > treap[o].key)
 61     {
 62         insert(treap[o].ch[1],tkey);
 63         maintain(o);
 64         if(treap[treap[o].ch[1]].fix > treap[o].fix)
 65             rotate(o,0);
 66     }
 67     else
 68     {
 69         treap[o].same++;
 70         maintain(o);
 71     }
 72 
 73 }
 74 void remove(int &o, int tkey)
 75 {
 76     if(tkey < treap[o].key)
 77     {
 78         remove(treap[o].ch[0],tkey);
 79     }
 80     else if(tkey > treap[o].key)
 81     {
 82         remove(treap[o].ch[1],tkey);
 83     }
 84     else
 85     {
 86         if(treap[o].same!=1)
 87             treap[o].same--;
 88         else if(treap[o].ch[0]==0 && treap[o].ch[1]==0)
 89             o = 0;
 90         else if(treap[o].ch[0]==0)
 91         {
 92             rotate(o,0);
 93             remove(treap[o].ch[0],tkey);
 94         }
 95         else if(treap[o].ch[1]==0)
 96         {
 97             rotate(o,1);
 98             remove(treap[o].ch[1],tkey);
 99         }
100         else if(treap[treap[o].ch[0]].fix <= treap[treap[o].ch[1]].fix)
101         {
102             rotate(o,0);
103             remove(treap[o].ch[0],tkey);
104         }
105         else
106         {
107             rotate(o,1);
108             remove(treap[o].ch[1],tkey);
109         }
110     }
111     maintain(o);
112 }
113 
114 int query(int o, int k)
115 {
116     while(o)
117     {
118         int cnt = treap[o].ch[0]==0 ? 0 : treap[treap[o].ch[0]].cnt;
119         if(cnt>=k)
120             o = treap[o].ch[0];
121         else if(cnt<k && k<=cnt+treap[o].same)
122             return treap[o].key;
123         else
124         {
125 
126             k -= cnt + treap[o].same;
127             o = treap[o].ch[1];
128         }
129     }
130 }
131 int main()
132 {
133     //freopen("d:/in.txt","r",stdin);
134     int n,m;
135     srand(time(0));
136     while(scanf("%d%d",&n,&m)!=EOF)
137     {
138 
139         for(int i=1;i<=n;++i)
140         {
141             scanf("%d",&val[i]);
142         }
143         tot = 0;
144         for(int i=0;i<m;++i)
145         {
146              scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
147              q[i].id = i;
148         }
149         sort(q,q+m);
150         int root = 0;
151         int L=1,R=1;//初始在Treap中的节点所属区间[L,R),注意半闭半开区间
152         for(int i=0;i<m;i++)
153         {
154             while(L<q[i].l)
155             {
156                 if(L<R) remove(root,val[L]);
157                 L++;
158             }
159             if(R<L) R=L;
160             while(R<=q[i].r)
161             {
162                 insert(root,val[R]);
163                 R++;
164             }
165             ans[q[i].id]=query(root,q[i].k);
166         }
167         for(int i=0;i<m;i++) printf("%d
",ans[i]);
168     }
169     return 0;
170 }
View Code