fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. struct Node {
  7.     ll sum_salary;        // Sum of salaries in the segment
  8.     ll sum_happiness;     // Sum of happiness in the segment
  9.     ll uniform_salary;    // Uniform salary value if all salaries are the same
  10.     bool is_uniform;      // Flag indicating if the segment is uniform
  11.     ll lazy_set;          // Pending set operation (None if -1)
  12.     ll lazy_add;          // Pending add operation
  13.  
  14.     Node() : sum_salary(0), sum_happiness(0), uniform_salary(0), is_uniform(true), lazy_set(-1), lazy_add(0) {}
  15. };
  16.  
  17. const int MAXN = 200005;
  18. int N, Q;
  19. ll a[MAXN];
  20. Node tree[4 * MAXN];
  21.  
  22. void build(int node, int l, int r) {
  23.     if (l == r) {
  24.         tree[node].sum_salary = a[l];
  25.         tree[node].sum_happiness = 0;
  26.         tree[node].uniform_salary = a[l];
  27.         tree[node].is_uniform = true;
  28.         tree[node].lazy_set = -1;
  29.         tree[node].lazy_add = 0;
  30.     } else {
  31.         int mid = (l + r) / 2;
  32.         build(2 * node, l, mid);
  33.         build(2 * node + 1, mid + 1, r);
  34.         tree[node].sum_salary = tree[2 * node].sum_salary + tree[2 * node + 1].sum_salary;
  35.         tree[node].sum_happiness = tree[2 * node].sum_happiness + tree[2 * node + 1].sum_happiness;
  36.         tree[node].is_uniform = tree[2 * node].is_uniform && tree[2 * node + 1].is_uniform && 
  37.                                 tree[2 * node].uniform_salary == tree[2 * node + 1].uniform_salary;
  38.         if (tree[node].is_uniform) {
  39.             tree[node].uniform_salary = tree[2 * node].uniform_salary;
  40.         }
  41.         tree[node].lazy_set = -1;
  42.         tree[node].lazy_add = 0;
  43.     }
  44. }
  45.  
  46. void push(int node, int l, int r) {
  47.     if (tree[node].lazy_set != -1) {
  48.         // Apply the set operation
  49.         ll c = tree[node].lazy_set;
  50.         ll cnt = r - l + 1;
  51.         if (tree[node].is_uniform) {
  52.             ll s_prev = tree[node].uniform_salary;
  53.             ll happiness_change = 0;
  54.             if (c > s_prev) happiness_change = cnt;
  55.             else if (c < s_prev) happiness_change = -cnt;
  56.             tree[node].sum_happiness += happiness_change;
  57.         } else {
  58.             // Can't compute directly; need to propagate
  59.             push(2 * node, l, (l + r) / 2);
  60.             push(2 * node + 1, (l + r) / 2 + 1, r);
  61.         }
  62.         tree[node].sum_salary = c * cnt;
  63.         tree[node].uniform_salary = c;
  64.         tree[node].is_uniform = true;
  65.         // Clear lazy tags
  66.         tree[node].lazy_set = -1;
  67.         tree[node].lazy_add = 0;
  68.         if (l != r) {
  69.             tree[2 * node].lazy_set = c;
  70.             tree[2 * node].lazy_add = 0;
  71.             tree[2 * node + 1].lazy_set = c;
  72.             tree[2 * node + 1].lazy_add = 0;
  73.         }
  74.     }
  75.     if (tree[node].lazy_add != 0) {
  76.         ll c = tree[node].lazy_add;
  77.         ll cnt = r - l + 1;
  78.         if (tree[node].is_uniform) {
  79.             ll s_prev = tree[node].uniform_salary;
  80.             ll s_new = s_prev + c;
  81.             ll happiness_change = 0;
  82.             if (c > 0) happiness_change = cnt;
  83.             else if (c < 0) happiness_change = -cnt;
  84.             tree[node].sum_happiness += happiness_change;
  85.             tree[node].uniform_salary = s_new;
  86.         } else {
  87.             // Can't compute directly; need to propagate
  88.             push(2 * node, l, (l + r) / 2);
  89.             push(2 * node + 1, (l + r) / 2 + 1, r);
  90.         }
  91.         tree[node].sum_salary += c * cnt;
  92.         if (l != r) {
  93.             if (tree[2 * node].lazy_set != -1) {
  94.                 tree[2 * node].lazy_set += c;
  95.             } else {
  96.                 tree[2 * node].lazy_add += c;
  97.             }
  98.             if (tree[2 * node + 1].lazy_set != -1) {
  99.                 tree[2 * node + 1].lazy_set += c;
  100.             } else {
  101.                 tree[2 * node + 1].lazy_add += c;
  102.             }
  103.         }
  104.         tree[node].lazy_add = 0;
  105.     }
  106. }
  107.  
  108. void range_set(int node, int l, int r, int ql, int qr, ll c) {
  109.     push(node, l, r);
  110.     if (r < ql || l > qr) return;
  111.     if (ql <= l && r <= qr) {
  112.         tree[node].lazy_set = c;
  113.         push(node, l, r);
  114.     } else {
  115.         int mid = (l + r) / 2;
  116.         range_set(2 * node, l, mid, ql, qr, c);
  117.         range_set(2 * node + 1, mid + 1, r, ql, qr, c);
  118.         tree[node].sum_salary = tree[2 * node].sum_salary + tree[2 * node + 1].sum_salary;
  119.         tree[node].sum_happiness = tree[2 * node].sum_happiness + tree[2 * node + 1].sum_happiness;
  120.         tree[node].is_uniform = tree[2 * node].is_uniform && tree[2 * node + 1].is_uniform && 
  121.                                 tree[2 * node].uniform_salary == tree[2 * node + 1].uniform_salary;
  122.         if (tree[node].is_uniform) {
  123.             tree[node].uniform_salary = tree[2 * node].uniform_salary;
  124.         } else {
  125.             tree[node].uniform_salary = 0;
  126.         }
  127.     }
  128. }
  129.  
  130. void range_add(int node, int l, int r, int ql, int qr, ll c) {
  131.     push(node, l, r);
  132.     if (r < ql || l > qr) return;
  133.     if (ql <= l && r <= qr) {
  134.         tree[node].lazy_add += c;
  135.         push(node, l, r);
  136.     } else {
  137.         int mid = (l + r) / 2;
  138.         range_add(2 * node, l, mid, ql, qr, c);
  139.         range_add(2 * node + 1, mid + 1, r, ql, qr, c);
  140.         tree[node].sum_salary = tree[2 * node].sum_salary + tree[2 * node + 1].sum_salary;
  141.         tree[node].sum_happiness = tree[2 * node].sum_happiness + tree[2 * node + 1].sum_happiness;
  142.         tree[node].is_uniform = tree[2 * node].is_uniform && tree[2 * node + 1].is_uniform && 
  143.                                 tree[2 * node].uniform_salary == tree[2 * node + 1].uniform_salary;
  144.         if (tree[node].is_uniform) {
  145.             tree[node].uniform_salary = tree[2 * node].uniform_salary;
  146.         } else {
  147.             tree[node].uniform_salary = 0;
  148.         }
  149.     }
  150. }
  151.  
  152. pair<ll, ll> query_salary(int node, int l, int r, int ql, int qr) {
  153.     push(node, l, r);
  154.     if (r < ql || l > qr) return {0, 0};
  155.     if (ql <= l && r <= qr) {
  156.         return {tree[node].sum_salary, r - l + 1};
  157.     } else {
  158.         int mid = (l + r) / 2;
  159.         auto left = query_salary(2 * node, l, mid, ql, qr);
  160.         auto right = query_salary(2 * node + 1, mid + 1, r, ql, qr);
  161.         return {left.first + right.first, left.second + right.second};
  162.     }
  163. }
  164.  
  165. pair<ll, ll> query_happiness(int node, int l, int r, int ql, int qr) {
  166.     push(node, l, r);
  167.     if (r < ql || l > qr) return {0, 0};
  168.     if (ql <= l && r <= qr) {
  169.         return {tree[node].sum_happiness, r - l + 1};
  170.     } else {
  171.         int mid = (l + r) / 2;
  172.         auto left = query_happiness(2 * node, l, mid, ql, qr);
  173.         auto right = query_happiness(2 * node + 1, mid + 1, r, ql, qr);
  174.         return {left.first + right.first, left.second + right.second};
  175.     }
  176. }
  177.  
  178. ll gcd(ll a, ll b) {
  179.     return b ? gcd(b, a % b) : a;
  180. }
  181.  
  182. void print_fraction(ll num, ll denom) {
  183.     ll g = gcd(abs(num), denom);
  184.     num /= g;
  185.     denom /= g;
  186.     cout << num << "/" << denom << "\n";
  187. }
  188.  
  189. int main() {
  190.     ios::sync_with_stdio(false);
  191.     cin.tie(nullptr);
  192.     cin >> N >> Q;
  193.     for (int i = 1; i <= N; ++i) {
  194.         cin >> a[i];
  195.     }
  196.     build(1, 1, N);
  197.     while (Q--) {
  198.         int type;
  199.         cin >> type;
  200.         if (type == 0) {
  201.             int l, r;
  202.             ll c;
  203.             cin >> l >> r >> c;
  204.             range_set(1, 1, N, l, r, c);
  205.         } else if (type == 1) {
  206.             int l, r;
  207.             ll c;
  208.             cin >> l >> r >> c;
  209.             range_add(1, 1, N, l, r, c);
  210.         } else if (type == 2) {
  211.             int l, r;
  212.             cin >> l >> r;
  213.             auto res = query_salary(1, 1, N, l, r);
  214.             ll sum = res.first;
  215.             ll cnt = res.second;
  216.             print_fraction(sum, cnt);
  217.         } else if (type == 3) {
  218.             int l, r;
  219.             cin >> l >> r;
  220.             auto res = query_happiness(1, 1, N, l, r);
  221.             ll sum = res.first;
  222.             ll cnt = res.second;
  223.             print_fraction(sum, cnt);
  224.         }
  225.     }
  226.     return 0;
  227. }
  228.  
Success #stdin #stdout 0.02s 41996KB
comments (?)
stdin
copy 
5 8
1 3 5 4 2
1 2 5 -1
2 1 4
0 2 3 3
3 1 5
1 4 5 3
0 3 4 5
3 1 5
2 2 5
stdout
copy 
5/2
-2/5
-2/5
17/4
https://ideone.com/8xERO4
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!