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 =http://www.mamicode.com/= t->lch->Rval) t->ans--; 75     if (t->rch && t->value =http://www.mamicode.com/= 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 r123     int ret = t2->ans;124     // get back to start position125     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, t3133     Split(root, t1, t3, r);134     Split(t1, t1, t2, l - 1);135     // merging them in this order: t2, t1, t3136     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 = http://www.mamicode.com/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 }