fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const long long inf = 1e15 + 5;
  4. const int N = 1e5 + 5;
  5. int n, q;
  6. long long a[N];
  7. set<int> rp[N], lp[N];
  8. namespace ST {
  9. 	pair<int, int> t[N << 2];
  10. 	int lazy[N << 2];
  11. 	inline pair<int, int> operator+(const pair<int, int> &lhs, const pair<int, int> &rhs) {
  12. 		if (lhs.first != rhs.first) return min(lhs, rhs);
  13. 		return {lhs.first, lhs.second + rhs.second}; 
  14. 	}
  15. 	inline void push_up(int p) {
  16. 		t[p] = t[p << 1] + t[p << 1 | 1];
  17. 	}
  18. 	inline void tag(int p, int x) {
  19. 		t[p].first += x;
  20. 		lazy[p] += x;
  21. 	}
  22. 	inline void push_down(int p) {
  23. 		if (lazy[p]) {
  24. 			tag(p << 1, lazy[p]);
  25. 			tag(p << 1 | 1, lazy[p]);
  26. 			lazy[p] = 0;
  27. 		}
  28. 	}
  29. 	void build(int p, int l, int r) {
  30. 		t[p].second = r - l + 1;
  31. 		if (l == r) return;
  32. 		int mid = (l + r) >> 1;
  33. 		build(p << 1, l, mid);
  34. 		build(p << 1 | 1, mid + 1, r);
  35. 	}
  36. 	void modify(int p, int l, int r, int ll, int rr, int x) {
  37. 		if (l >= ll && r <= rr) {
  38. 			tag(p, x);
  39. 			return;
  40. 		}
  41. 		push_down(p);
  42. 		int mid = (l + r) >> 1;
  43. 		if (mid >= ll) modify(p << 1, l, mid, ll, rr, x);
  44. 		if (mid < rr) modify(p << 1 | 1, mid + 1, r, ll, rr, x);
  45. 		push_up(p);
  46. 	}
  47. 	pair<int, int> query(int p, int l, int r, int ll, int rr) {
  48. 		if (l >= ll && r <= rr) return t[p];
  49. 		push_down(p);
  50. 		int mid = (l + r) >> 1;
  51. 		if (mid >= ll && mid < rr) return query(p << 1, l, mid, ll, rr) + query(p << 1 | 1, mid + 1, r, ll, rr);
  52. 		if (mid >= ll) return query(p << 1, l, mid, ll, rr);
  53. 		return query(p << 1 | 1, mid + 1, r, ll, rr); 
  54. 	}
  55. }
  56. namespace BIT {
  57. 	long long c[N];
  58. 	inline void modify(int p, long long x) {
  59. 		for (; p <= n; p += p & -p)
  60. 			c[p] += x;
  61. 	}
  62. 	inline long long query(int p) {
  63. 		long long res = 0;
  64. 		for (; p; p -= p & -p)
  65. 			res += c[p];
  66. 		return res;
  67. 	}
  68. 	inline long long query(int l, int r) {
  69. 		return query(r) - query(l - 1);
  70. 	}
  71. }
  72. namespace ST1 {
  73. 	long long val[N << 2], lazy[N << 2];
  74. 	inline void push_up(int p) {
  75. 		val[p] = min(val[p << 1], val[p << 1 | 1]);
  76. 	}
  77. 	inline void tag(int p, long long x) {
  78. 		val[p] += x;
  79. 		lazy[p] += x;
  80. 	}
  81. 	inline void push_down(int p) {
  82. 		if (lazy[p]) {
  83. 			tag(p << 1, lazy[p]);
  84. 			tag(p << 1 | 1, lazy[p]);
  85. 			lazy[p] = 0;
  86. 		}
  87. 	}
  88. 	void modify(int p, int l, int r, int ll, int rr, long long x) {
  89. 		if (l >= ll && r <= rr) {
  90. 			tag(p, x);
  91. 			return;
  92. 		}
  93. 		push_down(p);
  94. 		int mid = (l + r) >> 1;
  95. 		if (mid >= ll) modify(p << 1, l, mid, ll, rr, x);
  96. 		if (mid < rr) modify(p << 1 | 1, mid + 1, r, ll, rr, x);
  97. 		push_up(p);
  98. 	}
  99. 	long long find_l(int p, int l, int r, int pos, long long x) {
  100. 		if (val[p] >= x) return -1;
  101. 		if (l == r) return l;
  102. 		push_down(p);
  103. 		int mid = (l + r) >> 1;
  104. 		if (pos <= mid) return find_l(p << 1, l, mid, pos, x);
  105. 		int res = find_l(p << 1 | 1, mid + 1, r, pos, x);
  106. 		return ~res ? res : find_l(p << 1, l, mid, pos, x); 
  107. 	}
  108. 	long long find_r(int p, int l, int r, int pos, long long x) {
  109. 		if (val[p] >= x) return -1;
  110. 		if (l == r) return l;
  111. 		push_down(p);
  112. 		int mid = (l + r) >> 1;
  113. 		if (pos > mid) return find_r(p << 1 | 1, mid + 1, r, pos, x);
  114. 		int res = find_r(p << 1, l, mid, pos, x);
  115. 		return ~res ? res : find_r(p << 1 | 1, mid + 1, r, pos, x);
  116. 	}
  117. }
  118. namespace ST2 {
  119. 	long long val[N << 2], lazy[N << 2];
  120. 	inline void push_up(int p) {
  121. 		val[p] = max(val[p << 1], val[p << 1 | 1]);
  122. 	}
  123. 	inline void tag(int p, long long x) {
  124. 		val[p] += x;
  125. 		lazy[p] += x;
  126. 	}
  127. 	inline void push_down(int p) {
  128. 		if (lazy[p]) {
  129. 			tag(p << 1, lazy[p]);
  130. 			tag(p << 1 | 1, lazy[p]);
  131. 			lazy[p] = 0;
  132. 		}
  133. 	}
  134. 	void modify(int p, int l, int r, int ll, int rr, long long x) {
  135. 		if (l >= ll && r <= rr) {
  136. 			tag(p, x);
  137. 			return;
  138. 		}
  139. 		push_down(p);
  140. 		int mid = (l + r) >> 1;
  141. 		if (mid >= ll) modify(p << 1, l, mid, ll, rr, x);
  142. 		if (mid < rr) modify(p << 1 | 1, mid + 1, r, ll, rr, x);
  143. 		push_up(p);
  144. 	}
  145. 	long long find_l(int p, int l, int r, int pos, long long x) {
  146. 		if (val[p] <= x) return -1;
  147. 		if (l == r) return l;
  148. 		push_down(p);
  149. 		int mid = (l + r) >> 1;
  150. 		if (pos <= mid) return find_l(p << 1, l, mid, pos, x);
  151. 		int res = find_l(p << 1 | 1, mid + 1, r, pos, x);
  152. 		return ~res ? res : find_l(p << 1, l, mid, pos, x); 
  153. 	}
  154. 	long long find_r(int p, int l, int r, int pos, long long x) {
  155. 		if (val[p] <= x) return -1;
  156. 		if (l == r) return l;
  157. 		push_down(p);
  158. 		int mid = (l + r) >> 1;
  159. 		if (pos > mid) return find_r(p << 1 | 1, mid + 1, r, pos, x);
  160. 		int res = find_r(p << 1, l, mid, pos, x);
  161. 		return ~res ? res : find_r(p << 1 | 1, mid + 1, r, pos, x);
  162. 	}
  163. }
  164. inline bool judge(int l, int r) {
  165. 	if (r - l <= 1) return false;
  166. 	return BIT::query(l + 1, r - 1) < min(a[l], a[r]);
  167. }
  168. void modify_seg(int l, int r, int x) {
  169. 	ST::modify(1, 1, n, l + 1, r - 1, x);
  170. 	if (x == 1) {
  171. 		lp[l].insert(r);
  172. 		rp[r].insert(l);
  173. 	} else {
  174. 		lp[l].erase(r);
  175. 		rp[r].erase(l);
  176. 	} 
  177. }
  178. int find_r(int l, int r) {
  179. 	return ST1::find_r(1, 0, n + 1, r + 1, BIT::query(l));
  180. }
  181. int find_l(int l, int r) {
  182. 	return ST2::find_l(1, 0, n + 1, l - 1, BIT::query(r - 1));
  183. }
  184. void check(int pos, int x) {
  185. 	int l = pos - 1, r = pos + 1;
  186. 	while (true) {
  187. 		if (judge(l, r)) modify_seg(l, r, x);
  188. 		if (l == 0 && r == n + 1) break;
  189. 		if (a[l] < a[r]) l = find_l(l, r);	
  190. 		else r = find_r(l, r);
  191. 	}
  192. }
  193. void modify(int pos, long long x) {
  194. 	check(pos, -1);
  195. 	BIT::modify(pos, x - a[pos]);
  196. 	ST1::modify(1, 0, n + 1, pos + 1, n + 1, x - a[pos]);
  197. 	ST1::modify(1, 0, n + 1, pos, pos, -(x - a[pos]));
  198. 	ST2::modify(1, 0, n + 1, pos, n + 1, x - a[pos]);
  199. 	ST2::modify(1, 0, n + 1, pos, pos, x - a[pos]);
  200. 	a[pos] = x;
  201. 	while (!rp[pos].empty()) {
  202. 		int l = *rp[pos].begin();
  203. 		modify_seg(l, pos, -1);
  204. 	}
  205. 	while (!lp[pos].empty()) {
  206. 		int r = *lp[pos].begin();
  207. 		modify_seg(pos, r, -1);
  208. 	}
  209. 	lp[pos].clear(), rp[pos].clear();
  210. 	int r = find_r(pos, pos + 1);
  211. 	while (true) {
  212. 		if (judge(pos, r)) modify_seg(pos, r, 1);
  213. 		if (r == n + 1) break;
  214. 		r = find_r(pos, r);
  215. 	} 
  216. 	int l = find_l(pos - 1, pos);
  217. 	while (true) {
  218. 		if (judge(l, pos)) modify_seg(l, pos, 1);
  219. 		if (l == 0) break;
  220. 		l = find_l(l, pos); 
  221. 	}
  222. 	check(pos, 1);
  223. }
  224. int main() {
  225. 	scanf("%d", &n);
  226. 	ST::build(1, 1, n);
  227. 	a[0] = a[n + 1] = inf;
  228. 	ST1::modify(1, 0, n + 1, n + 1, n + 1, -inf);
  229. 	ST2::modify(1, 0, n + 1, 0, 0, inf);
  230. 	modify_seg(0, n + 1, 1);
  231. 	long long tmp;
  232. 	for (int i = 1; i <= n; ++i)
  233. 		scanf("%lld", &tmp), modify(i, tmp);
  234. 	scanf("%d", &q);
  235. 	while (q--) {
  236. 		int op, x, y;
  237. 		scanf("%d%d%d", &op, &x, &y);
  238. 		if (op == 1) {
  239. 			modify(x, y);
  240. 		} else {
  241. 			int l = ST1::find_l(1, 0, n + 1, y, BIT::query(x - 1));
  242. 			int r = ST2::find_r(1, 0, n + 1, x, BIT::query(y));
  243. 			printf("%d\n", ST::query(1, 1, n, l, r).second);
  244. 		}
  245. 	}
  246. 	return 0;
  247. }
Runtime error #stdin #stdout 0.01s 16724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bMwh1L
language:
C++14 (gcc 8.3)
created:
2 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!