hpnq

EBANINA

Sep 11th, 2022
160
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.22 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define loop(x, n) for(ll i = x; i < n; i++ )
  4. #define pb push_back
  5. #define MOD ll(1e9+7)
  6. #define all(x) x.begin(), x.end()
  7. #define f first
  8. #define s second
  9. #define DEBUG 1
  10. typedef long long ll;
  11. using namespace std;
  12. int next(int n, int k){
  13.     return (n+k)%26;
  14. }
  15.  
  16. ///
  17. struct Node{
  18.     int prior, size = 1;
  19.     int value;
  20.     Node *l = 0, *r = 0;
  21.     Node(int _key) {value = _key, prior = rand();}
  22. };
  23. ///
  24.  
  25. typedef pair<Node*, Node*> Pair;
  26.  
  27. int size(Node *v){return v ? v->size : 0;}
  28. void upd(Node *v){v->size = size(v->l) + size(v->r) + 1;}
  29.  
  30.  
  31. Node *merge(Node *l, Node *r){
  32.     if(!l) return r;
  33.     if(!r) return l;
  34.     if(l->prior > r->prior){
  35.         l->r = merge(l->r, r);
  36.         upd(l);
  37.         return l;
  38.     }else{
  39.         r->l = merge(l, r->l);
  40.         upd(l);
  41.         return r;
  42.     }
  43. }
  44.  
  45. Pair split(Node *p, int k){
  46.     if(!p) return {0, 0};
  47.     if(size(p->l) + 1 <= k){
  48.         Pair q = split(p->r, k - size(p->l) - 1);
  49.         p->l = q.second;
  50.         upd(p);
  51.         return {q.first, p};
  52.     }else{
  53.         Pair q = split(p->l, k);
  54.         p->l = q.second;
  55.         upd(p);
  56.         return {q.first, p};
  57.     }
  58. }
  59.  
  60. //Node *root = 0;
  61. Node *root = 0;
  62.  
  63. Node* insert( int x) {
  64.     Pair q= split(root, x);
  65.     Node *t = new Node(x);
  66. //    cout << q.f << " " << q.s << "\n";
  67.     root = merge(q.first, merge(t, q.second ));
  68. //    cout <<root->size <<"\n";
  69.     return root;
  70. }
  71. ///////
  72. ///////
  73.  
  74.  
  75. Node* ctrlx (int l, int r) {
  76.     Pair q1 = split(root, r);
  77.     Pair q2 = split(q1.first, l);
  78.     root = merge(q2.first, q1.second);
  79.     return q2.second;
  80. }
  81.  
  82. Node*  ctrlv (Node *root, Node *v, int k) {
  83.     Pair q = split(root, k);
  84.     root = merge(q.first, merge(v, q.second));
  85.     return root;
  86. }
  87.  
  88.  
  89. ///////
  90. ///////
  91.  
  92. vector<Node*> abc(26);
  93.  
  94. void solve(){
  95.     int n, m;
  96.     cin >> n >> m;
  97.     string a;
  98.     cin >> a;
  99.     ///построить дд /// nlogn
  100. //    loop(0, n){
  101. //        abc[a[i]-'a'] = insert(abc[a[i]-'a'], i);
  102. //    }
  103.     insert( 1);
  104.     insert( 2);
  105.     insert( 3);
  106.     insert( 4);
  107.     loop(0, m){
  108.         int q;
  109.         cin >> q;
  110.         if(q == 1){
  111.             //next
  112.             int r, l, k;
  113.             cin >> l >> r >> k;
  114.             Pair v;
  115.             ctrlx( l, r);
  116.             /*
  117.             loop(0, 26){
  118. //                cout  << k <<'\n';
  119.                 if(abc[i]!= 0) {
  120.                     v = ctrlx(abc[i], l, r);
  121. //                    cout << v.s->size <<"\n";
  122.                     abc[i] = v.s;
  123.                     abc[(i+k)%26] = ctrlv(abc[(i+k)%26], v.f, l);
  124.                 }
  125.  
  126.  
  127.             }
  128.             */
  129.  
  130.         }else{
  131.             // f(l, r)
  132.             int l, r;
  133.             cin >> l >> r;
  134.             cout << root->size <<" ";
  135.  
  136.             /*
  137.             loop(0, 26){
  138.                 cout << abc[i] <<" ";
  139.  
  140.             }
  141.             */
  142.             cout <<"\n";
  143.  
  144.         }
  145.     }
  146.  
  147. }
  148.  
  149. int main() {
  150. #ifdef DEBUG
  151.     freopen("text.txt", "r", stdin);
  152.     cout <<"DEBUG" <<"\n";
  153. #else
  154. #endif
  155. //    int t;
  156. //    cin >> t;
  157. //    loop(0, t) {
  158. //        solve();
  159. ////    cout<< solve_all("ananas");
  160. //
  161. //    }
  162.     solve();
  163. //    int n;
  164. //    cin >> n;
  165. //    cout << n;
  166.     return 0;
  167.  
  168.  
  169. }
Add Comment
Please, Sign In to add comment