CF997E Good Subsegments

简单题，不知道为啥和弱化版一个 Difficulty。

考虑弱化怎么做。

区间 \([l,r]\) 中的数是连续的，当且仅当区间最大值 \(\max\) 减去区间最小值 \(\min\) 为 \(r-l\)，即 \(\max-\min=r-l\)。

考虑扫描线，固定右端点 \(r\)，统计每个左端点的贡献。

由于 \(S(l,r)=\text{max}-\text{min}+l-r\ge 0\)，考虑维护每个 \(l\) 的 \(S\) 值。有贡献的左端点即 \(S(l)=0\)，线段树维护区间最小值的个数即可。

考虑右端点 \(r\) 移动，然后这个 \(\max\) 和 \(\min\) 可以用两个单调栈维护，动态修改 \(S\) 值，这很经典。然后你会弱化版了。

回到这题，还是考虑扫描线，但是固定右端点 \(r\) 的时候，可能可以贡献到 \(q_r\in[r,n]\) 的询问，不太好做。

可以再维护一个标记 \(tm\)，表示当前区间左端点应该向答案贡献多少次；由这个标记可以计算出当前区间的所有左端点对答案的历史贡献总和 \(sum\)。

注意到修改最小值时下放了 \(tm\) 标记，所以每次标记下放 \(tm\) 时对应的最小值一定是原来的最小值。

注意到有贡献的 \(r\) 在 \([ql,qr]\) 之间，贡献的 \(l\le r\)，所以取 \([ql,qr]\) 左端点的历史贡献总和即可。

复杂度还是 \(O(n\log n)\)。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

namespace vbzIO {
	char ibuf[(1 << 20) + 1], *iS, *iT;
	#if ONLINE_JUDGE
	#define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
	#else
	#define gh() getchar()
	#endif
	#define rd read
	#define wr write
	#define pc putchar
	#define pi pair<int, int>
	#define mp make_pair
	#define fi first
	#define se second
	#define pb push_back
	#define ins insert
	#define era erase
	inline int read () {
		char ch = gh();
		int x = 0;
		bool t = 0;
		while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
		return t ? ~(x - 1) : x;
	}
	inline void write(ll x) {
		if (x < 0) {
			x = ~(x - 1);
			putchar('-');
		}
		if (x > 9)
			write(x / 10);
		putchar(x % 10 + '0');
	}
}
using vbzIO::read;
using vbzIO::write;

const int inf = 1e9;
const int N = 3e5 + 300;
struct seg { int mn, ct, tg, tm; ll sum; seg () { mn = inf; } } tr[N << 2];
int n, m, a[N], tp[2], st[N][2];
vector<pi> q[N];
ll ans[N];

#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
void pushup(int x) {
	if (tr[ls].mn == tr[rs].mn) tr[x].mn = tr[ls].mn, tr[x].ct = tr[ls].ct + tr[rs].ct;
	else if (tr[ls].mn < tr[rs].mn) tr[x].mn = tr[ls].mn, tr[x].ct = tr[ls].ct;
	else tr[x].mn = tr[rs].mn, tr[x].ct = tr[rs].ct;
	tr[x].sum = tr[ls].sum + tr[rs].sum;
}

void pushtg(int x, int c) { tr[x].mn += c, tr[x].tg += c; }
void pushtm(int x, int c) { tr[x].sum += 1ll * tr[x].ct * c, tr[x].tm += c; }
void pushdown(int x) {
	if (tr[x].tg) {
		pushtg(ls, tr[x].tg), pushtg(rs, tr[x].tg);
		tr[x].tg = 0;
	}
	if (tr[x].tm) {
		if (tr[ls].mn == tr[x].mn) pushtm(ls, tr[x].tm);
		if (tr[rs].mn == tr[x].mn) pushtm(rs, tr[x].tm);
		tr[x].tm = 0;
	}
}

void upd(int l, int r, int p, int x) {
	if (l == r) return tr[x].mn = 0, tr[x].ct = 1, void();
	pushdown(x);
	if (p <= mid) upd(l, mid, p, ls);
	else upd(mid + 1, r, p, rs);
	pushup(x);
}

void add(int l, int r, int s, int t, int c, int x) {
	if (t < s) return;
	if (s <= l && r <= t) return pushtg(x, c);
	pushdown(x);
	if (s <= mid) add(l, mid, s, t, c, ls);
	if (t > mid) add(mid + 1, r, s, t, c, rs);
	pushup(x);
}

void ins(int l, int r, int s, int t, int c, int x) {
	if (t < s) return;
	if (s <= l && r <= t) return pushtm(x, c);
	pushdown(x);
	if (s <= mid) ins(l, mid, s, t, c, ls);
	if (t > mid) ins(mid + 1, r, s, t, c, rs);
	pushup(x);
}

ll qry(int l, int r, int s, int t, int x) {
	if (s <= l && r <= t) return tr[x].sum;
	pushdown(x);
	ll res = 0;
	if (s <= mid) res += qry(l, mid, s, t, ls);
	if (t > mid) res += qry(mid + 1, r, s, t, rs);
	return res;
}

int main() {
	n = rd();
	for (int i = 1, x, y; i <= n; i++) a[i] = rd();
	m = rd();
	for (int i = 1, l, r; i <= m; i++) 
		l = rd(), r = rd(), q[r].pb(mp(l, i));
	for (int i = 1; i <= n; i++) {
		while (tp[0] && a[st[tp[0]][0]] < a[i]) 
			add(1, n, st[tp[0] - 1][0] + 1, st[tp[0]][0], a[i] - a[st[tp[0]][0]], 1), tp[0]--;
		while (tp[1] && a[st[tp[1]][1]] > a[i])
			add(1, n, st[tp[1] - 1][1] + 1, st[tp[1]][1], a[st[tp[1]][1]] - a[i], 1), tp[1]--;
		st[++tp[0]][0] = st[++tp[1]][1] = i;
		add(1, n, 1, i - 1, -1, 1), upd(1, n, i, 1), pushtm(1, 1);
		for (pi p : q[i]) ans[p.se] = qry(1, n, p.fi, i, 1);
	}
	for (int i = 1; i <= m; i++) 
		wr(ans[i]), puts("");
	return 0;
}