fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int MOD = 1e9 + 7;  
  11.  
  12. const int N = 1e5 + 5;  
  13.  
  14. int add(int a, int b) {
  15. 	return (a + b) % MOD;  
  16. }
  17.  
  18. int mul(int a, int b) {
  19. 	return 1ll * a * b % MOD; 
  20. }
  21.  
  22. int n, q; 
  23. int a[N];  
  24.  
  25. int seg[4 * N];  
  26. ii lazy[4 * N]; // lazy[id] = {mul, add}: seg[id] * mul + add
  27.  
  28. void initLazy() {
  29. 	for (int id = 1; id <= 4 * n; id++) lazy[id] = {1, 0}; 
  30. }
  31.  
  32. void build(int id, int l, int r) {
  33. 	if (l == r) {
  34. 		seg[id] = a[l]; 
  35. 		return; 
  36. 	}
  37.  
  38. 	int mid = (l + r) >> 1; 
  39. 	build(id * 2, l, mid); 
  40. 	build(id * 2 + 1, mid + 1, r);  
  41.  
  42. 	seg[id] = add(seg[id * 2], seg[id * 2 + 1]); 
  43. }
  44.  
  45. void push(int id, int l, int r) {
  46. 	int mid = (l + r) >> 1;  
  47.  
  48. 	seg[id * 2] = add(mul(seg[id * 2], lazy[id].first), mul(mid - l + 1, lazy[id].second)); 
  49. 	lazy[id * 2].first = mul(lazy[id * 2].first, lazy[id].first); 
  50. 	lazy[id * 2].second = add(mul(lazy[id * 2].second, lazy[id].first), lazy[id].second); 
  51.  
  52. 	seg[id * 2 + 1] = add(mul(seg[id * 2 + 1], lazy[id].first), mul(r - mid, lazy[id].second)); 
  53. 	lazy[id * 2 + 1].first = mul(lazy[id * 2 + 1].first, lazy[id].first); 
  54. 	lazy[id * 2 + 1].second = add(mul(lazy[id * 2 + 1].second, lazy[id].first), lazy[id].second); 
  55.  
  56. 	lazy[id] = {1, 0}; 
  57. }
  58.  
  59. void update(int id, int l, int r, int u, int v, ii val) {
  60. 	if (l > v || r < u) return; 
  61.  
  62. 	if (u <= l && r <= v) {
  63. 		seg[id] = add(mul(seg[id], val.first), mul(r - l + 1, val.second));
  64. 		lazy[id].first = mul(lazy[id].first, val.first);
  65. 		lazy[id].second = add(mul(lazy[id].second, val.first), val.second); 
  66. 		return;  
  67. 	}
  68.  
  69. 	push(id, l, r);   
  70.  
  71. 	int mid = (l + r) >> 1; 
  72. 	update(id * 2, l, mid, u, v, val); 
  73. 	update(id * 2 + 1, mid + 1, r, u, v, val); 
  74.  
  75. 	seg[id] = add(seg[id * 2], seg[id * 2 + 1]); 
  76. }
  77.  
  78. int get(int id, int l, int r, int u, int v) {
  79. 	if (l > v || r < u) return 0; 
  80.  
  81. 	if (u <= l && r <= v) return seg[id];  
  82.  
  83. 	push(id, l, r);  
  84.  
  85. 	int mid = (l + r) >> 1;  
  86. 	return add(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v)); 
  87. }
  88.  
  89. int main() {
  90. 	ios::sync_with_stdio(0); cin.tie(0);  	
  91. 	cin >> n >> q; 
  92. 	for (int i = 1; i <= n; i++) cin >> a[i];
  93.  
  94. 	build(1, 1, n); 
  95. 	initLazy();   
  96.  
  97. 	while (q--) {
  98. 		int type, l, r; 
  99. 		cin >> type >> l >> r; 
  100.  
  101. 		if (type == 4) {
  102. 			cout << get(1, 1, n, l, r) << '\n'; 
  103. 		}
  104. 		else {
  105. 			int x; cin >> x;  
  106.  
  107. 			ii val; 
  108. 			if (type == 1) val = {1, x}; 
  109. 			if (type == 2) val = {x, 0};  
  110. 			if (type == 3) val = {0, x}; 
  111.  
  112. 			update(1, 1, n, l, r, val);  
  113. 		}
  114. 	}
  115. }
Success #stdin #stdout 0.01s 5644KB
comments (?)
stdin
copy 
5 4
1 2 3 4 5
1 1 3 2
2 2 4 4
3 4 5 2
4 1 5
stdout
copy 
43
https://ideone.com/tWZJQO
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!