fork download
copy 
  1. /* Author : Triet Do Thanh - FPT University */
  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      = 2e5 + 7;
  13. const long long oo     = 1e18 + 7;
  14. const long long MOD    = 1e9 + 7;
  15.  
  16. int n, q;
  17. int a[N];
  18.  
  19. int st[3][N * 4], lz[3][N * 4];
  20.  
  21. void push1(int id, int l, int r) {
  22.     if (lz[1][id]) {
  23.         int mid = (l + r) >> 1;
  24.         (st[1][id * 2] += lz[1][id] * (mid - l + 1)) %= MOD;
  25.         (st[1][id * 2 + 1] += lz[1][id] * (r - (mid + 1) + 1)) %= MOD;
  26.         (lz[1][id * 2] += lz[1][id]) %= MOD;
  27.         (lz[1][id * 2 + 1] += lz[1][id]) %= MOD;
  28.         lz[1][id] = 0;
  29.     }
  30. }
  31.  
  32. void upd1(int id, int l, int r, int u, int v, int val) {
  33.     if (l > v || r < u) return;
  34.     if (l >= u && r <= v) {
  35.         (st[1][id] += (r - l + 1) * val) %= MOD;
  36.         (lz[1][id] += val) %= MOD;
  37.         return;
  38.     }
  39.     push1(id, l, r);
  40.     int mid = (l + r) >> 1;
  41.     upd1(id * 2, l, mid, u, v, val); upd1(id * 2 + 1, mid + 1, r, u, v, val);
  42.     st[1][id] = (st[1][id * 2] + st[1][id * 2 + 1]) % MOD;
  43. }
  44.  
  45. int g1(int id, int l, int r, int u, int v) {
  46.     push1(id, l, r);
  47.     if (l > v || r < u) return 0;
  48.     if (l >= u && r <= v) {
  49.         return st[1][id] % MOD;   
  50.     }
  51.     int mid = (l + r) >> 1;
  52.     return ((g1(id * 2, l, mid, u, v) % MOD) + (g1(id * 2 + 1, mid + 1, r, u, v) % MOD)) % MOD;
  53. }
  54.  
  55. int calc(int pos) {
  56.     return pos * (pos + 1) / 2;
  57. }
  58.  
  59. void push2(int id, int l, int r) {
  60.     if (lz[2][id]) {
  61.         int mid = (l + r) >> 1;
  62.         (st[2][id * 2] += lz[2][id] * (calc(mid) - calc(l - 1))) %= MOD;
  63.         (st[2][id * 2 + 1] += lz[2][id] * (calc(r) - calc(mid))) %= MOD;
  64.         (lz[2][id * 2] += lz[2][id]) %= MOD;
  65.         (lz[2][id * 2 + 1] += lz[2][id]) %= MOD;
  66.         lz[2][id] = 0 ;
  67.     }
  68. }
  69.  
  70. void upd2(int id, int l, int r, int u, int v, int val) {
  71.     if (l > v || r < u) return;
  72.     if (l >= u && r <= v) {
  73.         (st[2][id] += (calc(r) - calc(l - 1)) * val) %= MOD;
  74.         (lz[2][id] += val) %= MOD;
  75.         return;
  76.     }
  77.     push2(id, l, r);
  78.     int mid = (l + r) >> 1;
  79.     upd2(id * 2, l, mid, u, v, val); upd2(id * 2 + 1, mid + 1, r, u, v, val);
  80.     st[2][id] = (st[2][id * 2] + st[2][id * 2 + 1]) % MOD;
  81. }
  82.  
  83. int g2(int id, int l, int r, int u, int v) {
  84.     push2(id, l, r);
  85.     if (l > v || r < u) return 0;
  86.     if (l >= u && r <= v) {
  87.         return st[2][id] % MOD;
  88.     }
  89.     int mid = (l + r) >> 1;
  90.     return ((g2(id * 2, l, mid, u, v) % MOD) + (g2(id * 2 + 1, mid + 1, r, u, v) % MOD)) % MOD;
  91. }
  92.  
  93. void update(int l, int r, int a, int b) {
  94.     upd1(1,1,n,l,r,b);
  95.     upd1(1,1,n,l,r,((-l * a) + MOD * MOD) % MOD);
  96.     upd2(1,1,n,l,r,a);
  97. }
  98.  
  99. int get(int l, int r) {
  100.     return (g1(1,1,n,l,r) + g2(1,1,n,l,r)) % MOD;
  101. }
  102.  
  103. void solve() {
  104.     cin >> n >> q;
  105.  
  106.     while (q-->0) {
  107.         int op; cin >> op;
  108.         if (op == 1) {
  109.             int l, r, a, b; cin >> l >> r >> a >> b;
  110.             update(l, r, a, b);
  111.         }
  112.         else {
  113.             int l, r; cin >> l >> r;
  114.             cout << get(l, r) << endl;
  115.         }
  116.     }
  117. }
  118.  
  119. #define TASK "test"
  120.  
  121. signed main()
  122. {
  123.    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  124.    if (fopen("input.txt", "r")) {
  125.       freopen("input.txt", "r", stdin);
  126.       freopen("output.txt", "w", stdout);
  127.    }
  128.    solve();
  129.    return 0;
  130. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tY0L10
language:
C++14 (gcc 8.3)
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!