线段树加单调栈维护每个后缀的最小值的好题。

可以先做一下弱化版：CF526F Pudding Monsters，那道题是本题的基础。

由于这是个排列，因此好区间可以转化为满足 \(max – min = r – l\) 的区间。其中 \(max,min\) 分别表示区间最大值和最小值，\(l,r\) 分别表示区间左右端点。我们可以枚举 \(r\)，那么限制变为 \(max – min + l = r\)。又因为对于所有区间，都有 \(max – min >= r – l\)，所以好区间可以转化为“以 \(r\) 为右端点，且 \(max – min + l\) 最小左端点的个数”。

我们从左往右扫一遍，用单调栈和线段树维护最值，扫的时候顺便统计一下全局最小值个数，这就是前面那道题的做法。

对于这道题，我们可以离线，将询问挂到右端点，“子区间”转化为“前缀的后缀”。如果只考虑一个前缀的所有后缀的答案，这题只不过多限制左端点的范围，不能小于 \(L\)，这个好说，查全局最小值个数改为查区间最小值个数即可。再考虑所有前缀的贡献，这个可以直接在线段树上打“历史贡献”的标记，查询就把节点的“历史贡献”加和即可。

总结一下，我们需要一棵线段树，支持区间加，单点修改，区间查历史贡献。还需要俩单调栈，维护最大最小值，并在线段树上进行操作。

细节看代码吧。

\(Code:\)

  1. #define N 201000
  2. #define NN 801000
  3. #define int long long
  4. template <typename T> inline void read(T &x) {
  5. 	x = 0; char c = getchar(); bool flag = false;
  6. 	while (!isdigit(c)) { if (c == '-')	flag = true; c = getchar(); }
  7. 	while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
  8. 	if (flag)	x = -x;
  9. }
  10. using namespace std;
  11. const int inf = 987654321;
  12. int n;
  13. int h[N];
  14. struct edge{
  15. 	int nxt, to, id;
  16. }e[N];
  17. int head[N], ecnt;
  18. inline void addedge(int from, int to, int id) {//邻接表挂询问
  19. 	e[++ecnt] = (edge){head[from], to, id};
  20. 	head[from] = ecnt;
  21. }
  22. int ans[N];
  24. struct node {
  25. 	int mn, cnt;
  26. 	node(int mnn = inf, int cntt = 0) { mn = mnn, cnt = cntt; }
  27. 	node operator +(const node a) const {
  28. 		return node(min(mn, a.mn), mn == a.mn ? cnt + a.cnt : (mn < a.mn ? cnt : a.cnt));
  29. 	}
  30. }nd[NN];
  31. int ls[NN], rs[NN], atag[NN], ctag[NN], res[NN], root, ttot;
  32. void build(int L, int R, int &cur) {
  33. 	cur = ++ttot;
  34. 	if (L == R)	return ;
  35. 	int mid = (L + R) >> 1;
  36. 	build(L, mid, ls[cur]);
  37. 	build(mid + 1, R, rs[cur]);
  38. }
  39. inline void pushup(int cur) {
  40. 	nd[cur] = nd[ls[cur]] + nd[rs[cur]];
  41. }
  42. inline void pusha(int cur, int v) {//打加法标记
  43. 	if (!cur)	return ;
  44. 	nd[cur].mn += v;
  45. 	atag[cur] += v;
  46. }
  47. inline void pushc(int cur, int mn, int c) {//打历史标记
  48. 	if (!cur || nd[cur].mn != mn)	return ;
  49.     //只有儿子最小值和父亲相同时才能继承贡献
  50. 	res[cur] += nd[cur].cnt * c;
  51. 	ctag[cur] += c;
  52. }
  53. inline void pushdown(int cur) {//下放标记。注意顺序
  54. 	if (atag[cur])
  55. 		pusha(ls[cur], atag[cur]), pusha(rs[cur], atag[cur]), atag[cur] = 0;
  56. 	if (ctag[cur])
  57. 		pushc(ls[cur], nd[cur].mn, ctag[cur]), 
  58. 		pushc(rs[cur], nd[cur].mn, ctag[cur]), 
  59. 		ctag[cur] = 0;
  60. }
  61. void modify(int L, int R, int l, int r, int v, int cur) {//区间加
  62. 	if (l <= L && R <= r) {
  63. 		pusha(cur, v);
  64. 		return ;
  65. 	}
  66. 	pushdown(cur);
  67. 	int mid = (L + R) >> 1;
  68. 	if (l <= mid)	modify(L, mid, l, r, v, ls[cur]);
  69. 	if (r > mid)	modify(mid + 1, R, l, r, v, rs[cur]);
  70. 	pushup(cur);
  71. }
  72. void modify(int L, int R, int pos, int v, int cur) {//单点修改
  73. 	if (L == R)	return nd[cur] = (node){v, 1}, void();
  74. 	pushdown(cur);
  75. 	int mid = (L + R) >> 1;
  76. 	if (pos <= mid)	modify(L, mid, pos, v, ls[cur]);
  77. 	else	modify(mid + 1, R, pos, v, rs[cur]);
  78. 	pushup(cur);
  79. }
  80. int query(int L, int R, int l, int r, int cur) {
  81. 	if (l <= L && R <= r)	return res[cur];
  82. 	pushdown(cur);
  83. 	int mid = (L + R) >> 1, tmp = 0;
  84. 	if (l <= mid)	tmp = query(L, mid, l, r, ls[cur]);
  85. 	if (r > mid)	tmp += query(mid + 1, R, l, r, rs[cur]);
  86. 	return tmp;
  87. }
  89. struct Seg {//单调栈
  90. 	int l, r, v;//l ~ r 的最值都是 v
  91. 	Seg(int ll = 0, int rr = 0, int vv = 0) { l = ll, r = rr, v = vv; }
  92. 	bool operator <(const Seg a) const {
  93. 		return v < a.v;
  94. 	}
  95. 	bool operator >(const Seg a) const {
  96. 		return v > a.v;
  97. 	}
  98. }smx[N], smn[N];
  99. int mxtop, mntop;
  101. signed main() {
  102. 	read(n);
  103. 	for (register int i = 1; i <= n; ++i)	read(h[i]);
  104. 	int q; read(q);
  105. 	for (register int i = 1; i <= q; ++i) {
  106. 		int l, r; read(l), read(r);
  107. 		addedge(r, l, i);
  108. 	}
  109. 	build(1, n, root);
  110. 	for (register int i = 1; i <= n; ++i) {
  111.     	//维护最值
  112. 		Seg s(i, i, h[i]);
  113. 		while (mxtop && s > smx[mxtop])
  114. 			modify(1, n, smx[mxtop].l, smx[mxtop].r, h[i] - smx[mxtop].v, root),
  115. 			s.l = smx[mxtop].l, --mxtop;
  116. 		smx[++mxtop] = s;
  117. 		
  118. 		s = Seg(i, i, h[i]);
  119. 		while (mntop && s < smn[mntop])
  120. 			modify(1, n, smn[mntop].l, smn[mntop].r, -h[i] + smn[mntop].v, root),
  121. 			s.l = smn[mntop].l, --mntop;
  122. 		smn[++mntop] = s;
  123. 		
  124. 		modify(1, n, i, i, root);//插入新点
  125. 		
  126. 		pushc(root, i, 1);//将当前的合法区间计入贡献
  127. 		for (register int j = head[i]; j; j = e[j].nxt) {
  128. 			int l = e[j].to, id = e[j].id;
  129. 			ans[id] = query(1, n, l, i, root);
  130. 		}
  131. 	}
  132. 	for (register int i = 1; i <= q; ++i)
  133. 		printf("%lld\n", ans[i]);
  134. 	return 0;
  135. }

版权声明：本文为JiaZP原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/JiaZP/p/13381983.html