fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fi first
  4. #define se second
  5. #define mp make_pair
  6. #define sz(x) (int)(x).size()
  7. #define all(x) (x).begin(), (x).end()
  8. #define yn(x) ((x) ? "Yes" : "No")
  9. #define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
  10. #define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)
  11. typedef long long ll;
  12. typedef pair <int, int> pii;
  13. typedef pair <ll, ll> pll;
  14. template <typename _Tp> bool maximize(_Tp &__a, const _Tp &__b) { if (__a < __b) { __a = __b; return true; } return false; }
  15. template <typename _Tp> bool minimize(_Tp &__a, const _Tp &__b) { if (__a > __b) { __a = __b; return true; } return false; }
  16. const int siz = 2e5 + 2;
  17. const int SIZ = 1e6 + 2;
  18. const int mod = 1e9 + 7;
  19. const int maxx = 2e9;
  20. const ll MAXX = 1e18;
  21. const string file = "3";
  22. mt19937 mt_rng_32(chrono::steady_clock::now().time_since_epoch().count());
  23. int rand_int(int lt, int rt) {
  24.     assert(lt <= rt);
  25.     return uniform_int_distribution <int> (lt, rt) (mt_rng_32);
  26. }
  27. struct implicit_treap {
  28.     struct node {
  29.         int lch, rch, pry, cnt, val;
  30.         node(int val = 0) : lch(0), rch(0), pry(rand_int(1, 1e9)), cnt(0), val(val) {
  31.         }
  32.     };
  33.     int root, len;
  34.     vector <node> tree;
  35.     implicit_treap() : root(0), len(0) {
  36.         tree.assign(1, node());
  37.     }
  38.     void recompute(int nd) {
  39.         if (nd) {
  40.             tree[nd].cnt = 1 + tree[tree[nd].lch].cnt + tree[tree[nd].rch].cnt;
  41.         }
  42.     }
  43.     void split(int crt, int key, int &lrt, int &rrt, int add = 0) {
  44.         if (!crt) {
  45.             lrt = rrt = 0;
  46.         } else {
  47.             int implicit_key = add + tree[tree[crt].lch].cnt;
  48.             if (key <= implicit_key) {
  49.                 split(tree[crt].lch, key, lrt, tree[crt].lch, add);
  50.                 rrt = crt;
  51.             } else {
  52.                 split(tree[crt].rch, key, tree[crt].rch, rrt, implicit_key + 1);
  53.                 lrt = crt;
  54.             }
  55.         }
  56.         recompute(crt);
  57.     }
  58.     void merge(int lrt, int rrt, int &crt) {
  59.         if (!lrt || !rrt) {
  60.             crt = (lrt) ? lrt : rrt;
  61.         } else if (tree[lrt].pry > tree[rrt].pry) {
  62.             merge(tree[lrt].rch, rrt, tree[lrt].rch);
  63.             crt = lrt;
  64.         } else {
  65.             merge(lrt, tree[rrt].lch, tree[rrt].lch);
  66.             crt = rrt;
  67.         }
  68.         recompute(crt);
  69.     }
  70.     template <typename _Tp>
  71.     void extract(ostream &stream, string fill, int crt) {
  72.         if (!crt) {
  73.             return;
  74.         }
  75.         extract <_Tp> (stream, fill, tree[crt].lch);
  76.         stream << _Tp(tree[crt].val) << fill;
  77.         extract <_Tp> (stream, fill, tree[crt].rch);
  78.     }
  79.     int new_node(int val) {
  80.         tree.push_back(val);
  81.         return sz(tree) - 1;
  82.     }
  83.     void insert(int pos, int val) {
  84.         assert(1 <= pos && pos <= len + 1);
  85.         int lrt, rrt;
  86.         split(root, pos - 1, lrt, rrt);
  87.         merge(lrt, new_node(val), lrt);
  88.         merge(lrt, rrt, root);
  89.         len++;
  90.     }
  91.     void rotate(int lt, int rt, int num) {
  92.         assert(1 <= lt && lt <= rt && rt <= len);
  93.         int lrt, mrt, rrt, trt;
  94.         split(root, lt - 1, lrt, mrt);
  95.         split(mrt, rt - lt + 1, mrt, rrt);
  96.         num %= tree[mrt].cnt;
  97.         split(mrt, tree[mrt].cnt - num, mrt, trt);
  98.         merge(lrt, trt, root);
  99.         merge(root, mrt, root);
  100.         merge(root, rrt, root);
  101.     }
  102.     void move(int lt, int rt, int pos) {
  103.         assert(1 <= lt && lt <= rt && rt <= len && 1 <= pos && pos <= len - (rt - lt + 1) + 1);
  104.         if (pos <= lt) {
  105.             rotate(pos, rt, rt - lt + 1);
  106.         } else {
  107.             rotate(lt, pos + (rt - lt + 1) - 1, pos - lt);
  108.         }
  109.     }
  110.     template <typename _Tp = int>
  111.     void extract(ostream &stream, string fill = " ") {
  112.         extract <_Tp> (stream, fill, root);
  113.         stream << "\n";
  114.     }
  115. };
  116. signed main() {
  117.     ios::sync_with_stdio(false);
  118.     cin.tie(nullptr);
  119.     int n, q; string s;
  120.     cin >> n >> q >> s;
  121.     s = ' ' + s;
  122.     implicit_treap tree;
  123.     rep (i, 1, n) {
  124.         tree.insert(i, s[i]);
  125.     }
  126.     while (q--) {
  127.         int l, r;
  128.         cin >> l >> r;
  129.         tree.move(l, r, n - (r - l + 1) + 1);
  130.     }
  131.     tree.extract <char> (cout, "");
  132.     return 0;
  133. }
  134.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/hdXbxz
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
179 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!