As another one of their crazy antics, the N (1 ≤ N ≤ 100,000) cows want Farmer John to race against the clock to answer some of their pressing questions.
The cows are lined up in a row from 1 to N, and each one is holding a sign representing a number, Ai (1 ≤ Ai≤ 1,000,000,000). The cows need FJ to perform Q (1 ≤ Q ≤ 50,000) operations, which can be either of the following:
- Modify cow i's number to X (1 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter M followed by the space-separated numbers i and X.
- Count how many cows in the range [P, Q] (1 ≤ P ≤ Q ≤ N) have Ai ≤ X (0 ≤ X ≤ 1,000,000,000). This will be represented in the input as a line containing the letter C followed by the space-separated numbers P, Q, and X.
Of course, FJ would like your help.
Input
The first line gives the integers N and Q, and the next N lines give the initial values of Ai. Finally, the next Q lines each contain a query of the form "M i X" or "C P Q X".
Output
Print the answer to each 'C' query, one per line.
Example
Input: 4 6 3 4 1 7 C 2 4 4 M 4 1 C 2 4 4 C 1 4 5 M 2 10 C 1 3 9 Output: 2 3 4 2
题意：给出一段序列，要求有两种操作， 1 修改一个位置的数字， 2 查询一段区间内的小于val的数字有多少个。
sl: 这是区间查询，所以用线段树维护就好了，但是查询小于val的数字有多少个，所以直接随便用一个平衡树求一个rank就好了。 最近刚刚学了SBT.
试了试模板，还是要手敲为妙。 加了挂还是超时，不知道为何。 应该有好方法。 用treap貌似能过？
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cmath> 6 7 using namespace std; 8 9 const int maxn = 100010; 10 11 struct Node { 12 int key, val; 13 Node(){}; 14 Node( int a, int b) { key = a; val = b; } 15 bool operator < (Node b) { return val < b.val; } 16 bool operator <= (Node b) { return val <= b.val; } 17 bool operator > (Node b) { return val > b.val; } 18 bool operator >= (Node b) { return val >= b.val; } 19 bool operator == (Node b) { return val == b.val; } 20 Node operator + ( int a) { 21 return Node(key, val+a) > Node(key, val) ? Node(key, val+a) : Node(key, val-a); 22 } 23 }; 24 25 int sz[maxn* 30]; 26 int key[maxn* 30]; 27 int lch[maxn* 30]; 28 int rch[maxn* 30]; 29 int tot; 30 31 template<typename Type> 32 class SBT 33 { 34 public: 35 SBT() { Clear(); } 36 void Clear() { root = 0; lch[ 0] = rch[ 0] = sz[ 0] = 0; } 37 static void ClearAll() { tot = 0; } 38 int Size() { return sz[root]; } 39 bool Empty() { return 0 == sz[root]; } 40 bool Find(Type k) { return Find(root, k); } 41 void InsertR(Type k) { Insert(root, k); } // 可重复插入 42 void Insert(Type k) { if (!Find(k)) Insert(root, k); } 43 void Delete(Type k) { if (Find(k)) Delete(root, k); } 44 void DeleteSmaller(Type k) { DeleteSmaller(root, k); } 45 int GetRank(Type k) { return GetRank(root, k); } 46 Type GetKth( int k) { return GetKth(root, k); } 47 Type GetMin() { return GetKth(root, 1); } 48 Type GetMax() { return GetKth(root, Size()); } 49 Type GetPre(Type k) { return GetPre(root, k); } 50 Type GetSuc(Type k) { return GetSuc(root, k); } 51 int GetSmaller(Type k) { return GetSmaller(root, k); } // 返回小于k的元素的个数 52 53 private: 54 void LeftRotate( int &t) { 55 int k = rch[t]; 56 rch[t] = lch[k]; 57 lch[k] = t; 58 sz[k] = sz[t]; 59 sz[t] = 1 + sz[lch[t]] + sz[rch[t]]; 60 t = k; 61 } 62 void RightRotate( int &t) { 63 int k = lch[t]; 64 lch[t] = rch[k]; 65 rch[k] = t; 66 sz[k] = sz[t]; 67 sz[t] = 1 + sz[lch[t]] + sz[rch[t]]; 68 t = k; 69 } 70 void Maintain( int &t, bool flag) { 71 if ( 0 == t) return ; 72 if ( false == flag) { 73 if (sz[lch[lch[t]]] > sz[rch[t]]) { 74 RightRotate(t); 75 } else if (sz[rch[lch[t]]] > sz[rch[t]]) { 76 LeftRotate(lch[t]); 77 RightRotate(t); 78 } else { 79 return ; 80 } 81 } else { 82 if (sz[rch[rch[t]]] > sz[lch[t]]) { 83 LeftRotate(t); 84 } else if (sz[lch[rch[t]]] > sz[lch[t]]) { 85 RightRotate(rch[t]); 86 LeftRotate(t); 87 } else { 88 return ; 89 } 90 } 91 Maintain(lch[t], false); 92 Maintain(rch[t], true); 93 Maintain(t, false); 94 Maintain(t, true); 95 } 96 Type GetPre( int t, Type k) { 97 if ( 0 == k) return k; 98 if (k <= key[t]) return GetPre(lch[t], k); 99 Type tmp = GetPre(rch[t], k); 100 if (tmp == k) return key[t]; 101 return tmp; 102 } 103 Type GetSuc( int t, Type k) { 104 if ( 0 == root) return k; 105 if (k >= key[t]) return GetSuc(rch[t], k); 106 Type tmp = GetSuc(lch[t], k); 107 if (tmp == k) return key[t]; 108 return tmp; 109 } 110 Type GetKth( int t, int k) { 111 if (sz[lch[t]] >= k) return GetKth(lch[t], k); 112 if (sz[lch[t]] == k - 1) return key[t]; 113 return GetKth(rch[t], k - sz[lch[t]] - 1); 114 } 115 int GetRank( int t, Type k) { 116 if ( 0 == t) return 0; 117 if (k < key[t]) return GetRank(lch[t], k); 118 return sz[lch[t]] + 1 + GetRank(rch[t], k); 119 } 120 int GetSmaller( int t, Type k) { 121 if ( 0 == t) return 0; 122 if (k <= key[t]) return GetSmaller(lch[t], k); 123 return sz[lch[t]] + 1 + GetSmaller(rch[t], k); 124 } 125 bool Find( int t, Type k) { 126 if ( 0 == t) return false; 127 else if (k < key[t]) return Find(lch[t], k); 128 else return (key[t] == k || Find(rch[t], k)); 129 } 130 void Insert( int &t, Type k) { 131 if ( 0 == t) { 132 t = ++tot; 133 lch[t] = rch[t] = 0; 134 sz[t]= 1; 135 key[t] = k; 136 return ; 137 } 138 sz[t]++; 139 if (k < key[t]) Insert(lch[t], k); 140 else Insert(rch[t], k); 141 Maintain(t, k >= key[t]); 142 } 143 void DeleteSmaller( int &t , Type k) { 144 if ( 0 == t) return ; 145 if ( key[t] < k ) { 146 t = rch[t]; 147 DeleteSmaller(t , key); 148 } else { 149 DeleteSmaller(lch[t] , k); 150 sz[t] = 1 + sz[lch[t]] + sz[rch[t]]; 151 } 152 } 153 Type Delete( int &t, Type k) { 154 sz[t]--; 155 if ((key[t] == k) || (k < key[t] && 0 == lch[t]) || (k > key[t] && 0 == rch[t])) { 156 Type tmp = key[t]; 157 if ( 0 == lch[t] || 0 == rch[t]) { 158 t = lch[t] + rch[t]; 159 } else { 160 key[t] = Delete(lch[t], key[t] + 1); 161 } 162 return tmp; 163 } else { 164 if (k < key[t]) { 165 return Delete(lch[t], k); 166 } else { 167 return Delete(rch[t], k); 168 } 169 } 170 } 171 private: 172 int root; 173 }; 174 175 SBT < int> sbt[maxn<< 2]; 176 int a[maxn]; 177 178 void build( int L, int R, int o) { 179 sbt[o].Clear(); 180 for( int i=L;i<=R;i++) { 181 sbt[o].InsertR(a[i]); 182 } 183 if(L==R) return ; 184 int mid=(L+R)>> 1; 185 build(L,mid,o<< 1); 186 build(mid+ 1,R,o<< 1| 1); 187 } 188 void Update( int L, int R, int o, int pos, int val) { 189 sbt[o].Delete(a[pos]); 190 sbt[o].InsertR(val); 191 if(L==R) return ; 192 int mid=(L+R)>> 1; 193 if(pos<=mid) Update(L,mid,o<< 1,pos,val); 194 if(pos>mid) Update(mid+ 1,R,o<< 1| 1,pos,val); 195 } 196 197 int Query( int L, int R, int o, int ls, int rs, int val) { 198 if(ls<=L&&rs>=R) { 199 return sbt[o].GetRank(val); 200 } 201 int mid=(L+R)>> 1; int res= 0; 202 if(ls<=mid) res+=Query(L,mid,o<< 1,ls,rs,val); 203 if(rs>mid) res+=Query(mid+ 1,R,o<< 1| 1,ls,rs,val); 204 return res; 205 } 206 inline int read() 207 { 208 int m= 0; 209 char ch=getchar(); 210 while(ch< ' 0 '||ch> ' 9 '){ch=getchar(); } 211 while(ch>= ' 0 '&&ch<= ' 9 '){m=m* 10+ch- ' 0 '; ch=getchar(); } 212 return m; 213 } 214 int main() { 215 int n,m; char op[ 3]; 216 int ls,rs,val; 217 while(scanf( " %d %d ",&n,&m)== 2) { 218 for( int i= 1;i<=n;i++) { 219 a[i]=read(); 220 } 221 SBT< int> :: ClearAll(); 222 build( 1,n, 1); 223 for( int i= 1;i<=m;i++) { 224 scanf( " %s ",op); 225 if(op[ 0]== ' C ') { 226 ls=read(); rs=read(); val=read(); 227 int ans=Query( 1,n, 1,ls,rs,val); 228 printf( " %d\n ",ans); 229 } 230 else { 231 ls=read(); rs=read(); 232 Update( 1,n, 1,ls,val); 233 a[ls]=val; 234 } 235 } 236 } 237 return 0;
238 }