fork download 
  1. // Done by AnhHao215
  2. // On 19/07/2025
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. #define Ngbanh() signed main()
  8. #define Task "SEGMENTTREE"
  9. #define in() Task".inp"
  10. #define out() Task".out"
  11.  
  12. #define FOR(i,a,b) for(int i=a;i<b;i++)
  13. #define REP(i,a,b) for(int i=a;i<=b;i++)
  14. #define FORD(i,a,b) for(int i=a-1;i>=b;i--)
  15. #define REPD(i,a,b) for(int i=a;i>=b;i--)
  16.  
  17. #define all(x) x.begin(), x.end()
  18. #define rall(x) x.rbegin(), x.rend()
  19. #define pb emplace_back
  20. #define mp make_pair
  21. #define reset(f, x) memset(f, x, sizeof(f))
  22. #define sz(x) int(x.size())
  23. #define bit(x, i) ((x >> i) & 1)
  24.  
  25. #define F first
  26. #define S second
  27. #define endl "\n"
  28. #define sp ' '
  29. #define elif else if
  30. #define mid int((l + r) / 2)
  31. #define toL int(node << 1)
  32. #define toR int(node << 1 | 1)
  33.  
  34. #define Optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  35. #define Fopen() if(fopen(in(),"r")){freopen(in(),"r",stdin);freopen(out(),"w",stdout);}
  36.  
  37. #pragma GCC optimize("O3")
  38. #pragma GCC target("avx,avx2,fma,sse4.2")
  39. #pragma GCC optimize("unroll-loops")
  40.  
  41. typedef long long ll;
  42. typedef long double ld;
  43. typedef vector<int> vi;
  44. typedef pair<int, int> pii;
  45.  
  46. const int maxn = 1e5 + 5;
  47. const int base = 31;
  48. const int MOD = 1e9 + 7;
  49. const ll INF = 1e18;
  50.  
  51. int n, q;
  52. int a[maxn];
  53. ll tree[4 * maxn], val_add[4 * maxn], val_mul[4 * maxn], val_set[4 * maxn];
  54.  
  55. void Init(int node, int l, int r) {
  56.     val_add[node] = 0;
  57.     val_mul[node] = 1;
  58.     val_set[node] = -1;
  59.     if(l == r) {
  60.         tree[node] = a[l] % MOD;
  61.         return;
  62.     }
  63.     Init(toL, l, mid);
  64.     Init(toR, mid + 1, r);
  65.     tree[node] = (tree[toL] + tree[toR]) % MOD;
  66. }
  67.  
  68. void PushSet(int node, int l, int r) {
  69.     if(val_set[node] == -1) return;
  70.     tree[node] = val_set[node] * (r - l + 1) % MOD;
  71.     if(l != r) {
  72.         val_set[toL] = val_set[toR] = val_set[node];
  73.         val_add[toL] = val_add[toR] = 0;
  74.         val_mul[toL] = val_mul[toR] = 1;
  75.     }
  76.     val_set[node] = -1;
  77. }
  78.  
  79. void PushMul(int node, int l, int r) {
  80.     if(val_mul[node] == 1) return;
  81.     tree[node] = tree[node] * val_mul[node] % MOD;
  82.     if(l != r) {
  83.         val_mul[toL] = val_mul[toL] * val_mul[node] % MOD;
  84.         val_mul[toR] = val_mul[toR] * val_mul[node] % MOD;
  85.         val_add[toL] = val_add[toL] * val_mul[node] % MOD;
  86.         val_add[toR] = val_add[toR] * val_mul[node] % MOD;
  87.     }
  88.     val_mul[node] = 1;
  89. }
  90.  
  91. void PushAdd(int node, int l, int r) {
  92.     if(val_add[node] == 0)  return;
  93.     tree[node] = (tree[node] + val_add[node] * (r - l + 1)) % MOD;
  94.     if (l != r) {
  95.         val_add[toL] = (val_add[toL] + val_add[node]) % MOD;
  96.         val_add[toR] = (val_add[toR] + val_add[node]) % MOD;
  97.     }
  98.     val_add[node] = 0;
  99. }
  100.  
  101. void Push(int node, int l, int r) {
  102.     PushSet(node, l, r);
  103.     PushMul(node, l, r);
  104.     PushAdd(node, l, r);
  105. }
  106.  
  107. void UpdateAdd(int node, int l, int r, int u, int v, ll w) {
  108.     Push(node, l, r);
  109.     if (v < l || r < u) return;
  110.     if (u <= l && r <= v) {
  111.         val_add[node] = (val_add[node] + w) % MOD;
  112.         Push(node, l, r);
  113.         return;
  114.     }
  115.     UpdateAdd(toL, l, mid, u, v, w);
  116.     UpdateAdd(toR, mid + 1, r, u, v, w);
  117.     tree[node] = (tree[toL] + tree[toR]) % MOD;
  118. }
  119.  
  120. void UpdateMul(int node, int l, int r, int u, int v, ll w) {
  121.     Push(node, l, r);
  122.     if (v < l || r < u) return;
  123.     if (u <= l && r <= v) {
  124.         val_mul[node] = val_mul[node] * w % MOD;
  125.         Push(node, l, r);
  126.         return;
  127.     }
  128.     UpdateMul(toL, l, mid, u, v, w);
  129.     UpdateMul(toR, mid + 1, r, u, v, w);
  130.     tree[node] = (tree[toL] + tree[toR]) % MOD;
  131. }
  132.  
  133. void UpdateAlt(int node, int l, int r, int u, int v, ll w) {
  134.     Push(node, l, r);
  135.     if (v < l || r < u) return;
  136.     if (u <= l && r <= v) {
  137.         val_set[node] = w;
  138.         val_add[node] = 0;
  139.         val_mul[node] = 1;
  140.         Push(node, l, r);
  141.         return;
  142.     }
  143.     UpdateAlt(toL, l, mid, u, v, w);
  144.     UpdateAlt(toR, mid + 1, r, u, v, w);
  145.     tree[node] = (tree[toL] + tree[toR]) % MOD;
  146. }
  147.  
  148. ll GetSum(int node, int l, int r, int u, int v) {
  149.     Push(node, l, r);
  150.     if (v < l || r < u) return 0;
  151.     if (u <= l && r <= v) return tree[node];
  152.     return (GetSum(toL, l, mid, u, v) + GetSum(toR, mid + 1, r, u, v)) % MOD;
  153. }
  154.  
  155. Ngbanh() {
  156.     Optimize();
  157.     Fopen();
  158.  
  159.     cin >> n >> q;
  160.     REP(i, 1, n) cin >> a[i];
  161.     Init(1, 1, n);
  162.  
  163.     FOR(i, 0, q) {
  164.         int type, u, v;
  165.         ll w;
  166.         cin >> type;
  167.         if (type == 1) {
  168.             cin >> u >> v >> w;
  169.             UpdateAdd(1, 1, n, u, v, w);
  170.         }
  171.         elif (type == 2) {
  172.             cin >> u >> v >> w;
  173.             UpdateMul(1, 1, n, u, v, w);
  174.         }
  175.         elif (type == 3) {
  176.             cin >> u >> v >> w;
  177.             UpdateAlt(1, 1, n, u, v, w);
  178.         }
  179.         elif (type == 4) {
  180.             cin >> u >> v;
  181.             cout << GetSum(1, 1, n, u, v) << endl;
  182.         }
  183.     }
  184.  
  185.     return 0;
  186. }
  187.  
Success #stdin #stdout 0.01s 9736KB
comments (?)
stdin 
7 7
3 5 2 5 6 2 3
1 4 6 2
2 3 8 9
3 4 6 10
4 6 7
2 3 6 7
1 2 7 1
4 3 5
stdout 
37
269
https://ideone.com/zW0T2W
language:
C++ (gcc 8.3)
created:
20 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!