fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define fri(i,n) for(int i=0;i<n;i++)
  3. #define fr(i,a,b) for(int i=a;i<=b;i++)
  4. #define ol(v) v.begin(),v.end()
  5. #define forc(v) for(auto it:v)
  6. #define se second
  7. #define fi first
  8. #define pb push_back
  9. #define pf push_front
  10. #define MX 1e18
  11. #define MN -MX
  12. #define MOD 1000000007
  13. #define mid ((b+e)/2)
  14. #define left (2*i+1)
  15. #define right (2*i+2)
  16. using namespace std;
  17. typedef long long ll;
  18. typedef long double ld;
  19.  
  20. template <typename T> istream&operator>>(istream &inp, vector<T> &vec){
  21. 	fri(i,vec.size()) inp>>vec[i];
  22. 	return inp;
  23. }
  24.  
  25. template <typename T> ostream&operator<<(ostream &oup, vector<T> vec){
  26. 	forc(vec) oup<<it<<" ";
  27. 	oup<<"\n";
  28. 	return oup;
  29. }
  30.  
  31.  
  32. class l1{public:ll t, f, time;l1(){t = f = time = 0;} l1(ll a, ll b, ll c){t = a, f = b, time = c;}
  33. 		l1 operator+(const l1 &n){
  34. 			return l1(t+n.t, f+n.f, max(time, n.time));
  35. 		}
  36. 		};
  37. class l2{ public: ll l, r, t, f, time;l2(){l = r = t = f = time=0;} l2(ll a, ll b, ll c, ll d, ll e){l = a; r = b; t = c; f = d; time = e;}};
  38.  
  39. class nd{
  40. 	public:
  41. 	ll t, f;
  42. 	nd(){
  43. 		t = f = 0;
  44. 	}
  45. 	nd(ll a, ll b){
  46. 		t = a; f = b;
  47. 	}
  48.  
  49. 	ll get(){
  50. 		return min(t, f);
  51. 	}
  52. 	nd operator+(const nd &n){
  53. 		return nd(n.t+t, n.f+f);
  54. 	}
  55. };
  56.  
  57.  
  58. ll cnt;
  59. vector<ll> arr;
  60. vector<l1> ll1;
  61. vector<l2> ll2;
  62. vector<nd> segT;
  63.  
  64. ll tx, fx;
  65. int l, r;
  66. ll pp;
  67. vector<pair<ll, ll> > csum(100001);
  68.  
  69. ll T(ll n){ll kk=0;while(n>0 and n%2==0){kk++;n/=2;}return kk;}
  70. ll F(ll n){ll kk=0;while(n>0 and n%5==0){kk++;n/=5;}return kk;}
  71.  
  72. void init(){
  73. 	csum[0].fi = csum[0].se = 0;
  74. 	csum[1].fi = csum[1].se = 0;
  75. 	for(ll i = 2;i<=100000;i++){
  76. 		csum[i].fi = T(i)+csum[i-1].fi;
  77. 		csum[i].se = F(i)+csum[i-1].se;
  78. 	}
  79. }
  80.  
  81.  
  82. void build(int b, int e, int i){
  83. 	if(b==e){
  84. 		segT[i].t = T(arr[b]);
  85. 		segT[i].f = F(arr[b]);
  86. 		return;
  87. 	}
  88. 	build(b, mid, left);
  89. 	build(mid+1, e, right);
  90. 	segT[i] = segT[left]+segT[right];
  91. }
  92.  
  93. void first(int b, int e, int i){
  94.  
  95. 	segT[i].t += ll1[i].t*(e-b+1);
  96. 	segT[i].f += ll1[i].f*(e-b+1);
  97.  
  98. 	if(b!=e){
  99. 		ll1[left] = ll1[left]+ll1[i];
  100. 		ll1[right] = ll1[right]+ll1[i];//(ll1[i].t, ll1[i].f, ll1[i].time);
  101. 	}
  102. //	ll1[i] = l1();
  103. }
  104.  
  105. void second(int b, int e, int i){
  106.  
  107. 	segT[i].t = csum[e-ll2[i].l+1].fi - csum[b-ll2[i].l].fi + ll2[i].t*(e-b+1);
  108. 	segT[i].f = csum[e-ll2[i].l+1].se - csum[b-ll2[i].l].se + ll2[i].f*(e-b+1);
  109.  
  110. 	if(b!=e){
  111. 		ll2[left] = ll2[i];//(ll2[i].l, ll2[i].r, ll2[i].t, ll2[i].f, ll2[i].time);
  112. 		ll2[right] = ll2[i];//(ll2[i].l, ll2[i].r, ll2[i].t, ll2[i].f, ll2[i].time);
  113. 	}
  114. //	ll2[i] = l2();
  115. }
  116.  
  117. void lazy(int b, int e, int i){
  118.  
  119.  
  120. 	if(ll2[i].time) second(b, e, i);
  121. 	if(ll1[i].time) first(b, e, i);
  122. 	ll2[i] = l2();
  123. 	ll1[i] = l1();
  124. }
  125.  
  126. void update(int b, int e, int i){
  127. 	lazy(b, e, i);
  128.  
  129. 	if(b>r or e < l) return;
  130. 	if(b >= l and e <= r){
  131. 		segT[i].t += tx*(e-b+1);
  132. 		segT[i].f += fx*(e-b+1);
  133. 		if(b!=e){
  134. 			ll1[left].t += tx;
  135. 			ll1[right].f += fx;
  136. 			ll1[left].time = ll1[right].time = cnt;
  137. 			cnt++;
  138. 		}
  139. 		return;
  140. 	}
  141. 	update(b, mid, left);
  142. 	update(mid+1, e, right);
  143.  
  144. 	segT[i] = segT[left]+segT[right];
  145. }
  146.  
  147. void replace(int b, int e, int i){
  148. 	lazy(b, e, i);
  149.  
  150. 	if(b>r or e < l) return;
  151. 	if(b>=l and e <= r){
  152. 		ll tt = csum[e-l+1].fi-csum[b-l].fi + tx*(e-b+1);
  153. 		ll ff = csum[e-l+1].se-csum[b-l].se + fx*(e-b+1);
  154. 		segT[i].t = tt;
  155. 		segT[i].f = ff;
  156. 		if(b!=e){
  157. //			ll2[i] = l2();
  158. 			ll2[left] = l2(l, r, tx, fx, cnt);
  159. 			ll2[right] = l2(l, r, tx, fx, cnt++);
  160. //			ll1[i] = l1();
  161. 			ll1[left] = l1();
  162. 			ll1[right] = l1();
  163. 		}
  164. 		return;
  165. 	}
  166. 	replace(b, mid, left);
  167. 	replace(mid+1, e, right);
  168. 	segT[i] = segT[left]+segT[right];
  169. }
  170.  
  171. nd query(int b, int e, int i){
  172. 	lazy(b, e, i);
  173. 	if(b > r or e < l) return nd();
  174. 	if(b>=l and e <= r) return segT[i];
  175. 	return query(b, mid, left)+query(mid+1, e, right);
  176. }
  177.  
  178.  
  179. int main(){
  180. //	ios::sync_with_stdio(false);
  181. 	#ifdef DBG
  182. 		freopen("in", "r", stdin);
  183. 	#endif
  184. 	init();
  185. 	int tt;
  186. 	cin>>tt;
  187. 	while(tt--){
  188. 		cnt = 1;
  189. 		int n, m;
  190. 		cin>>n>>m;
  191. 		segT.clear();
  192. 		arr.clear();
  193. 		ll1.clear();
  194. 		ll2.clear();
  195. 		arr.resize(n);
  196. 		segT.resize(4*n);
  197. 		ll1.resize(4*n);
  198. 		ll2.resize(4*n);
  199. 		cin>>arr;
  200. 		build(0, n-1, 0);
  201. 		ll ans = 0;
  202. 		fri(i, m){
  203. 			int kk;
  204. 			cin>>kk>>l>>r;
  205. 			l--; r--;
  206. 			if(kk==1){
  207. 				cin>>pp;
  208. 				tx = T(pp);
  209. 				fx = F(pp);
  210. 				update(0, n-1, 0);
  211. 			}
  212. 			else if(kk==2){
  213. 				cin>>pp;
  214. 				tx = T(pp);
  215. 				fx = F(pp);
  216. 				replace(0, n-1, 0);
  217. 			}
  218. 			else{
  219. 				ans += query(0, n-1, 0).get();
  220. //				cout<<ans<<"\n";
  221. 			}
  222. 		}
  223. 		cout<<ans<<"\n";
  224.  
  225. 	}
  226.  
  227. 	return 0;
  228.  
  229. }
Success #stdin #stdout 0s 16072KB
comments (?)
stdin
copy 
2
5 5
2 4 3 5 5
3 2 4
3 2 5
2 2 4 1
1 3 3 10
3 1 5
6 6
5 4 10 12 15 18
3 1 6
2 2 5 5
3 3 6
1 1 4 20
3 1 3
3 1 2
stdout
copy 
5
14
https://ideone.com/ZTIq4d
language:
C++14 (gcc 8.3)
created:
6 years 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!