fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = (int) 1e5 + 7;
  5. const long long mod = (long long) 1e9 + 7;
  6. int n, q, command;
  7. long long a[N], l, r, x, y;
  8.  
  9. struct SEGTREE{
  10.     vector<long long> tree, lazy_one, lazy_two;
  11.  
  12.     void init(int n){
  13.         tree.resize(4 * n + 7);
  14.         lazy_one.resize(4 * n + 7);
  15.         lazy_two.resize(4 * n + 7);
  16.     }
  17.  
  18.     void push_one(int node, long long l, long long r){
  19.         if(!lazy_one[node]) return;
  20.         tree[node] += (r - l + 1) * lazy_one[node];
  21.         tree[node] %= mod;
  22.         if(l != r){
  23.             lazy_one[node * 2] += lazy_one[node];
  24.             lazy_one[node * 2 + 1] += lazy_one[node];
  25.         }
  26.         lazy_one[node] = 0;
  27.     }
  28.  
  29.     void push_two(int node, long long l, long long r){
  30.         if(!lazy_two[node]) return;
  31.         tree[node] += (r - l + 1) * (r + l) / 2 * lazy_two[node];
  32.         tree[node] %= mod;
  33.         if(l != r){
  34.             lazy_two[node * 2] += lazy_two[node];
  35.             lazy_two[node * 2 + 1] += lazy_two[node];
  36.         }
  37.         lazy_two[node] = 0;
  38.     }
  39.  
  40.     void update_one(int node, long long l, long long r, int u, int v, long long val){
  41.         push_one(node, l, r);
  42.         if(v < l || r < u) return;
  43.         if(u <= l && r <= v){
  44.             lazy_one[node] += val;
  45.             push_one(node, l, r);
  46.             return;
  47.         }
  48.         int mid = l + (r - l) / 2;
  49.         update_one(node * 2, l, mid, u, v, val);
  50.         update_one(node * 2 + 1, mid + 1, r, u, v, val);
  51.         tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % mod;
  52.     }
  53.  
  54.     void update_two(int node, long long l, long long r, int u, int v, long long val){
  55.         push_two(node, l, r);
  56.         if(v < l || r < u) return;
  57.         if(u <= l && r <= v){
  58.             lazy_two[node] += val;
  59.             push_two(node, l, r);
  60.             return;
  61.         }
  62.         int mid = l + (r - l) / 2;
  63.         update_two(node * 2, l, mid, u, v, val);
  64.         update_two(node * 2 + 1, mid + 1, r, u, v, val);
  65.         tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % mod;
  66.     }
  67.  
  68.     long long get(int node, long long l, long long r, int u, int v){
  69.         push_two(node, l, r);
  70. 		push_one(node, l, r);
  71.         if(v < l || r < u) return 0;
  72.         if(u <= l && r <= v) return tree[node] % mod;
  73.         int mid = l + (r - l) / 2;
  74.         long long get1 = get(node * 2, l, mid, u, v) % mod;
  75.         long long get2 = get(node * 2 + 1, mid + 1, r, u, v) % mod;
  76.         return (get1 + get2) % mod;
  77.     }
  78. } segtree;
  79.  
  80. int main(){
  81.     ios_base::sync_with_stdio(false);
  82.     cin.tie(0); cout.tie(0);
  83.     //freopen("marisa.inp", "r", stdin);
  84.     //freopen("marisa.out", "w", stdout);
  85.     cin >> n >> q;
  86.  
  87.     segtree.init(n);
  88.     while(q--){
  89.         cin >> command >> l >> r;
  90.         if(command & 1){
  91.             cin >> x >> y;
  92.             segtree.update_two(1, 1, n, l, r, x);
  93. 			segtree.update_one(1, 1, n, l, r, y - l * x);
  94.         }
  95.         else cout << segtree.get(1, 1, n, l, r) << "\n";
  96.     }
  97. }
Success #stdin #stdout 0.01s 5408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pm8nRN
language:
C++14 (gcc 8.3)
created:
2 years 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!