fork download
copy 
  1. // #define ONLINE_JUDGE
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #if !defined(mhnd01s) || defined(ONLINE_JUDGE)
  5. #define print(...) ((void)0)
  6. #endif
  7. using ll = long long;
  8. void solve();
  9. signed main() {
  10. #ifdef mhnd01s
  11.     int x = mt19937(random_device()())()%100;printf("%d\n", x);
  12.     freopen("out", "wt", stdout);
  13. #else
  14.     cin.tie(0)->sync_with_stdio(0);
  15. #endif
  16.     cin.exceptions(cin.failbit);
  17.     int t = 1;
  18.     // cin >> t;
  19.     while(t--) {
  20.         solve();
  21.         if(t) cout << '\n';
  22.     }return 0;
  23. }
  24.  
  25. struct segtreebeats {
  26.     static const ll INF = 2e18, UNSET = LLONG_MIN;
  27.  
  28.     struct Node {
  29.         ll sum, mx1, mx2, mxc, mn1, mn2, mnc, d_gcd, lz_add, lz_set;
  30.     };
  31.  
  32.     int sz;
  33.     vector<Node> tree;
  34.  
  35.     inline ll absgcd(ll a, ll b) {
  36.         a = abs(a); b = abs(b);
  37.         while (b) { a %= b; swap(a, b); }
  38.         return a;
  39.     }
  40.  
  41.     Node leaf(ll v) { return {v, v, -INF, 1, v, INF, 1, 0, 0, UNSET}; }
  42.  
  43.     segtreebeats(int n, const vector<ll> &a) {
  44.         for (sz = 1; sz < n; sz <<= 1);
  45.         tree.assign(sz << 1, leaf(0));
  46.         build(a, n, 1, 0, sz - 1);
  47.     }
  48.  
  49.     inline void pull(int x) {
  50.         int lc = x << 1, rc = x << 1 | 1;
  51.         auto &U = tree[x], &L = tree[lc], &R = tree[rc];
  52.  
  53.         U.sum = L.sum + R.sum;
  54.         U.lz_add = 0; U.lz_set = UNSET;
  55.  
  56.         if (L.mx1 == R.mx1) U.mx1 = L.mx1, U.mx2 = max(L.mx2, R.mx2), U.mxc = L.mxc + R.mxc;
  57.         else if (L.mx1 > R.mx1) U.mx1 = L.mx1, U.mx2 = max(L.mx2, R.mx1), U.mxc = L.mxc;
  58.         else U.mx1 = R.mx1, U.mx2 = max(L.mx1, R.mx2), U.mxc = R.mxc;
  59.  
  60.         if (L.mn1 == R.mn1) U.mn1 = L.mn1, U.mn2 = min(L.mn2, R.mn2), U.mnc = L.mnc + R.mnc;
  61.         else if (L.mn1 < R.mn1) U.mn1 = L.mn1, U.mn2 = min(L.mn2, R.mn1), U.mnc = L.mnc;
  62.         else U.mn1 = R.mn1, U.mn2 = min(L.mn1, R.mn2), U.mnc = R.mnc;
  63.  
  64.         U.d_gcd = absgcd(L.d_gcd, R.d_gcd);
  65.         ll aL = L.mx2, aR = R.mx2;
  66.         if (aL != -INF && aL != L.mn1 && aR != -INF && aR != R.mn1)
  67.             U.d_gcd = absgcd(U.d_gcd, aL - aR);
  68.  
  69.         ll any = UNSET;
  70.         if (aL != -INF && aL != L.mn1) any = aL;
  71.         else if (aR != -INF && aR != R.mn1) any = aR;
  72.  
  73.         ll vals[4] = {L.mn1, L.mx1, R.mn1, R.mx1};
  74.         for (int i = 0; i < 4; ++i) {
  75.             if (vals[i] != U.mn1 && vals[i] != U.mx1) {
  76.                 if (any != UNSET) U.d_gcd = absgcd(U.d_gcd, vals[i] - any);
  77.                 else any = vals[i];
  78.             }
  79.         }
  80.     }
  81.  
  82.     inline void apply_set(int x, int lx, int rx, ll v) {
  83.         ll len = rx - lx + 1;
  84.         tree[x] = {len * v, v, -INF, len, v, INF, len, 0, 0, v};
  85.     }
  86.  
  87.     inline void apply_add(int x, int lx, int rx, ll v) {
  88.         if (!v) return;
  89.         auto &nd = tree[x];
  90.         if (nd.lz_set != UNSET) return apply_set(x, lx, rx, nd.lz_set + v);
  91.         if (nd.mx1 == nd.mn1) return apply_set(x, lx, rx, nd.mn1 + v);
  92.         ll len = rx - lx + 1;
  93.         nd.sum += len * v;
  94.         nd.mx1 += v; if (nd.mx2 != -INF) nd.mx2 += v;
  95.         nd.mn1 += v; if (nd.mn2 != INF) nd.mn2 += v;
  96.         nd.lz_add += v;
  97.     }
  98.  
  99.     inline void apply_chmin(int x, int lx, int rx, ll v) {
  100.         auto &nd = tree[x];
  101.         if (nd.mx1 <= v) return;
  102.         if (nd.mn1 >= v) return apply_set(x, lx, rx, v);
  103.         if (nd.mn2 == nd.mx1) nd.mn2 = v;
  104.         nd.sum -= (nd.mx1 - v) * nd.mxc;
  105.         nd.mx1 = v;
  106.     }
  107.  
  108.     inline void apply_chmax(int x, int lx, int rx, ll v) {
  109.         auto &nd = tree[x];
  110.         if (nd.mn1 >= v) return;
  111.         if (nd.mx1 <= v) return apply_set(x, lx, rx, v);
  112.         if (nd.mx2 == nd.mn1) nd.mx2 = v;
  113.         nd.sum += (v - nd.mn1) * nd.mnc;
  114.         nd.mn1 = v;
  115.     }
  116.  
  117.     inline void push(int x, int lx, int rx) {
  118.         if (lx == rx) return tree[x].lz_add = 0, tree[x].lz_set = UNSET, void();
  119.         int m = (lx + rx) >> 1, lc = x << 1, rc = x << 1 | 1;
  120.  
  121.         if (tree[x].lz_set != UNSET) {
  122.             apply_set(lc, lx, m, tree[x].lz_set);
  123.             apply_set(rc, m + 1, rx, tree[x].lz_set);
  124.             tree[x].lz_set = UNSET;
  125.         }
  126.         if (tree[x].lz_add) {
  127.             apply_add(lc, lx, m, tree[x].lz_add);
  128.             apply_add(rc, m + 1, rx, tree[x].lz_add);
  129.             tree[x].lz_add = 0;
  130.         }
  131.         if (tree[lc].mx1 > tree[x].mx1) apply_chmin(lc, lx, m, tree[x].mx1);
  132.         if (tree[rc].mx1 > tree[x].mx1) apply_chmin(rc, m + 1, rx, tree[x].mx1);
  133.         if (tree[lc].mn1 < tree[x].mn1) apply_chmax(lc, lx, m, tree[x].mn1);
  134.         if (tree[rc].mn1 < tree[x].mn1) apply_chmax(rc, m + 1, rx, tree[x].mn1);
  135.     }
  136.  
  137.     void build(const vector<ll> &a, int n, int x, int lx, int rx) {
  138.         if (lx == rx) return void(tree[x] = (lx < n) ? leaf(a[lx]) : leaf(0));
  139.         int m = (lx + rx) >> 1;
  140.         build(a, n, x << 1, lx, m);
  141.         build(a, n, x << 1 | 1, m + 1, rx);
  142.         pull(x);
  143.     }
  144.  
  145.     void chmin(int l, int r, ll v, int x, int lx, int rx) {
  146.         if (lx > r || rx < l || tree[x].mx1 <= v) return;
  147.         if (lx >= l && rx <= r && tree[x].mx2 < v) return apply_chmin(x, lx, rx, v);
  148.         push(x, lx, rx);
  149.         int m = (lx + rx) >> 1;
  150.         chmin(l, r, v, x << 1, lx, m);
  151.         chmin(l, r, v, x << 1 | 1, m + 1, rx);
  152.         pull(x);
  153.     }
  154.  
  155.     void chmax(int l, int r, ll v, int x, int lx, int rx) {
  156.         if (lx > r || rx < l || tree[x].mn1 >= v) return;
  157.         if (lx >= l && rx <= r && tree[x].mn2 > v) return apply_chmax(x, lx, rx, v);
  158.         push(x, lx, rx);
  159.         int m = (lx + rx) >> 1;
  160.         chmax(l, r, v, x << 1, lx, m);
  161.         chmax(l, r, v, x << 1 | 1, m + 1, rx);
  162.         pull(x);
  163.     }
  164.  
  165.     void assign(int l, int r, ll v, int x, int lx, int rx) {
  166.         if (lx > r || rx < l) return;
  167.         if (lx >= l && rx <= r) return apply_set(x, lx, rx, v);
  168.         push(x, lx, rx);
  169.         int m = (lx + rx) >> 1;
  170.         assign(l, r, v, x << 1, lx, m);
  171.         assign(l, r, v, x << 1 | 1, m + 1, rx);
  172.         pull(x);
  173.     }
  174.  
  175.     void add(int l, int r, ll v, int x, int lx, int rx) {
  176.         if (lx > r || rx < l) return;
  177.         if (lx >= l && rx <= r) return apply_add(x, lx, rx, v);
  178.         push(x, lx, rx);
  179.         int m = (lx + rx) >> 1;
  180.         add(l, r, v, x << 1, lx, m);
  181.         add(l, r, v, x << 1 | 1, m + 1, rx);
  182.         pull(x);
  183.     }
  184.  
  185.     ll sum(int l, int r, int x, int lx, int rx) {
  186.         if (lx > r || rx < l) return 0;
  187.         if (lx >= l && rx <= r) return tree[x].sum;
  188.         push(x, lx, rx);
  189.         int m = (lx + rx) >> 1;
  190.         return sum(l, r, x << 1, lx, m) + sum(l, r, x << 1 | 1, m + 1, rx);
  191.     }
  192.  
  193.     ll qmin(int l, int r, int x, int lx, int rx) {
  194.         if (lx > r || rx < l) return INF;
  195.         if (lx >= l && rx <= r) return tree[x].mn1;
  196.         push(x, lx, rx);
  197.         int m = (lx + rx) >> 1;
  198.         return min(qmin(l, r, x << 1, lx, m), qmin(l, r, x << 1 | 1, m + 1, rx));
  199.     }
  200.  
  201.     ll qmax(int l, int r, int x, int lx, int rx) {
  202.         if (lx > r || rx < l) return -INF;
  203.         if (lx >= l && rx <= r) return tree[x].mx1;
  204.         push(x, lx, rx);
  205.         int m = (lx + rx) >> 1;
  206.         return max(qmax(l, r, x << 1, lx, m), qmax(l, r, x << 1 | 1, m + 1, rx));
  207.     }
  208.  
  209.     ll qgcd(int l, int r, int x, int lx, int rx) {
  210.         if (lx > r || rx < l) return 0;
  211.         if (lx >= l && rx <= r) {
  212.             ll ans = absgcd(tree[x].d_gcd, tree[x].mx1);
  213.             if (tree[x].mx2 != -INF) ans = absgcd(ans, tree[x].mx2 - tree[x].mx1);
  214.             if (tree[x].mn2 != INF) ans = absgcd(ans, tree[x].mn2 - tree[x].mn1);
  215.             return ans;
  216.         }
  217.         push(x, lx, rx);
  218.         int m = (lx + rx) >> 1;
  219.         return absgcd(qgcd(l, r, x << 1, lx, m), qgcd(l, r, x << 1 | 1, m + 1, rx));
  220.     }
  221.  
  222.     void chmin(int l, int r, ll v) { chmin(l, r, v, 1, 0, sz - 1); }
  223.     void chmax(int l, int r, ll v) { chmax(l, r, v, 1, 0, sz - 1); }
  224.     void assign(int l, int r, ll v) { assign(l, r, v, 1, 0, sz - 1); }
  225.     void add(int l, int r, ll v) { add(l, r, v, 1, 0, sz - 1); }
  226.     ll qsum(int l, int r) { return sum(l, r, 1, 0, sz - 1); }
  227.     ll qmin(int l, int r) { return qmin(l, r, 1, 0, sz - 1); }
  228.     ll qmax(int l, int r) { return qmax(l, r, 1, 0, sz - 1); }
  229.     ll qgcd(int l, int r) { return qgcd(l, r, 1, 0, sz - 1); }
  230. };
  231.  
  232. void solve() {
  233.     int n, q; cin >> n;
  234.     vector<ll> v(n);
  235.     for (auto &i : v) cin >> i;
  236.     segtreebeats sgt(n, v);
  237.     cin >> q;
  238.     while (q--) {
  239.         int type; cin >> type;
  240.         if (type == 1) {
  241.             int l, r, x; cin >> l >> r >> x;
  242.             sgt.chmin(--l, --r, x);
  243.         } else if (type == 2) {
  244.             int l, r, x; cin >> l >> r >> x;
  245.             sgt.chmax(--l, --r, x);
  246.         } else if (type == 3) {
  247.             int l, r, x; cin >> l >> r >> x;
  248.             sgt.assign(--l, --r, x);
  249.         } else if (type == 4) {
  250.             int l, r, x; cin >> l >> r >> x;
  251.             sgt.add(--l, --r, x);
  252.         } else if (type == 5) {
  253.             int l, r; cin >> l >> r;
  254.             cout << sgt.qsum(--l, --r);
  255.         } else if (type == 6) {
  256.             int l, r; cin >> l >> r;
  257.             cout << sgt.qmin(--l, --r);
  258.         } else if (type == 7) {
  259.             int l, r; cin >> l >> r;
  260.             cout << sgt.qmax(--l, --r);
  261.         } else if (type == 8) {
  262.             int l, r; cin >> l >> r;
  263.             cout << sgt.qgcd(--l, --r);
  264.         }
  265.         cout << '\n';
  266.     }
  267. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
7
1 2 3 4 5 6 7
20
4 2 7 10
5 1 6
6 1 6
7 1 6
8 1 6
2 1 6 14
5 2 7
6 2 7
7 2 7
8 2 7
1 2 7 12
5 1 6
6 1 6
7 1 6
8 1 6
3 2 6 15
5 1 7
6 1 7
7 1 7
8 1 7
stdout
copy 
71
1
16
1

90
14
17
1

74
12
14
2

101
12
15
1
https://ideone.com/9cpWRb
language:
C++14 (gcc 8.3)
created:
4 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!