fork download 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<int,int> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. const int C = 3;
  25. const int BL = 800;
  26.  
  27. unsigned int B[100001][3];
  28.  
  29. struct change
  30. {
  31. 	unsigned int add,mult;
  32. };
  33.  
  34. struct block
  35. {
  36. 	int l,r;
  37. 	change mod[3][3];
  38. 	unsigned int sum[3];
  39. };
  40.  
  41. block init(int l, int r)
  42. {
  43. 	block tmp;
  44. 	memset(tmp.sum,0,sizeof(tmp.sum));
  45. 	////////cerr<<"SUM : "<<tmp.sum[0]<<'\n';
  46. 	for(int j=0;j<3;j++)
  47. 	{
  48. 		for(int i=l;i<=r;i++)
  49. 		{
  50. 			tmp.sum[j]+=B[i][j];
  51. 			//////cerr<<i<<' '<<j<<' '<<B[i][j]<<' '<<tmp.sum[j]<<' '<<l<<' '<<r<<'\n';
  52. 		}
  53. 		//////cerr<<l<<' '<<r<<' '<<tmp.sum[j]<<'\n';
  54. 	}
  55. 	for(int i=0;i<3;i++)
  56. 	{
  57. 		for(int j=0;j<3;j++)
  58. 		{
  59. 			tmp.mod[i][j].add=0;
  60. 			if(i==j) tmp.mod[i][j].mult=1;
  61. 			else tmp.mod[i][j].mult=0;
  62. 		}
  63. 	}
  64. 	tmp.l=l; tmp.r=r;
  65. 	return tmp;
  66. }
  67.  
  68.  
  69. list<block> vec; //linked list of blocks
  70. typedef list<block>::iterator lit;
  71.  
  72. unsigned int queryblock(lit a, int idx)
  73. {
  74. 	return a->sum[idx];
  75. }
  76.  
  77. void propogate(lit it) //update a for the part it
  78. {
  79. 	int l = it->l; int r = it->r;
  80. 	for(int i = l; i <= r; i++)
  81. 	{
  82. 		unsigned int s[3];
  83. 		for(int j = 0; j < 3; j++)
  84. 		{
  85. 			s[j]=0;
  86. 			for(int k = 0; k < 3; k++)
  87. 			{
  88. 				s[j] += B[i][k]*it->mod[j][k].mult;
  89. 				s[j] += it->mod[j][k].add;
  90. 				////cerr<<it->mod[j][k].mult<<' '<<it->mod[j][k].add<<" | ";
  91. 			}
  92. 			////cerr<<s[j]<<' ';
  93. 			////cerr<<'\n';
  94. 		}
  95. 		////cerr<<'\n';
  96. 		for(int j=0;j<3;j++) 
  97. 		{
  98. 			B[i][j]=s[j];
  99. 		}
  100. 	}	
  101. }
  102.  
  103. void recalc(int n) //recalculates the whole thing. call recalc(w)
  104. {
  105. 	for(lit it = vec.begin(); it != vec.end(); it++)
  106. 	{
  107. 		propogate(it);
  108. 	}	
  109. 	vec.clear();
  110. 	for(int i = 0; i < n; i+=BL)
  111. 	{
  112. 		int l = i; int r = min(n-1,i+BL-1);
  113. 		vec.pb(init(l,r));
  114. 		////////cerr<<l<<' '<<r<<'\n';
  115. 	}
  116. }
  117.  
  118. lit split(lit it, int mid) //split into [l, mid] and [mid+1, r]. returns the last position
  119. {
  120. 	int l = it->l;
  121. 	int r = it->r;
  122. 	propogate(it);
  123. 	block a = init(l,mid);
  124. 	block b = init(mid+1,r);
  125. 	//////cerr<<"SUM : "<<b.sum[0]<<'\n';
  126. 	lit it2 = vec.insert(it,a);
  127. 	it2++;
  128. 	lit it3 = vec.erase(it2);
  129. 	return vec.insert(it3,b);
  130. }
  131.  
  132. unsigned int query(int l, int r, int idx)
  133. {
  134. 	unsigned int res = 0;
  135. 	for(lit it = vec.begin(); it != vec.end(); it++)
  136. 	{
  137. 		int L = it->l; int R = it->r;
  138. 		if(L>R) continue;
  139. 		if(R<l||L>r) continue;
  140.  
  141. 		if(l<=L&&R<=r)
  142. 		{
  143. 			res+=queryblock(it,idx);
  144. 		}
  145. 		else if(L<=l&&r<=R) //L l r R
  146. 		{
  147. 			//////cerr<<"HERE IT : "<<it->l<<' '<<it->r<<' '<<it->sum[idx]<<' '<<B[0][0]<<' '<<it->mod[0][0].mult<<'\n';
  148. 			lit tmp = split(it,l-1);
  149. 			//////cerr<<"HERE 2 : "<<tmp->l<<' '<<tmp->r<<' '<<tmp->sum[idx]<<' '<<B[0][0]<<'\n';
  150. 			lit tmp2 = split(tmp,r);
  151. 			tmp2--;
  152. 			//////cerr<<"HERE : "<<tmp2->l<<' '<<tmp2->r<<' '<<tmp2->sum[idx]<<'\n';
  153. 			it=tmp2;
  154. 			res+=queryblock(it,idx);
  155. 		}
  156. 		else if(L<l) //L l R r
  157. 		{
  158. 			lit tmp = split(it,l-1);
  159. 			it=tmp;
  160. 			 //cerr<<"L R : "<<it->l<<' '<<it->r<<' '<<res<<' '<<queryblock(it,idx)<<'\n';
  161. 			res+=queryblock(it,idx);
  162. 		}
  163. 		else if(R>r) //l L r R
  164. 		{
  165. 			lit tmp = split(it,r);
  166. 			tmp--;
  167. 			it=tmp;
  168. 			//cerr<<"L R : "<<it->l<<' '<<it->r<<' '<<res<<' '<<queryblock(it,idx)<<'\n';
  169. 			res+=queryblock(it,idx);
  170. 		}
  171. 		else assert(0);
  172. 	}
  173. 	return res;
  174. }
  175.  
  176. void copy(int l, int r, int t1, int t2)
  177. {
  178. 	for(lit it = vec.begin(); it != vec.end(); it++)
  179. 	{
  180. 		int L = it->l; int R = it->r;
  181. 		if(L>R) continue;
  182. 		if(R<l||L>r) continue;
  183. 		if(l<=L&&R<=r)
  184. 		{
  185. 			for(int j=0;j<3;j++)
  186. 			{
  187. 				it->mod[t2][j]=it->mod[t1][j];
  188. 			}
  189. 			it->sum[t2]=it->sum[t1];
  190. 		}
  191. 		else if(L<=l&&r<=R) //L l r R
  192. 		{
  193. 			lit tmp = split(it,l-1);
  194. 			lit tmp2 = split(tmp,r);
  195. 			tmp2--;
  196. 			it=tmp2;
  197. 			for(int j=0;j<3;j++)
  198. 			{
  199. 				it->mod[t2][j]=it->mod[t1][j];
  200. 			}
  201. 			it->sum[t2]=it->sum[t1];
  202. 		}
  203. 		else if(L<l) //L l R r
  204. 		{
  205. 			lit tmp = split(it,l-1);
  206. 			it=tmp;
  207. 			for(int j=0;j<3;j++)
  208. 			{
  209. 				it->mod[t2][j]=it->mod[t1][j];
  210. 			}
  211. 			it->sum[t2]=it->sum[t1];
  212. 		}
  213. 		else if(R>r) //l L r R
  214. 		{
  215. 			lit tmp = split(it,r);
  216. 			tmp--;
  217. 			it=tmp;
  218. 			for(int j=0;j<3;j++)
  219. 			{
  220. 				it->mod[t2][j]=it->mod[t1][j];
  221. 			}
  222. 			it->sum[t2]=it->sum[t1];
  223. 		}
  224. 		else assert(0);
  225. 	}
  226. }
  227.  
  228. void swap(int l, int r, int t1, int t2)
  229. {
  230. 	for(lit it = vec.begin(); it != vec.end(); it++)
  231. 	{
  232. 		int L = it->l; int R = it->r;
  233. 		if(L>R) continue;
  234. 		if(R<l||L>r) continue;
  235. 		if(l<=L&&R<=r)
  236. 		{
  237. 			for(int j=0;j<3;j++)
  238. 			{
  239. 				swap(it->mod[t2][j],it->mod[t1][j]);
  240. 			}
  241. 			swap(it->sum[t2],it->sum[t1]);
  242. 		}
  243. 		else if(L<=l&&r<=R) //L l r R
  244. 		{
  245. 			lit tmp = split(it,l-1);
  246. 			lit tmp2 = split(tmp,r);
  247. 			tmp2--;
  248. 			it=tmp2;
  249. 			for(int j=0;j<3;j++)
  250. 			{
  251. 				swap(it->mod[t2][j],it->mod[t1][j]);
  252. 			}
  253. 			swap(it->sum[t2],it->sum[t1]);
  254. 		}
  255. 		else if(L<l) //L l R r
  256. 		{
  257. 			lit tmp = split(it,l-1);
  258. 			it=tmp;
  259. 			for(int j=0;j<3;j++)
  260. 			{
  261. 				swap(it->mod[t2][j],it->mod[t1][j]);
  262. 			}
  263. 			swap(it->sum[t2],it->sum[t1]);
  264. 		}
  265. 		else if(R>r) //l L r R
  266. 		{
  267. 			lit tmp = split(it,r);
  268. 			tmp--;
  269. 			it=tmp;
  270. 			for(int j=0;j<3;j++)
  271. 			{
  272. 				swap(it->mod[t2][j],it->mod[t1][j]);
  273. 			}
  274. 			swap(it->sum[t2],it->sum[t1]);
  275. 		}
  276. 		else assert(0);
  277. 	}
  278. }
  279.  
  280. void modify(int l, int r, int t, unsigned int p1, unsigned int p2)
  281. {
  282. 	for(lit it = vec.begin(); it != vec.end(); it++)
  283. 	{
  284. 		int L = it->l; int R = it->r;
  285. 		if(L>R) continue;
  286. 		if(R<l||L>r) continue;
  287. 		if(l<=L&&R<=r)
  288. 		{
  289. 			for(int j=0;j<3;j++)
  290. 			{
  291. 				//it->mod[t2][j]=it->mod[t1][j];
  292. 				unsigned int a = it->mod[t][j].mult;
  293. 				unsigned int b = it->mod[t][j].add;
  294. 				it->mod[t][j].mult=a*p1;
  295. 				it->mod[t][j].add=b*p1;
  296. 			}
  297. 			it->mod[t][0].add+=p2;
  298. 			it->sum[t]*=p1;
  299. 			it->sum[t]+=(R-L+1)*p2;
  300. 		}
  301. 		else if(L<=l&&r<=R) //L l r R
  302. 		{
  303. 			lit tmp = split(it,l-1);
  304. 			lit tmp2 = split(tmp,r);
  305. 			tmp2--;
  306. 			it=tmp2;
  307. 			for(int j=0;j<3;j++)
  308. 			{
  309. 				//it->mod[t2][j]=it->mod[t1][j];
  310. 				unsigned int a = it->mod[t][j].mult;
  311. 				unsigned int b = it->mod[t][j].add;
  312. 				it->mod[t][j].mult=a*p1;
  313. 				it->mod[t][j].add=b*p1;
  314. 			}
  315. 			it->mod[t][0].add+=p2;
  316. 			it->sum[t]*=p1;
  317. 			it->sum[t]+=(it->r-it->l+1)*p2;
  318. 		}
  319. 		else if(L<l) //L l R r
  320. 		{
  321. 			lit tmp = split(it,l-1);
  322. 			it=tmp;
  323. 			for(int j=0;j<3;j++)
  324. 			{
  325. 				//it->mod[t2][j]=it->mod[t1][j];
  326. 				unsigned int a = it->mod[t][j].mult;
  327. 				unsigned int b = it->mod[t][j].add;
  328. 				it->mod[t][j].mult=a*p1;
  329. 				it->mod[t][j].add=b*p1;
  330. 			}
  331. 			it->mod[t][0].add+=p2;
  332. 			it->sum[t]*=p1;
  333. 			it->sum[t]+=(it->r-it->l+1)*p2;
  334. 			 //cerr<<"SUM : "<<it->l<<' '<<it->r<<' '<<it->sum[t]<<'\n';
  335. 		}
  336. 		else if(R>r) //l L r R
  337. 		{
  338. 			lit tmp = split(it,r);
  339. 			tmp--;
  340. 			it=tmp;
  341. 			for(int j=0;j<3;j++)
  342. 			{
  343. 				//it->mod[t2][j]=it->mod[t1][j];
  344. 				unsigned int a = it->mod[t][j].mult;
  345. 				unsigned int b = it->mod[t][j].add;
  346. 				it->mod[t][j].mult=a*p1;
  347. 				it->mod[t][j].add=b*p1;
  348. 			}
  349. 			it->mod[t][0].add+=p2;
  350. 			it->sum[t]*=p1;
  351. 			it->sum[t]+=(it->r-it->l+1)*p2;
  352. 			 //cerr<<"SUM : "<<it->l<<' '<<it->r<<' '<<it->sum[t]<<'\n';
  353. 		}
  354. 		else assert(0);
  355. 		/*
  356. 		propogate(it);
  357. 		block tmp = init(it->l,it->r);
  358. 		(*it) = tmp;
  359. 		*/
  360. 	}
  361. }
  362.  
  363. void advmodify(int l, int r, int t1, int t2, unsigned int p)
  364. {
  365. 	for(lit it = vec.begin(); it != vec.end(); it++)
  366. 	{
  367. 		int L = it->l; int R = it->r;
  368. 		if(L>R) continue;
  369. 		if(R<l||L>r) continue;
  370. 		if(l<=L&&R<=r)
  371. 		{
  372. 			it->sum[t2]+=p*it->sum[t1];
  373. 			for(int j=0;j<3;j++)
  374. 			{
  375. 				//it->mod[t2][j]=it->mod[t1][j];
  376. 				it->mod[t2][j].mult += it->mod[t1][j].mult*p;
  377. 				it->mod[t2][j].add += it->mod[t1][j].add*p;
  378. 			}
  379. 		}
  380. 		else if(L<=l&&r<=R) //L l r R
  381. 		{
  382. 			lit tmp = split(it,l-1);
  383. 			lit tmp2 = split(tmp,r);
  384. 			tmp2--;
  385. 			it=tmp2;
  386. 			it->sum[t2]+=p*it->sum[t1];
  387. 			for(int j=0;j<3;j++)
  388. 			{
  389. 				//it->mod[t2][j]=it->mod[t1][j];
  390. 				it->mod[t2][j].mult += it->mod[t1][j].mult*p;
  391. 				it->mod[t2][j].add += it->mod[t1][j].add*p;
  392. 			}
  393. 		}
  394. 		else if(L<l) //L l R r
  395. 		{
  396. 			lit tmp = split(it,l-1);
  397. 			it=tmp;
  398. 			it->sum[t2]+=p*it->sum[t1];
  399. 			for(int j=0;j<3;j++)
  400. 			{
  401. 				//it->mod[t2][j]=it->mod[t1][j];
  402. 				it->mod[t2][j].mult += it->mod[t1][j].mult*p;
  403. 				it->mod[t2][j].add += it->mod[t1][j].add*p;
  404. 			}
  405. 		}
  406. 		else if(R>r) //l L r R
  407. 		{
  408. 			lit tmp = split(it,r);
  409. 			tmp--;
  410. 			it=tmp;
  411. 			it->sum[t2]+=p*it->sum[t1];
  412. 			for(int j=0;j<3;j++)
  413. 			{
  414. 				//it->mod[t2][j]=it->mod[t1][j];
  415. 				it->mod[t2][j].mult += it->mod[t1][j].mult*p;
  416. 				it->mod[t2][j].add += it->mod[t1][j].add*p;
  417. 			}
  418. 		}
  419. 		else assert(0);
  420. 		/*
  421. 		propogate(it);
  422. 		block tmp = init(it->l,it->r);
  423. 		(*it) = tmp;
  424. 		*/
  425. 	}
  426. }
  427.  
  428. int main()
  429. {
  430. 	ios_base::sync_with_stdio(0); cin.tie(0);
  431. 	/*
  432. 	freopen("diskraid.txt","r",stdin);
  433. 	freopen("diskraidans.txt","w",stdout);
  434. 	*/
  435. 	int n, w, q;
  436. 	cin>>n>>w>>q;
  437. 	for(int i=0;i<w;i++)
  438. 	{
  439. 		for(int j=0;j<n;j++)
  440. 		{
  441. 			//read the i-th element of j-th register
  442. 			cin>>B[i][j];
  443. 		}
  444. 	}
  445. 	recalc(w);
  446. 	for(int i=0;i<q;i++)
  447. 	{
  448. 		char c; cin>>c;
  449. 		if(c=='Q')
  450. 		{
  451. 			int l,r,t;
  452. 			cin>>l>>r>>t;
  453. 			unsigned int ans = query(l,r,t);
  454. 			assert(ans>=0);
  455. 			//cout<<"Case #"<<i<<" : ";
  456. 			cout<<ans<<'\n';
  457. 		}
  458. 		else if(c=='C')
  459. 		{
  460. 			int l,r,t1,t2;
  461. 			cin>>l>>r>>t1>>t2; //copy t1 into t2
  462. 			copy(l,r,t1,t2);
  463. 		}
  464. 		else if(c=='M')
  465. 		{
  466. 			int l,r,t; unsigned int p1,p2;
  467. 			cin>>l>>r>>t>>p1>>p2; //*p1 + p2 for all [l, r] in t
  468. 			modify(l,r,t,p1,p2);
  469. 		}
  470. 		else if(c=='A')
  471. 		{
  472. 			int l,r,t1,t2;
  473. 			cin>>l>>r>>t1>>t2; //t1*p into t2
  474. 			unsigned int p;
  475. 			cin>>p;
  476. 			advmodify(l,r,t1,t2,p);
  477. 		}
  478. 		else
  479. 		{
  480. 			int l,r,t1,t2;
  481. 			cin>>l>>r>>t1>>t2; //swap t1 and t2
  482. 			swap(l,r,t1,t2);
  483. 		}
  484. 		if(int(vec.size())>=BL) recalc(w);
  485. 	}
  486. }
  487.  
Success #stdin #stdout 0s 16416KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/kN5jxN
language:
C++14 (gcc 8.3)
created:
7 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!