fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ii pair<int, int>
  6. #define fi first
  7. #define se second
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 2e5;
  12. const int block_size = 447;
  13. const int max_cnt = maxn/block_size + 316;
  14.  
  15. int n, q, L[maxn + 10], R[maxn + 10], cnt_block = 0;
  16. ll a[maxn + 10], sum[maxn + 10];
  17. bool rev[maxn + 10];
  18. vector<ll> block[maxn + 10];
  19.  
  20. int get_id(int p)
  21. {
  22.     return p / block_size + 1; // 1-based block id
  23. }
  24.  
  25. void lazy(int id)
  26. {
  27.     if (id < 1 || id > cnt_block) return;
  28.     if (rev[id])
  29.     {
  30.         rev[id] = false;
  31.         reverse(block[id].begin(), block[id].end());
  32.     }
  33. }
  34.  
  35. void split(int p)
  36. {
  37.     if (p <= 0 || p >= n) return; // guard: only split meaningful positions
  38.     for (int i = 1; i <= cnt_block; i++)
  39.         if (L[i] <= p && p <= R[i])
  40.         {
  41.             if (p == R[i]) return;
  42.             // shift blocks right by one starting from cnt_block down to i+1
  43.             for (int j = cnt_block; j > i; j--)
  44.             {
  45.                 swap(block[j + 1], block[j]);
  46.                 L[j + 1] = L[j];
  47.                 R[j + 1] = R[j];
  48.                 sum[j + 1] = sum[j];
  49.                 rev[j + 1] = rev[j];
  50.             }
  51.             cnt_block++;
  52.             lazy(i);
  53.             vector<ll> tmp = block[i];
  54.             block[i].clear();
  55.             block[i + 1].clear();
  56.             int oldLi = L[i];
  57.             int oldRi = R[i];
  58.             L[i + 1] = p + 1;
  59.             R[i + 1] = oldRi;
  60.             R[i] = p;
  61.             L[i] = oldLi;
  62.  
  63.             sum[i] = sum[i + 1] = 0;
  64.             rev[i] = rev[i + 1] = 0;
  65.  
  66.             // redistribute elements from tmp (which correspond to positions oldLi..oldRi)
  67.             for (int offset = 0; offset < (int)tmp.size(); offset++)
  68.             {
  69.                 int pos = oldLi + offset;
  70.                 int nxt_i = i + (pos > p);
  71.                 block[nxt_i].push_back(tmp[offset]);
  72.                 sum[nxt_i] += tmp[offset];
  73.             }
  74.             return;
  75.         }
  76. }
  77.  
  78. int find_id(int p)
  79. {
  80.     if (p <= 0 || p > n) return 0;
  81.     for (int i = 1; i <= cnt_block; i++)
  82.         if (L[i] <= p && p <= R[i])
  83.             return i;
  84.     return 0;
  85. }
  86.  
  87. void rebuild()
  88. {
  89.     // gather all elements in order
  90.     vector<ll> v;
  91.     v.reserve(n + 5);
  92.     for (int i = 1; i <= cnt_block; i++)
  93.     {
  94.         lazy(i);
  95.         for (ll x : block[i]) v.push_back(x);
  96.         block[i].clear();
  97.     }
  98.     // v should have size n
  99.     if ((int)v.size() != n)
  100.     {
  101.         // If there's discrepancy, try to pad or truncate safely
  102.         v.resize(n, 0);
  103.     }
  104.  
  105.     // clear sums and rev
  106.     for (int i = 1; i <= cnt_block; i++) { sum[i] = 0; rev[i] = 0; }
  107.  
  108.     // recompute cnt_block based on n
  109.     cnt_block = get_id(n);
  110.  
  111.     // ensure block vectors cleared for ids we'll use
  112.     for (int id = 1; id <= cnt_block; id++) block[id].clear();
  113.  
  114.     // fill blocks from v (v is 0-based)
  115.     for (int i = 1; i <= n; i++)
  116.     {
  117.         int id = get_id(i);
  118.         ll val = v[i - 1];
  119.         block[id].push_back(val);
  120.         sum[id] += val;
  121.     }
  122.  
  123.     // recompute L/R
  124.     int cur = 1;
  125.     for (int id = 1; id <= cnt_block; id++)
  126.     {
  127.         L[id] = cur;
  128.         R[id] = cur + (int)block[id].size() - 1;
  129.         cur = R[id] + 1;
  130.     }
  131. }
  132.  
  133. void rever(int l, int r)
  134. {
  135.     if (l >= r) return;
  136.     split(l - 1);
  137.     split(r);
  138.  
  139.     int id_l = find_id(l);
  140.     int id_r = find_id(r);
  141.     if (id_l == 0 || id_r == 0) return;
  142.  
  143.     // swap whole blocks between id_l..id_r
  144.     for (int i = id_l, j = id_r; i < j; i++, j--)
  145.     {
  146.         swap(block[i], block[j]);
  147.         swap(rev[i], rev[j]);
  148.         swap(sum[i], sum[j]);
  149.     }
  150.     // toggle rev for blocks inside [id_l, id_r]
  151.     for (int i = id_l; i <= id_r; i++)
  152.         rev[i] = !rev[i];
  153.  
  154.     // recompute L/R according to current block sizes
  155.     int cur = 1;
  156.     for (int i = 1; i <= cnt_block; i++)
  157.     {
  158.         L[i] = cur;
  159.         R[i] = cur + (int)block[i].size() - 1;
  160.         cur = R[i] + 1;
  161.     }
  162. }
  163.  
  164. ll get_sum(int l, int r, int id)
  165. {
  166.     if (id < 1 || id > cnt_block) return 0;
  167.     ll ans = 0;
  168.     int len = (int)block[id].size();
  169.     // ensure lazy applied so physical order matches indices L..R
  170.     lazy(id);
  171.     for (int i = L[id], j = 0; i <= R[id] && j < len; i++, j++)
  172.         if (l <= i && i <= r)
  173.             ans += block[id][j];
  174.     return ans;
  175. }
  176.  
  177. int main()
  178. {
  179.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  180.     if (fopen("SUMS.INP", "r"))
  181.     {
  182.         freopen("SUMS.INP", "r", stdin);
  183.         freopen("SUMS.OUT", "w", stdout);
  184.     }
  185.  
  186.     // init
  187.     memset(L, 0, sizeof L);
  188.     memset(R, 0, sizeof R);
  189.     memset(sum, 0, sizeof sum);
  190.     memset(rev, 0, sizeof rev);
  191.     for (int i = 0; i <= maxn; i++) block[i].clear();
  192.     cnt_block = 0;
  193.  
  194.     cin >> n >> q;
  195.     for (int i = 1; i <= n; i++)
  196.     {
  197.         cin >> a[i];
  198.         int id = get_id(i);
  199.         if (i == 1 || get_id(i - 1) != get_id(i))
  200.             L[id] = i;
  201.         R[id] = i;
  202.         sum[id] += a[i];
  203.         block[id].push_back(a[i]);
  204.     }
  205.     cnt_block = get_id(n);
  206.  
  207.     while (q--)
  208.     {
  209.         int t, l, r;
  210.         cin >> t >> l >> r;
  211.         if (t == 1)
  212.             rever(l, r);
  213.         else
  214.         {
  215.             ll ans = 0;
  216.             int id_l = find_id(l);
  217.             int id_r = find_id(r);
  218.  
  219.             if (id_l == 0 || id_r == 0) {
  220.                 cout << 0 << '\n';
  221.                 if (cnt_block > max_cnt) rebuild();
  222.                 continue;
  223.             }
  224.  
  225.             if (id_l != id_r)
  226.             {
  227.                 lazy(id_l);
  228.                 lazy(id_r);
  229.                 ans += get_sum(l, R[id_l], id_l);
  230.                 for (int i = id_l + 1; i <= id_r - 1; i++)
  231.                     ans += sum[i];
  232.                 ans += get_sum(L[id_r], r, id_r);
  233.             }
  234.             else
  235.             {
  236.                 lazy(id_l);
  237.                 ans = get_sum(l, r, id_l);
  238.             }
  239.             cout << ans << '\n';
  240.         }
  241.         if (cnt_block > max_cnt)
  242.             rebuild();
  243.     }
  244.     return 0;
  245. }
  246.  
Success #stdin #stdout 0.01s 13168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NfNhdl
language:
C++14 (gcc 8.3)
created:
5 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!