fork download 
  1. #include <bits/stdc++.h>
  2. #include <unordered_map>
  3. #define _CRT_SECURE_NO_WARNINGS
  4. #pragma GCC optimize ("O3")
  5. #define int long long
  6.  
  7. using namespace std;
  8.  
  9. const int oo = 1e9 + 7;
  10. const int MOD = 1e9 + 7;
  11. const int MAXN = 1e6;
  12. const int MAX = 2e5;
  13.  
  14. int dx[4] = { 0, 0, 1, -1 };
  15. int dy[4] = { 1, -1, 0 ,0 };
  16. struct Node {
  17.     int sum;
  18.     int min_val;
  19.     int min_pos;
  20. } tree_node;
  21.  
  22. int n, q;
  23.  
  24. vector<int> a;
  25.  
  26. vector<Node> tree;
  27.  
  28. int offset = 0;
  29.  
  30. void build(int idx, int l, int r) {
  31.     if (l == r) {
  32.         tree[idx].sum = a[l];
  33.         tree[idx].min_val = a[l];
  34.         tree[idx].min_pos = l;
  35.         return;
  36.     }
  37.     int mid = (l + r) >> 1;
  38.     build(2 * idx, l, mid);
  39.     build(2 * idx + 1, mid + 1, r);
  40.     tree[idx].sum = tree[2 * idx].sum + tree[2 * idx + 1].sum;
  41.  
  42.     if (tree[2 * idx].min_val <= tree[2 * idx + 1].min_val) {
  43.         tree[idx].min_val = tree[2 * idx].min_val;
  44.         tree[idx].min_pos = tree[2 * idx].min_pos;
  45.     }
  46.     else {
  47.         tree[idx].min_val = tree[2 * idx + 1].min_val;
  48.         tree[idx].min_pos = tree[2 * idx + 1].min_pos;
  49.     }
  50. }
  51.  
  52. int get_sum(int idx, int l, int r, int u, int v) {
  53.     if (u > r || v < l) return 0;
  54.     if (l >= u && r <= v) return tree[idx].sum;
  55.     int mid = (l + r) >> 1;
  56.     return get_sum(2 * idx, l, mid, u, v) + get_sum(2 * idx + 1, mid + 1, r, u, v);
  57. }
  58.  
  59. pair<int, int> get_min(int idx, int l, int r, int u, int v) {
  60.     if (u > r || v < l) return { oo, -1 };
  61.     if (l >= u && r <= v) return { tree[idx].min_val, tree[idx].min_pos };
  62.     int mid = (l + r) >> 1;
  63.     pair<int, int> left_min = get_min(2 * idx, l, mid, u, v);
  64.     pair<int, int> right_min = get_min(2 * idx + 1, mid + 1, r, u, v);
  65.     if (left_min.first < right_min.first) return left_min;
  66.     if (left_min.first > right_min.first) return right_min;
  67.     if (left_min.second < right_min.second) return left_min;
  68.     return right_min;
  69. }
  70.  
  71. void point_update(int idx, int l, int r, int pos, int value) {
  72.     if (l == r) {
  73.         tree[idx].sum = value;
  74.         tree[idx].min_val = value;
  75.         tree[idx].min_pos = l;
  76.         return;
  77.     }
  78.     int mid = (l + r) >> 1;
  79.     if (pos <= mid) {
  80.         point_update(2 * idx, l, mid, pos, value);
  81.     }
  82.     else {
  83.         point_update(2 * idx + 1, mid + 1, r, pos, value);
  84.     }
  85.     tree[idx].sum = tree[2 * idx].sum + tree[2 * idx + 1].sum;
  86.     if (tree[2 * idx].min_val <= tree[2 * idx + 1].min_val) {
  87.         tree[idx].min_val = tree[2 * idx].min_val;
  88.         tree[idx].min_pos = tree[2 * idx].min_pos;
  89.     }
  90.     else {
  91.         tree[idx].min_val = tree[2 * idx + 1].min_val;
  92.         tree[idx].min_pos = tree[2 * idx + 1].min_pos;
  93.     }
  94. }
  95.  
  96. signed main() {
  97.     ios::sync_with_stdio(false);
  98.     cin.tie(0);
  99.  
  100.     cin >> n >> q;
  101.     a.resize(n + 1);
  102.     for (int i = 1; i <= n; i++) {
  103.         cin >> a[i];
  104.     }
  105.     tree.resize(4 * n + 5);
  106.     build(1, 1, n);
  107.  
  108.     while (q--) {
  109.         int type; cin >> type;
  110.         if (type == 1) {
  111.             int d; cin >> d;
  112.             offset = (offset + d) % n;
  113.         }
  114.         else if (type == 2) {
  115.             int s, t, p;
  116.             cin >> s >> t >> p;
  117.             int real_s = (s - offset - 1 + n * n) % n + 1;
  118.             int real_t = (t - offset - 1 + n * n) % n + 1;
  119.  
  120.             if (real_s <= real_t) {
  121.                 pair<int, int> min_info = get_min(1, 1, n, real_s, real_t);
  122.                 point_update(1, 1, n, min_info.second, p);
  123.             }
  124.             else {
  125.                 pair<int, int> min_info1 = get_min(1, 1, n, real_s, n);
  126.                 pair<int, int> min_info2 = get_min(1, 1, n, 1, real_t);
  127.                 pair<int, int> min_info;
  128.                 if (min_info1.first < min_info2.first) {
  129.                     min_info = min_info1;
  130.                 }
  131.                 else if (min_info1.first > min_info2.first) {
  132.                     min_info = min_info2;
  133.                 }
  134.                 else {
  135.                     if (s > t) {
  136.                         min_info = min_info2;
  137.                     }
  138.                     else {
  139.                         min_info = min_info1;
  140.                     }
  141.                 }
  142.                 point_update(1, 1, n, min_info.second, p);
  143.             }
  144.         }
  145.         else if (type == 3) {
  146.             int s, t;
  147.             cin >> s >> t;
  148.  
  149.             int real_s = (s - offset - 1 + n * n) % n + 1;
  150.             int real_t = (t - offset - 1 + n * n) % n + 1;
  151.  
  152.             int ans = 0;
  153.             if (real_s <= real_t) {
  154.                 ans = get_sum(1, 1, n, real_s, real_t);
  155.             }
  156.             else {
  157.                 ans = get_sum(1, 1, n, real_s, n) + get_sum(1, 1, n, 1, real_t);
  158.             }
  159.             cout << ans << endl;
  160.         }
  161.     }
  162.     return 0;
  163. }
  164.  
Runtime error #stdin #stdout 2.17s 2095644KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/1XU1IC
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!