fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. vector<int>inp;
  5. const int MODE  = 1e9+7;
  6. struct Query
  7. {
  8. 	int a,b,c,d;
  9. };
  10. vector<Query> query;
  11. vector<long long> seg;
  12. vector<vector<long long>> segmu;
  13. int q;
  14. void build(int id, int l, int r)
  15. {
  16. 	if(l == r)
  17. 	{
  18. 		seg[id] = inp[l];
  19. 		return;
  20. 	}
  21. 	int mid = (l+r)/2;
  22. 	build(id*2, l, mid);
  23. 	build(id*2+1, mid+1, r);
  24. 	seg[id] = (seg[id*2] + seg[id*2+1]) % MODE;
  25. }
  26. void update(int id, int l, int r, int pos, int val)
  27. {
  28. 	if(l == r)
  29. 	{
  30. 		seg[id] =val;
  31. 		return;
  32. 	}
  33. 	int mid = (l+r)/2;
  34. 	if(mid >= pos) update(id*2, l, mid, pos, val);
  35. 	else update(id*2+1, mid+1, r, pos, val);
  36. 	seg[id] = (seg[id*2] + seg[id*2+1]) % MODE;
  37. }
  38.  
  39. long long get(int id, int l, int r, int u, int v)
  40. {
  41. 	if( u > r || v < l) return 0;
  42. 	if(u <= l && v >= r) return seg[id];
  43. 	int mid = (l+r)/2;
  44. 	return (get(id*2, l, mid, u, v) + get(id*2+1, mid+1, r, u, v)) % MODE;
  45. }
  46. long long pw(int x, int y)
  47. {
  48. 	long long res = 1,  mul = x;
  49. 	while(y > 0)
  50. 	{
  51. 		if(y & 1) res =(1LL*res*mul) % MODE;
  52. 		mul = (1ll*mul*mul) % MODE;
  53. 		y >>=1;
  54. 	}
  55. 	return res;
  56. }
  57.  
  58. void buildmu(int id, int l, int r, int k, vector<long long>&seg)
  59. {
  60. 	if(l == r)
  61. 	{
  62. 		seg[id] = pw(inp[l], k);
  63. 		return;
  64. 	}
  65. 	int mid = (l+r)/2;
  66. 	buildmu(id*2, l, mid, k, seg);
  67. 	buildmu(id*2+1, mid+1, r, k, seg);
  68. 	seg[id] = (seg[id*2] + seg[id*2+1]) % MODE;
  69. 	return;
  70. }
  71.  
  72. void updatemu(int id, int l, int r, int pos, int val, int k, vector<long long>&seg)
  73. {
  74. 	if(l == r)
  75. 	{
  76. 		seg[id] = pw(val, k);
  77. 		return;
  78. 	}
  79. 	int mid  = (l+r)/2;
  80. 	if(mid >= pos) updatemu(id*2, l, mid, pos, val, k, seg);
  81. 	else updatemu(id*2+1, mid+1, r, pos, val, k, seg);
  82. 	seg[id] = (seg[id*2] + seg[id*2+1]) % MODE;
  83. }
  84.  
  85. long long getmu(int id, int l, int r, int u, int v, vector<long long>&seg)
  86. {
  87. 	if(u > r || v < l) return 0;
  88. 	if(u <= l && v >= r) return seg[id];
  89. 	int mid = (l+r)/2;
  90. 	return (getmu(id*2, l, mid, u, v, seg) +getmu(id*2+1,mid+1, r, u, v, seg)) % MODE;
  91. }
  92. void sub()
  93. {
  94. 	seg.resize(4*n+1);
  95. 	segmu.resize(6, vector<long long>(4*n+1));
  96. 	for(int i =1; i<=5; i++) buildmu(1, 1, n, i, segmu[i]);
  97. 	build(1, 1, n);
  98. 	for(int i =1; i<=q;i++)
  99. 	{
  100. 		if(query[i].a == 1)
  101. 		{
  102. 			for(int j = 1; j<=5; j++) updatemu(1, 1, n, query[i].b, query[i].c, j, segmu[j]);
  103. 			update(1, 1, n, query[i].b, query[i].c);
  104. 		}
  105. 		else
  106. 		{
  107. 			long long luythuatong = pw(get(1, 1, n, query[i].b, query[i].c), query[i].d);
  108. 			long long tongluythua = getmu(1, 1, n, query[i].b, query[i].c, segmu[query[i].d]);
  109. 			//cout << luythuatong << " " << tongluythua << endl;
  110. 			int tmp = 0;
  111. 			if(query[i].d == 1) tmp = query[i].c - query[i].b;
  112. 			else if(query[i].d == 2)tmp = query[i].c - query[i].b +1;
  113. 			else if(query[i].d == 3) tmp = query[i].c - query[i].b +1;
  114. 			if(query[i].d == 3) 	cout << (((long long)2*luythuatong) % MODE  + ((long long)(2*tmp + 4)*tongluythua) % MODE ) % MODE << '\n';
  115. 			else cout << (((long long)2*luythuatong) % MODE  + ((long long)2*(tmp)*tongluythua) % MODE ) % MODE << '\n';
  116. 		}
  117. 	}
  118. }
  119.  
  120. int main()
  121. {
  122. 	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  123. 	cin >> n >> q;
  124. 	inp.resize(n+1);
  125. 	query.resize(q+1);
  126. 	for(int i =1; i<=n; i++) cin >> inp[i];
  127. 	for(int  i =1; i<=q; i++)
  128. 	{
  129. 		int a; cin >> a;
  130. 		query[i].a = a;
  131. 		if(a == 1)
  132. 		{
  133. 			int b,c; cin >> b >> c;
  134. 			query[i].b = b;
  135. 			query[i].c = c;
  136. 		}
  137. 		else 
  138. 		{
  139. 			int b,c,d; cin >> b >> c >> d;
  140. 			query[i] = {a, b, c, d};
  141. 		}
  142. 	}
  143. 	//sub1();
  144. 	sub();
  145. 	return 0;
  146. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3 3
1 2 3
2 1 3 1
1 2 0
2 1 2 3
stdout
copy 
36
10
https://ideone.com/86LWTn
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!