fork download 
  1. /*
  2. Author : DeMen100ns (Vo Khac Trieu)
  3. School: University of Science, VNU-HCM
  4. */
  5.  
  6. #include <bits/stdc++.h>
  7. #define endl '\n'
  8.  
  9. #define int long long
  10.  
  11. using namespace std;
  12.  
  13. const int N = 2e5 + 5;
  14. const long long INF = numeric_limits<long long>::max() / 2;
  15. const int MAXA = 1e9;
  16. const int BL = 430;
  17.  
  18. int a[N];
  19. vector <int> block[N];
  20. int L[N], R[N], sum[N], rev[N];
  21. int cntblock = 0, n;
  22.  
  23. void normalize(int id){
  24.     if (rev[id]){
  25.         rev[id] ^= 1;
  26.         reverse(block[id].begin(), block[id].end());
  27.     }
  28. }
  29.  
  30. void split(int u){
  31.     //split u-(u+1)
  32.  
  33.     for(int i = 1; i <= cntblock; ++i){
  34.         if (L[i] <= u && u <= R[i]){
  35.             if (u == R[i]) return;
  36.  
  37.             normalize(i);
  38.             for(int j = cntblock; j >= i + 1; --j){
  39.                 // block[j + 1] = block[j];
  40.                 swap(block[j + 1], block[j]); //-> O(1)
  41.                 L[j + 1] = L[j]; R[j + 1] = R[j];
  42.                 sum[j + 1] = sum[j]; rev[j + 1] = rev[j];
  43.             } ++cntblock;
  44.  
  45.             //i, i + 1
  46.             //L[i] - u, u + 1 - R[i]
  47.             L[i + 1] = u + 1, R[i + 1] = R[i];
  48.             R[i] = u;
  49.  
  50.             sum[i] = sum[i + 1] = 0;
  51.             rev[i] = rev[i + 1] = 0;
  52.  
  53.             vector <int> v = block[i];
  54.             block[i].clear(); block[i + 1].clear();
  55.  
  56.             for(int j = 0, id = L[i]; j < v.size(); ++j, ++id){
  57.                 if (id <= u){
  58.                     block[i].push_back(v[j]);
  59.                     sum[i] += v[j];
  60.                 } else {
  61.                     block[i + 1].push_back(v[j]);
  62.                     sum[i + 1] += v[j];
  63.                 }
  64.             } 
  65.  
  66.             return;
  67.             //[1 2 3] [4 5 | 6] [7 8 9]
  68.             //[1 2 3] [4 5] [6] [7 8 9]
  69.         }
  70.     }
  71. }
  72.  
  73. void reverse(int l, int r){
  74.     split(l - 1); split(r);
  75.  
  76.     int Lb = n + 1, Rb = 0;
  77.     for(int b = 1; b <= cntblock; ++b){
  78.         if (l <= L[b] && R[b] <= r){
  79.             Lb = min(Lb, b);
  80.             Rb = b;
  81.         }
  82.     }
  83.  
  84.     for(int l = Lb, r = Rb; l < r; ++l, --r){
  85.         swap(block[l], block[r]);
  86.         swap(sum[l], sum[r]);
  87.         swap(rev[l], rev[r]);
  88.     }
  89.  
  90.     int lcur = 1;
  91.     for(int b = 1; b <= cntblock; ++b){
  92.         L[b] = lcur; R[b] = lcur + block[b].size() - 1;
  93.         lcur += block[b].size();
  94.     }
  95.  
  96.     for(int b = Lb; b <= Rb; ++b){
  97.         rev[b] ^= 1;
  98.     }
  99. }
  100.  
  101. void rebuild(){
  102.     int id = 0;
  103.     for(int i = 1; i <= cntblock; ++i){
  104.         normalize(i);
  105.         for(int v : block[i]){
  106.             a[++id] = v;
  107.         }
  108.         block[i].clear();
  109.         L[i] = R[i] = 0;
  110.         sum[i] = rev[i] = 0;
  111.     }
  112.     cntblock = 0;
  113.  
  114.     for(int i = 1; i <= n; ++i){
  115.         if (i % BL == 1) {
  116.             cntblock++;
  117.         }
  118.  
  119.         if (L[cntblock] == 0) L[cntblock] = R[cntblock] = i;
  120.         else R[cntblock] = i;
  121.  
  122.         sum[cntblock] += a[i];
  123.  
  124.         block[cntblock].push_back(a[i]);
  125.     }    
  126. }
  127.  
  128. void solve(){
  129.     int q; cin >> n >> q;
  130.     for(int i = 1; i <= n; ++i){
  131.         cin >> a[i];
  132.  
  133.         if (i % BL == 1) {
  134.             cntblock++;
  135.         }
  136.  
  137.         if (L[cntblock] == 0) L[cntblock] = R[cntblock] = i;
  138.         else R[cntblock] = i;
  139.  
  140.         sum[cntblock] += a[i];
  141.  
  142.         block[cntblock].push_back(a[i]);
  143.     }
  144.  
  145.     int cnt = 0;
  146.     while (q--){
  147.         int type; cin >> type;
  148.         if (type == 1){
  149.             int u, v; cin >> u >> v;
  150.             reverse(u, v);
  151.         } else {
  152.             int l, r; cin >> l >> r;
  153.             int ans = 0;
  154.             for(int b = 1; b <= cntblock; ++b){
  155.                 //Case 1: Khong giao
  156.                 if (R[b] < l || L[b] > r) continue;
  157.  
  158.                 //Case 2: Nam trong
  159.                 if (l <= L[b] && R[b] <= r){
  160.                     ans += sum[b];
  161.                     continue;
  162.                 }
  163.  
  164.                 normalize(b);
  165.  
  166.                 for(int j = 0, i = L[b]; i <= R[b]; ++i, ++j){
  167.                     if (l <= i && i <= r){
  168.                         ans += block[b][j];
  169.                     }
  170.                 }
  171.             }
  172.             cout << ans << endl;
  173.         }
  174.  
  175.         cnt = (cnt + 2) % BL;
  176.         if (cnt <= 1){
  177.             rebuild();
  178.         }
  179.     }
  180. }
  181.  
  182. signed main(){
  183.     ios_base::sync_with_stdio(0); cin.tie(0);
  184.  
  185.     int t = 1; // cin >> t;
  186.     for(int test = 1; test <= t; ++test){
  187.         solve();
  188.     }
  189. }
  190.  
Success #stdin #stdout 0.01s 9992KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Nm8MJr
language:
C++14 (gcc 8.3)
created:
5 hours 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!