fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define fi first
  5. #define se second
  6.  
  7. const int maxN=1e3+5;
  8. struct ez 
  9. {
  10. 	int sum, mn, mx;
  11. };
  12. int n, m, q, a[maxN][maxN]; 
  13. ez segtree[4*maxN][4*maxN];
  14.  
  15. ez merge_segtree(ez l, ez r)
  16. {
  17. 	ez res;
  18. 	res.sum=l.sum+r.sum;
  19. 	res.mn=min(l.mn, r.mn);
  20. 	res.mx=max(l.mx, r.mx);
  21. 	return res;
  22. }
  23.  
  24. void build_y(int nodex, int lx, int rx, int nodey, int ly, int ry)
  25. {
  26. 	if(ly==ry)
  27. 	{
  28. 		if(lx==rx) segtree[nodex][nodey].mn=segtree[nodex][nodey].sum=segtree[nodex][nodey].mx=a[lx][ly];
  29. 		else segtree[nodex][nodey]=merge_segtree(segtree[nodex*2][nodey],segtree[nodex*2+1][nodey]);
  30. 	}
  31. 	else
  32. 	{
  33. 		int midy=(ly+ry)>>1;
  34. 		build_y(nodex, lx, rx, nodey*2, ly, midy);
  35. 		build_y(nodex, lx, rx, nodey*2+1, midy+1, ry);
  36. 		segtree[nodex][nodey]=merge_segtree(segtree[nodex][nodey*2],segtree[nodex][nodey*2+1]);
  37. 	}
  38. }
  39.  
  40. void build_x(int nodex, int lx, int rx)
  41. {
  42. 	if(lx!=rx)
  43. 	{
  44. 		int midx=(lx+rx)>>1;
  45. 		build_x(nodex*2, lx, midx);
  46. 		build_x(nodex*2+1, midx+1, rx);
  47. 	}
  48. 	build_y(nodex, lx, rx, 1, 1, m);
  49. }
  50.  
  51. void update_y(int nodex, int lx, int rx, int nodey, int ly, int ry, int x, int y, int val)
  52. {
  53. 	if(ly==ry)
  54. 	{
  55. 		if(lx==rx) segtree[nodex][nodey].mn=segtree[nodex][nodey].sum=segtree[nodex][nodey].mx=val;
  56. 		else segtree[nodex][nodey]=merge_segtree(segtree[nodex*2][nodey],segtree[nodex*2+1][nodey]);
  57. 	}
  58. 	else
  59. 	{
  60. 		int midy=(ly+ry)>>1;
  61. 		if(y<=midy) update_y(nodex, lx, rx, nodey*2, ly, midy, x, y, val);
  62. 		else update_y(nodex, lx, rx, nodey*2+1, midy+1, ry, x, y, val);
  63. 		segtree[nodex][nodey]=merge_segtree(segtree[nodex][nodey*2],segtree[nodex][nodey*2+1]);
  64. 	}
  65. }
  66.  
  67. void update_x(int nodex, int lx, int rx, int x, int y, int val)
  68. {
  69. 	if(lx!=rx)
  70. 	{
  71. 		int midx=(lx+rx)>>1;
  72. 		if(x<=midx) update_x(nodex*2, lx, midx, x, y, val);
  73. 		else update_x(nodex*2+1, midx+1, rx, x, y, val);
  74. 	}
  75. 	update_y(nodex, lx, rx, 1, 1, m, x, y, val);
  76. }
  77.  
  78. ez get_y(int nodex, int nodey, int tl_y, int tr_y, int ly, int ry)
  79. {
  80. 	if(ly>ry) return {0,(int)1e18,(int)-1e18};
  81. 	if(tl_y==ly && tr_y==ry) return segtree[nodex][nodey];
  82. 	int tmid_y=(tl_y+tr_y)>>1;
  83. 	return merge_segtree(get_y(nodex, nodey*2, tl_y, tmid_y, ly, min(tmid_y, ry)),
  84. 	get_y(nodex, nodey*2+1, tmid_y+1, tr_y, max(ly, tmid_y+1), ry));
  85. }
  86.  
  87. ez get_x(int nodex, int tlx, int trx, int lx, int rx, int ly, int ry)
  88. {
  89. 	if(lx>rx) return {0,(int)1e18,(int)-1e18};
  90. 	if(lx==tlx && rx==trx) return get_y(nodex, 1, 1, m, ly, ry);
  91. 	int tmidx=(tlx+trx)>>1;
  92. 	return merge_segtree(get_x(nodex*2, tlx, tmidx, lx, min(rx,tmidx), ly, ry),
  93. 	get_x(nodex*2+1, tmidx+1, trx, max(lx, tmidx+1), rx, ly, ry));
  94. }
  95.  
  96.  
  97. void solve()
  98. {
  99. 	build_x(1,1,n);
  100. 	while(q--)
  101. 	{
  102. 		int type; cin>>type;
  103. 		if(type==1)
  104. 		{
  105. 			int l,r,x; cin>>l>>r>>x;
  106. 			update_x(1,1,n,l,r,x);
  107. 		}
  108. 		else
  109. 		{
  110. 			int lx,rx,ly,ry; cin>>lx>>ly>>rx>>ry;
  111. 			if(type==2) cout<<get_x(1,1,n,lx,rx,ly,ry).sum<<'\n';
  112. 			if(type==3) cout<<get_x(1,1,n,lx,rx,ly,ry).mx<<'\n';
  113. 			if(type==4) cout<<get_x(1,1,n,lx,rx,ly,ry).mn<<'\n';
  114. 		}
  115. 	}
  116. }
  117.  
  118. int32_t main()
  119. {
  120. 	cin>>n>>m>>q;
  121. 	for(int i=1; i<=n; i+=1)
  122. 	{
  123. 		for(int j=1; j<=m; j+=1)
  124. 		{
  125. 			cin>>a[i][j];
  126. 		}
  127. 	}
  128. 	solve();
  129. }
Success #stdin #stdout 0.01s 7664KB
comments (?)
stdin
copy 
4 4 4
4 4 2 3
4 3 1 3
2 1 4 2
2 4 2 3
4 1 3 1 3
2 4 3 4 4
4 4 1 4 4
1 4 4 4
stdout
copy 
2
5
2
https://ideone.com/mykKgO
language:
C++14 (gcc 8.3)
created:
10 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!