fork(1) download 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. using namespace std;
  4.  
  5. template<typename Key>
  6. struct TreapNode {
  7.     Key key;
  8.     int priority, size;
  9.     TreapNode *left, *right;
  10.     TreapNode(const Key& k) : key(k), priority(rand()), size(1), left(nullptr), right(nullptr) {}
  11. };
  12.  
  13. template<typename Key>
  14. class Treap {
  15.     TreapNode<Key>* root = nullptr;
  16.  
  17.     int getSize(TreapNode<Key>* t) {
  18.         return t ? t->size : 0;
  19.     }
  20.  
  21.     void update(TreapNode<Key>* t) {
  22.         if (t) t->size = 1 + getSize(t->left) + getSize(t->right);
  23.     }
  24.  
  25.     void split(TreapNode<Key>* t, const Key& key, TreapNode<Key>*& l, TreapNode<Key>*& r) {
  26.         if (!t) l = r = nullptr;
  27.         else if (key < t->key)
  28.             split(t->left, key, l, t->left), r = t;
  29.         else
  30.             split(t->right, key, t->right, r), l = t;
  31.         update(t);
  32.     }
  33.  
  34.     TreapNode<Key>* merge(TreapNode<Key>* l, TreapNode<Key>* r) {
  35.         if (!l || !r) return l ? l : r;
  36.         if (l->priority > r->priority) {
  37.             l->right = merge(l->right, r);
  38.             update(l);
  39.             return l;
  40.         } else {
  41.             r->left = merge(l, r->left);
  42.             update(r);
  43.             return r;
  44.         }
  45.     }
  46.     void update_all(TreapNode<Key>* t) {
  47.         if (!t) return;
  48.         update_all(t->left);
  49.         update_all(t->right);
  50.         update(t);
  51.     }
  52.  
  53. public:
  54.     void insert (TreapNode<Key>* & t, TreapNode<Key>* it) {
  55. 	    if (!t) {t = it; return;}
  56. 	    if (it->priority > t->priority)
  57. 	        split (t, it->key, it->left, it->right),  t = it;
  58. 	    else
  59. 	        insert (t->key <= it->key ? t->right : t->left, it);
  60. 	    update(t);
  61. 	}
  62. 	void insert(const Key& key) {
  63.         insert(root, new TreapNode<Key>(key));
  64.     }
  65. 	/*
  66.     void insert(const Key& key) {
  67.         TreapNode<Key> *l, *r;
  68.         split(root, key, l, r);
  69.         root = merge(merge(l, new TreapNode<Key>(key)), r);
  70.     }*/
  71.  
  72.     TreapNode<Key>* erase(TreapNode<Key>* t, const Key& key) {
  73. 	    if (!t) return nullptr;
  74. 	    if (key == t->key)
  75. 	        return merge(t->left, t->right);
  76. 	    else if (key < t->key)
  77. 	        t->left = erase(t->left, key);
  78. 	    else
  79. 	        t->right = erase(t->right, key);
  80. 	    update(t);
  81. 	    return t;
  82. 	}
  83.  
  84.     void erase(const Key& key) {
  85.     	root = erase(root,key);
  86.     }
  87.  
  88.     int count_less_equal(const Key& key) {
  89.         TreapNode<Key> *cur = root;
  90.         int ans = 0;
  91.         while(cur){
  92.         	if(key>=cur->key) ans+=1+getSize(cur->left), cur = cur->right;
  93.         	else cur = cur->left;
  94.         }
  95.         return ans;
  96.     }
  97.  
  98.     void build(const vector<Key>& sorted_keys) {
  99.         stack<TreapNode<Key>*> stk;
  100.         for (const auto& key : sorted_keys) {
  101.             TreapNode<Key>* cur = new TreapNode<Key>(key);
  102.             TreapNode<Key>* last = nullptr;
  103.  
  104.             while (!stk.empty() && stk.top()->priority < cur->priority) {
  105.                 last = stk.top();
  106.                 stk.pop();
  107.             }
  108.  
  109.             if (!stk.empty()) stk.top()->right = cur;
  110.             cur->left = last;
  111.             stk.push(cur);
  112.         }
  113.  
  114.         // Root is bottom of stack
  115.         while (stk.size() > 1) stk.pop();
  116.         root = stk.top();
  117.  
  118.         update_all(root);
  119.     }
  120. };
  121.  
  122.  
  123. const int N = 100001;
  124.  
  125. Treap<pair<int,int>> bit[N];
  126.  
  127. void insert(int x, int y)
  128. {
  129. 	for(int i = x; i < N; i += i & -i)
  130. 		bit[i].insert({y, x});
  131. }
  132.  
  133. void remove(int x, int y)
  134. {
  135. 	for(int i = x; i < N; i += i & -i)
  136. 		bit[i].erase({y, x});
  137. }
  138.  
  139. int query(int x, int y)
  140. {
  141. 	int ans = 0;
  142. 	for(int i = x; i > 0; i -= i & -i){
  143. 		ans += bit[i].count_less_equal({y+1, 0});
  144. 	}
  145. 	return ans;
  146. }
  147.  
  148.  
  149. int main(){
  150. 	ios::sync_with_stdio(false);
  151. 	cin.tie(0);
  152. 	int n,q;
  153. 	cin>>n>>q;
  154. 	vector<int> arr(n+1);
  155. 	vector<vector<pair<int,int>>> sorted_keys(N);
  156. 	for(int i=1;i<=n;++i){
  157. 		cin>>arr[i];
  158. 		//insert(i,arr[i]);
  159. 		for(int j = i; j < N; j += j & -j)
  160. 			sorted_keys[j].emplace_back(i, arr[i]);
  161. 	}
  162. 	for(int i=1;i<=n;++i){
  163. 		for(auto x: sorted_keys[i])
  164. 			bit[i].insert(x);
  165. 	}
  166. 	while(q--){
  167. 		string op;
  168. 		cin>>op;
  169. 		if(op=="M"){
  170. 			int i,x;
  171. 			cin>>i>>x;
  172. 			remove(i,arr[i]);
  173. 			insert(i,x);
  174. 			arr[i]=x;
  175. 		}else{
  176. 			int p,q,x;
  177. 			cin>>p>>q>>x;
  178. 			cout<<query(q,x)-query(p-1,x)<<endl;
  179. 		}
  180. 	}
  181. }
Success #stdin #stdout 0.01s 5584KB
comments (?)
stdin 
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
stdout 
3
4
5
3
https://ideone.com/G1YvZ1
Treap
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!