fork download
copy 
  1. // Author: pppssslc
  2. // Date: 15/08/2026
  3. #include<bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. template<class X, class Y> void mini(X &x, const Y &y){
  8. 	x = min(x, y);
  9. }
  10.  
  11. template<class X, class Y> void maxi(X &x, const Y &y){
  12. 	x = max(x, y);
  13. }
  14.  
  15. typedef string str;
  16. typedef long long ll;
  17. typedef unsigned long long ull;
  18. typedef __int128 i128;
  19. typedef double db;
  20. typedef long double ld;
  21. typedef pair<int, int> pii;
  22. typedef pair<ll, ll> pll;
  23. typedef pair<ld, ld> pldld;
  24. typedef pair<db, db> pdd;
  25. typedef pair<char, char> pcc;
  26. typedef vector<int> vi;
  27. typedef vector<ll> vl;
  28. typedef vector<char> vc;
  29. typedef vector<pii> vpii;
  30. typedef vector<pll> vpll;
  31. typedef vector<vector<int>> vii;
  32. typedef vector<vector<ll>> vll;
  33. typedef vector<vector<char>> vcc;
  34. typedef map<int, int> mpii;
  35. typedef map<ll, ll> mpll;
  36. typedef set<int> si;
  37. typedef set<ll> sl;
  38. typedef complex<ld> cd;
  39.  
  40. #define se second
  41. #define fi first
  42. #define Rep(i, l, r, x) for(int i = l; i < (int)r; i += x)
  43. #define Repd(i, l, r, x) for(int i = l; i > (int)r; i -= x)
  44. #define For(i, l, r, x) for(int i = l; i <= (int)r; i += x)
  45. #define Ford(i, l, r, x) for(int i = l; i >= (int)r; i -= x)
  46. #define Fore(x, a) for(auto x: a)
  47. #define pb push_back
  48. #define pf push_front
  49. #define ppb pop_back
  50. #define ppf pop_front
  51. #define ins insert
  52. #define era erase
  53. #define upb upper_bound
  54. #define lwb lower_bound
  55. #define all(a) a.begin(), a.end()
  56.  
  57. const db PI = acos(-1);
  58. const ll inf = 1e18 + 1;
  59. const int mod = 1e9 + 7;
  60. const int maxn = 2e5 + 5;
  61.  
  62. int n, q;
  63. ll bit[maxn], st[maxn * 4], d[maxn], a[maxn];
  64.  
  65. ll gcd(ll a, ll b){
  66. 	if(!a) return abs(b);
  67. 	if(!b) return abs(a);
  68. 	return gcd(b, a % b);
  69. }
  70.  
  71. ll get(int k){
  72. 	ll ret = 0;
  73. 	Ford(i, k, 1, i&-i) ret += bit[i];
  74. 	return ret + 1;
  75. }
  76.  
  77. void upd(int k, int v){
  78. 	For(i, k, n, i&-i) bit[i] += v;
  79. }
  80.  
  81. ll get(int id, int l, int r, int u, int v){
  82. 	if(r < u || v < l) return 0;
  83. 	if(u <= l && r <= v) return st[id];
  84. 	int m = (l + r) >> 1;
  85. 	ll L = get(id * 2, l, m, u, v);
  86. 	ll R = get(id * 2 + 1, m + 1, r, u, v);
  87. 	return gcd(L, R);
  88. }
  89.  
  90. void upd(int id, int l, int r, int p, int v){
  91. 	if(p < l || r < p) return;
  92. 	if(l == r){
  93. 		st[id] += v;
  94. 		return;
  95. 	}
  96. 	int m = (l + r) >> 1;
  97. 	upd(id * 2, l, m, p, v);
  98. 	upd(id * 2 + 1, m + 1, r, p, v);
  99. 	st[id] = gcd(st[id * 2], st[id * 2 + 1]);
  100. }
  101.  
  102. signed main(){
  103. 	ios_base::sync_with_stdio(false);
  104. 	cin.tie(nullptr); cout.tie(nullptr);
  105. 	cin >> n >> q;
  106. 	For(i, 1, q, 1){
  107. 		int t, l, r; cin >> t >> l >> r;
  108. 		if(t == 1){
  109. 			int x; cin >> x;
  110. 			upd(l, x); upd(r + 1, -x);
  111. 			upd(1, 1, n, l, x);
  112. 			upd(1, 1, n, r + 1, -x);
  113. 		}else{
  114. 			cout << gcd(get(l), get(1, 1, n, l + 1, r)) << '\n';
  115. 		}
  116. 	}
  117. 	cerr << "TIME ELAPSED: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
  118. 	return 0;
  119. }
Success #stdin #stdout #stderr 0s 5324KB
comments (?)
stdin
copy 
5 5
2 1 5
1 2 3 5
1 4 5 2
2 2 4
2 2 3
stdout
copy 
1
3
6
stderr
copy 
TIME ELAPSED: 0.004264s.
https://ideone.com/1KwHcB
language:
C++14 (gcc 8.3)
created:
18 hours 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!