Treap模板

  1 /*************************************************************************
  2     > File Name: D.cpp
  3     > Author: Stomach_ache
  4     > Mail: sudaweitong@gmail.com
  5     > Created Time: 2014年10月03日 星期五 14时55分53秒
  6     > Propose: 
  7  ************************************************************************/
  8 #include <cmath>
  9 #include <ctime>
 10 #include <string>
 11 #include <cstdio>
 12 #include <vector>
 13 #include <fstream>
 14 #include <cstring>
 15 #include <iostream>
 16 #include <algorithm>
 17 using namespace std;
 18 /*Let's fight!!!*/
 19 
 20 typedef struct TreeNode* pTree;
 21 pTree null, root;
 22 struct TreeNode {
 23     int value, size, prior;
 24     //======
 25     int ans, Lval, Rval;
 26     //======
 27     pTree lch, rch;
 28     TreeNode() : value(0), size(0) {
 29           lch = rch = NULL;
 30     }
 31     TreeNode(int val);
 32 };
 33 
 34 TreeNode::TreeNode(int val) : value(val), size(1) {
 35     lch = rch = NULL;
 36     prior = rand() % 1000000000 + 1;
 37     Lval = Rval = val;
 38     ans = 1;
 39 }
 40 
 41 int GetRightValue(pTree t) {
 42     ｉf (!t->rch) return t->value;
 43     return GetRightValue(t->rch);
 44 }
 45 
 46 int GetLeftValue(pTree t) {
 47     if (!t->lch) return t->value;
 48     return GetLeftValue(t->lch);
 49 }
 50 
 51 int GetSize(pTree t) {
 52       if (!t) return 0;
 53       return t->size;
 54 }
 55 
 56 int GetAns(pTree t) {
 57     if (!t) return 0;
 58     return t->ans;
 59 }
 60 
 61 void pushUp(pTree t) {
 62     if (!t) return ;
 63     t->size = 1 + GetSize(t->lch) + GetSize(t->rch);
 64     if (t->lch) 
 65         t->Lval = t->lch->Lval;
 66     else 
 67         t->Lval = t->value;
 68     if (t->rch)
 69           t->Rval = t->rch->Rval;
 70     else 
 71           t->Rval = t->value;
 72 
 73     t->ans = 1 + GetAns(t->lch) + GetAns(t->rch);
 74     if (t->lch && t->value == t->lch->Rval) t->ans--;
 75     if (t->rch && t->value == t->rch->Lval) t->ans--;
 76 }
 77 
 78 void Split(pTree t, pTree &l, pTree &r, int key, int add = 0) {
 79     if (!t) {
 80         l = r = NULL;
 81         return ;
 82     }
 83 
 84     int cur_add = add + GetSize(t->lch);
 85     if (cur_add >= key) Split(t->lch, l, t->lch, key, add), r = t;
 86     else Split(t->rch, t->rch, r, key, add + GetSize(t->lch) + 1), l = t;
 87     pushUp(l);
 88     pushUp(r);
 89 }
 90 
 91 void Merge(pTree &t, pTree l, pTree r) {
 92       // Merge two subtree
 93     pushUp(l);
 94     pushUp(r);
 95     if (!l|| !r) {
 96           t = l ? l : r;
 97         return ;
 98     }
 99 
100     if (l->prior > r->prior) Merge(l->rch, l->rch, r), t = l;
101     else Merge(r->lch, l, r->lch), t = r;
102     pushUp(t);
103 }
104 
105 void insert(pTree &t, int val) {
106     pTree tmp = new TreeNode(val);
107     Merge(t, t, tmp);
108 }
109 
110 void write(pTree t) {
111       if (!t) return ;
112     write(t->lch);
113     cout << t->value << " ";
114     write(t->rch);
115 }
116 
117 int get(pTree root, int l, int r) {
118       pTree t1, t2, t3;
119     // spliting tree in three segments t1, t2, t3;
120     Split(root, t1, t3, r);
121     Split(t1, t1, t2, l - 1);
122     // t2 = segment from l to r
123     int ret = t2->ans;
124     // get back to start position
125     Merge(t1, t1, t2);
126     Merge(root, t1, t3);
127     return ret;
128 }
129 
130 void replacing(pTree &root, int l, int r) {
131       pTree t1, t2, t3;
132     // spliting tree in three segments t1, t2, t3
133     Split(root, t1, t3, r);
134     Split(t1, t1, t2, l - 1);
135     // merging them in this order: t2, t1, t3
136     Merge(t1, t2, t1);
137     Merge(root, t1, t3);
138 }
139 
140 void read(int &res) {
141     res = 0;
142     char c = ' ';
143     while (c < '0' || c > '9') c = getchar();
144     while (c >= '0' && c <= '9') res = (res<<3) + (res<<1) + c - '0', c = getchar();
145 }
146 
147 int main(void) {
148       srand(time(0));
149     //null = new TreeNode();
150     //null->lch = null->rch = null;
151     //null->size = null->value = 0;
152 
153     ios::sync_with_stdio(false);
154     int tcase;
155     read(tcase);
156     while (tcase--) {
157           root = NULL;
158           int N, M, val, op, l, r;
159         read(N);
160         for (int i = 1; i <= N; i++) {
161               read(val);
162             insert(root, val);
163         }
164         read(M);
165         while (M--) {
166               read(op), read(l), read(r);
167             if (op == 1) {
168                   int res = get(root, l, r);
169                 cout << res << endl;
170             } else {
171                   replacing(root, l, r);
172             }
173         }
174     }
175 
176     return 0;
177 }