fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define lowbit(x) (x & (-x))
  3. using namespace std;
  4. long long n, m;
  5. long long ba[100010];
  6. struct BIT
  7. {
  8.     vector<long long> val,a1,a2;
  9.     void init()
  10.     {
  11.     	val.resize(n + 10);
  12.     	a1.resize(n + 10);
  13.     	a2.resize(n + 10);
  14.     }
  15.     void update(long long pos,long long k) {
  16.         for(long long i = pos;i <= n + 5;i += lowbit(i)) {
  17.             a1[i] += k;
  18.             a2[i] += k * pos;
  19.         }
  20.     }
  21.     long long query(long long pos) {
  22.         long long res = 0;
  23.         for(long long i = pos;i > 0;i -= lowbit(i)) res += (pos + 1) * a1[i] - a2[i];
  24.         return res;
  25.     }
  26.     void bulid(){for(long long i = 1;i <= n + 5;++i) update(i,val[i] - val[i - 1]);}
  27.     void reg_add(long long l,long long r,long long k){update(l,k);update(r + 1,-k);}
  28.     long long reg_sum(long long l,long long r){return query(r) - query(l - 1);}
  29. } wlx;
  30. struct operate
  31. {
  32. 	char opt;
  33. 	int l, r, c;
  34. 	int x, y, b;
  35. };
  36. operate a[200010];
  37. long long ans[100010];
  38. void work(long long ld, long long rd, vector <long long> &now)
  39. {
  40. 	if (now.empty()) return ;
  41. 	if (ld == rd) {for (auto x : now) ans[x] = ld; return ;}
  42. 	long long mid = (ld + rd) >> 1;
  43. 	vector <long long> left, right;
  44. 	for (auto x : now)
  45. 		if (a[x].opt == 'C')
  46. 		{
  47. 			if (a[x].y > mid) {wlx.reg_add(a[x].x, a[x].x, 1); right.push_back(x);}
  48. 			else left.push_back(x);
  49. 		}
  50. 		else if (a[x].opt == 'T')
  51. 		{
  52. 			if (a[x].y > mid) {wlx.reg_add(a[x].x, a[x].x, -1); right.push_back(x);}
  53. 			else left.push_back(x);
  54. 		}
  55. 		else
  56. 		{
  57. 			long long num = wlx.reg_sum(a[x].l, a[x].r);
  58. 			if (a[x].c > num) {a[x].c -= num; left.push_back(x);}
  59. 			else right.push_back(x);
  60. 		}
  61. 	for (auto x : now)
  62. 		if (a[x].opt == 'C')
  63. 		{
  64. 			if (a[x].y > mid) wlx.reg_add(a[x].x, a[x].x, -1); 
  65. 		}
  66. 		else if (a[x].opt == 'T')
  67. 		{
  68. 			if (a[x].y > mid) wlx.reg_add(a[x].x, a[x].x, 1); 
  69. 		}
  70. 	work(mid + 1, rd, right);
  71. 	work(ld, mid, left);
  72. }
  73. int main()
  74. {
  75. 	cin >> n >> m;
  76. 	for (int i = 1; i <= n; i++)
  77. 	{
  78. 		cin >> ba[i];
  79. 		a[i].opt = 'C';
  80. 		a[i].x = i;
  81. 		a[i].b = -1;
  82. 		a[i].y = ba[i];
  83. 	}
  84. 	wlx.init();
  85. 	int cnt = n;
  86. 	for (long long i = 1; i <= m; i++)
  87. 	{
  88. 		cnt++;
  89. 		cin >> a[cnt].opt;
  90. 		if (a[cnt].opt == 'Q')
  91. 		{
  92. 			cin >> a[cnt].l >> a[cnt].r >> a[cnt].c;
  93. 			a[cnt].c *= -1;
  94. 			a[cnt].c += -a[cnt].l + a[cnt].r + 2;
  95. 		}
  96. 		else
  97. 		{
  98. 			cin >> a[cnt].x >> a[cnt].y;
  99. 			a[cnt].b = ba[a[cnt].x];
  100. 			ba[a[cnt].x] = a[cnt].y;
  101. 			cnt++;
  102. 			a[cnt].opt = 'T';
  103. 			a[cnt].x = a[cnt - 1].x;
  104. 			a[cnt].y = a[cnt - 1].b;
  105. 		}
  106. 	}
  107. 	vector <long long> all;
  108. 	for (long long i = 1; i <= cnt; i++) all.push_back(i);
  109. 	work(0, 1000000000, all);
  110. 	for (long long i = 1; i <= cnt; i++) if (a[i].opt == 'Q') cout << ans[i] << endl;
  111. 	return 0;
  112. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
stdout
copy 
3
6
https://ideone.com/TAvjZK
language:
C++14 (gcc 8.3)
created:
4 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!