fork download
copy 
  1. /* Author : Nguyen Thanh Tung */
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define endl 		         '\n'
  6. #define int 		         long long
  7.  
  8. using namespace 	         std;
  9.  
  10. typedef pair<int, int>       ii;
  11.  
  12. const int       N            = 1e6 + 7;
  13. const long long oo           = 1e18 + 7;
  14. const long long MOD          = 1e9 + 7;
  15.  
  16. int n, m;
  17. int a[N];
  18. int lazy1[N << 2], lazy2[N << 2], st1[N << 2], st2[N << 2];
  19.  
  20. int calc(int x) {
  21.     return x * (x + 1) / 2;
  22. }
  23.  
  24. void fix1(int id, int l, int r) {
  25.     if(lazy1[id]) {
  26.         int m = (l + r) >> 1;
  27.         (st1[id << 1] += lazy1[id] * (m - l + 1)) %= MOD;
  28.         (st1[id << 1 | 1] += lazy1[id] * (r - m)) %= MOD;        
  29.         (lazy1[id << 1] += lazy1[id]) %= MOD;
  30.         (lazy1[id << 1 | 1] += lazy1[id]) %= MOD;
  31.         lazy1[id] = 0;
  32.     }
  33. }
  34.  
  35. void update1(int id, int l, int r, int u, int v, int val) {
  36.     if(v < l || u > r) {
  37.         return;
  38.     }
  39.     if(u <= l && v >= r) {
  40.         (st1[id] += val * (r - l + 1)) %= MOD;
  41.         (lazy1[id] += val) %= MOD; 
  42.         return;
  43.     }
  44.     fix1(id, l, r);
  45.     int m = (l + r) >> 1;
  46.     update1(id << 1, l, m, u, v, val);
  47.     update1(id << 1 | 1, m + 1, r, u, v, val);
  48.     st1[id] = ((st1[id << 1] + st1[id << 1 | 1])) % MOD ;
  49. }
  50.  
  51. int get1(int id, int l, int r, int u, int v) {
  52.     fix1(id, l, r);
  53.     if(v < l || u > r) {
  54.         return 0;
  55.     }
  56.     if(u <= l && v >= r) {
  57.         return st1[id] % MOD;
  58.     }
  59.     int m = (l + r) >> 1;
  60.     return ((get1(id << 1, l, m, u, v) % MOD) + (get1(id << 1 | 1, m + 1, r, u, v) % MOD)) % MOD ;
  61. }
  62.  
  63. void fix2(int id, int l, int r) {
  64.     if(lazy2[id]) {
  65.         int m = (l + r) >> 1;
  66.         (st2[id << 1] += lazy2[id] * (calc(m) - calc(l - 1))) %= MOD;
  67.         (st2[id << 1 | 1] += lazy2[id] * (calc(r) - calc(m))) %= MOD;        
  68.         (lazy2[id << 1] += lazy2[id]) %= MOD;
  69.         (lazy2[id << 1 | 1] += lazy2[id]) %= MOD;
  70.         lazy2[id] = 0;
  71.     }    
  72. }
  73.  
  74. void update2(int id, int l, int r, int u, int v, int val) {
  75.     if(v < l || u > r) {
  76.         return;
  77.     }
  78.     if(u <= l && v >= r) {
  79.         st2[id] += val * (calc(r) - calc(l - 1)) % MOD;
  80.         (lazy2[id] += val) %= MOD;
  81.         return;
  82.     }
  83.     fix2(id, l, r);
  84.     int m = (l + r) >> 1;
  85.     update2(id << 1, l, m, u, v, val);
  86.     update2(id << 1 | 1, m + 1, r, u, v, val);
  87.     st2[id] = ((st2[id << 1] + st2[id << 1 | 1])) % MOD;
  88. }
  89.  
  90. int get2(int id, int l, int r, int u, int v) {
  91.     fix2(id, l, r);
  92.     if(v < l || u > r) {
  93.         return 0;
  94.     }
  95.     if(u <= l && v >= r) {
  96.         return st2[id] % MOD;
  97.     }
  98.     int m = (l + r) >> 1;
  99.     return ((get2(id << 1, l, m, u, v) % MOD) + (get2(id << 1 | 1, m + 1, r, u, v) % MOD)) % MOD;
  100. }
  101.  
  102. void solve() {
  103.     cin >> n >> m;
  104.     while(m--) {
  105.         int op, l, r;
  106.         cin >> op >> l >> r;
  107.         if(op == 1) {
  108.             int A, B;
  109.             cin >> A >> B;
  110.             update1(1, 1, n, l, r, B - A * l);
  111.             update2(1, 1, n, l, r, A);
  112.         }
  113.         else {
  114.             cout << (get1(1, 1, n, l, r) % MOD + get2(1, 1, n, l, r) % MOD) % MOD << endl;
  115.         }
  116.     }
  117. }
  118.  
  119. #define TASK "code"
  120.  
  121. signed main () {
  122.    ios_base::sync_with_stdio (false);
  123.    cin.tie(nullptr), cout.tie(nullptr);
  124.    if (fopen(TASK".INP", "r")) {
  125.       freopen(TASK".INP", "r", stdin);
  126.       freopen(TASK".OUT", "w", stdout);
  127.    }
  128.    solve();
  129.    return 0;
  130. }
  131.  
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CTHltJ
language:
C++14 (clang 8.0)
created:
3 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!