fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. #define int long long
  5. #define F(i, l, r) for(int i = l; i <= r; ++i)
  6. #define E(i, l, r) for(int i = l; i >= r; --i)
  7. #define eb emplace_back
  8. const ll mod = 1e9 + 7;
  9. const int ars = 1e5 + 5;
  10. const int ii = 1e9;
  11. const ll il = 1e18;
  12.  
  13. int n, m, a[ars];
  14. struct node {
  15.     int sum, lza, lzb;
  16.     node() {
  17.         sum = lza = lzb = 0;
  18.     }
  19.     node(int s, int a, int b) : sum(s), lza(a), lzb(b) {}
  20. } st[ars * 4];
  21.  
  22.  
  23. // ta biến đổi lượng cộng vào đoạn f(i)
  24. // f(i) = A * si + C = A * si + (B - A * L);
  25. // si là tổng sigma i: l->r
  26. void apply(int id, int l, int r, int A, int C) {
  27.     int len = r - l + 1;
  28.     int si = (len * l) + (len * (len - 1) / 2); si %= mod;
  29.     int fi = (A * si + C * len) % mod;
  30.  
  31.     st[id].sum = (st[id].sum + fi) % mod;
  32.     st[id].lza = (st[id].lza + A) % mod;
  33.     st[id].lzb = (st[id].lzb + C) % mod;
  34. }
  35.  
  36. void push(int id, int l, int r) {
  37.     if(!st[id].lza and !st[id].lzb) return;
  38.     int mid = (l + r) / 2;
  39.  
  40.     apply(id * 2,     l,     mid, st[id].lza, st[id].lzb);
  41.     apply(id * 2 + 1, mid + 1, r, st[id].lza, st[id].lzb);
  42.     st[id].lza = st[id].lzb = 0;
  43. }
  44.  
  45. void update(int id, int l, int r, int L, int R, int A, int B) {
  46.     if(l > R or r < L) return;
  47.     if(l >= L and r <= R) {
  48.         int C = B - A * L;
  49.         C = (C % mod) + mod; C %= mod;
  50.         apply(id, l, r, A % mod, C);
  51.         return;
  52.     }
  53.     push(id, l, r);
  54.     int mid = (l + r) / 2;
  55.     update(id * 2,     l,     mid, L, R, A, B);
  56.     update(id * 2 + 1, mid + 1, r, L, R, A, B);
  57.     st[id].sum = (st[id * 2].sum + st[id * 2 + 1].sum) % mod;
  58. }
  59.  
  60. int get(int id, int l, int r, int L, int R) {
  61.     if(l > R or r < L) return 0;
  62.     if(l >= L and r <= R) return st[id].sum;
  63.     push(id, l, r);
  64.     int mid = (l + r) / 2;
  65.     return (get(id * 2, l, mid, L, R) + get(id * 2 + 1, mid + 1, r, L, R)) % mod;
  66. }
  67.  
  68. signed main() {
  69.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  70.     cin >> n >> m;
  71.  
  72.     F(i, 1, m) {
  73.         int t; cin >> t;
  74.         if(t == 1) {
  75.             int L, R, A, B;
  76.             cin >> L >> R >> A >> B;
  77.             update(1, 1, n, L, R, A, B);
  78.         }else {
  79.             int L, R;
  80.             cin >> L >> R;
  81.             cout << get(1, 1, n, L, R) << "\n";
  82.         }
  83.     }
  84.  
  85.  
  86.     return 0;
  87. }
Success #stdin #stdout 0.01s 12944KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9yPgwQ
language:
C++14 (gcc 8.3)
created:
6 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!