给定一个长度为 $n$ 的排列，定义一个区间$(l,r)$是好的当且仅当其满足 $\max - \min = r - l$ 。有 $Q$ 次询问，每次询问一个区间内有多少个子区间是好的。
$n, Q\leq 1.2\times 10^5$
题解给的分治加莫队做法没怎么看懂，复杂度是 $\mathcal{O(n \sqrt n \log n)}$ 的。搜了一下发现有 $\mathcal{O(n\log n)}$ 的做法，就去学习了一下。
思路还是类似的，首先考虑当只有一个询问时怎么做。有一种分治做法，这里不再细说，很多地方都出过，我们考虑线段树扫描线的做法。
我们枚举一个左端点$l$，统计所有合法的右端点。类似于这一道题，我们定义一个右端点$r$的权值为 $\max - \min - (r - l)$，显然，任何时候一个点的权值不会小于 $-1$，且一个右端点合法当且仅当其权值为 $-1$。
那么我们直接对于线段树，统计一下其中的最小值和最小值出现的次数，若最小值为 $-1$ 则计入答案。
发现我们每次向左移动一次左端点时，会改变若干个区间的 $\max,\min$，以及其长度。但是容易发现所有的修改数量是 $\mathcal{O(n)}$ 级别的。
然后考虑对于任意区间时怎么处理，我们考虑如果可以记录每个区间的历史贡献和，那么答案也是容易计算的。将询问离线后单次区间查询即可。考虑如何记录区间的历史贡献，我们对于线段树每个节点，维护区间最小值，最小值出现次数，总贡献以及当前的最小值出现次数作为历史合法答案贡献了几次，当一个标记传下来时，因为我们保证了区间最小值不会超过 $-1$，所以直接合并标记即可。值得注意的时候，最后一个标记下传时，需要满足其最小值是作为父亲线段中最小值出现的。
复杂度 $O((n + q)\log n)$
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define up(i,j,n) for (int i = j; i <= n; i++)
#define down(i,j,n) for (int i = j; i >= n; i--)
#define cadd(a,b) a = add (a, b)
#define cpop(a,b) a = pop (a, b)
#define cmul(a,b) a = mul (a, b)
#define pr pair<int, int>
#define fi first
#define se second
#define SZ(x) (int)x.size()
#define bin(i) (1 << (i))
#define Auto(i,node) for (int i = LINK[node]; i; i = e[i].next)
template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
template<typename T> inline T dmax(T x, T y){return x > y ? x : y;}
template<typename T> inline T dmin(T x, T y){return x < y ? x : y;}
const int MAXN = 2e5 + 5;
const ll oo = 2e18;
struct Query {
int le, ri, o;
inline Query (int le = 0, int ri = 0, int o = 0) :
le(le), ri(ri), o(o) {}
inline bool operator < (const Query & w) const {
return le < w.le;
}
}qry[MAXN];
int N, Q, a[MAXN];
ll ans[MAXN];
struct tree {
int mn, cnt, tag, upd;
ll sum;
}t[MAXN << 2];
inline void rel(int k){
t[k].mn = dmin(t[k << 1].mn, t[k << 1 | 1].mn);
t[k].sum = t[k << 1].sum + t[k << 1 | 1].sum;
t[k].cnt = 0;
if (t[k << 1].mn == t[k].mn) t[k].cnt += t[k << 1].cnt;
if (t[k << 1 | 1].mn == t[k].mn) t[k].cnt += t[k << 1 | 1].cnt;
}
void cg(int k, int tag, int upd){
if (tag != 0) {
t[k].mn += tag;
t[k].tag += tag;
}
if (t[k].mn == t[k >> 1].mn || t[k].mn == 0) {
t[k].sum += (ll)t[k].cnt * upd;
t[k].upd += upd;
}
}
void Pushdown(int k){
cg(k << 1, t[k].tag, t[k].upd);
cg(k << 1 | 1, t[k].tag, t[k].upd);
t[k].tag = t[k].upd = 0;
}
void Build(int le, int ri, int k){
if (le == ri) {
t[k].mn = 1; t[k].cnt = 1;
return;
}
int mi = (le + ri) >> 1;
Build(le, mi, k << 1);
Build(mi + 1, ri, k << 1 | 1);
rel(k);
}
void cg(int le, int ri, int k, int L, int R, int tag, int upd){
if (le != ri) Pushdown(k);
if (L <= le && ri <= R) return cg(k, tag, upd);
int mi = (le + ri) >> 1;
if (L <= mi) cg(le, mi, k << 1, L, R, tag, upd);
if (mi + 1 <= R) cg(mi + 1, ri, k << 1 | 1, L, R, tag, upd);
rel(k);
}
ll get(int le, int ri, int k, int L, int R){
if (le != ri) Pushdown(k);
if (L <= le && ri <= R) return t[k].sum;
int mi = (le + ri) >> 1;
ll sum = 0;
if (L <= mi) sum += get(le, mi, k << 1, L, R);
if (mi + 1 <= R) sum += get(mi + 1, ri, k << 1 | 1, L, R);
return sum;
}
deque<int> q_mx, q_mn;
int main(){
#ifdef cydiater
freopen("input.in", "r", stdin);
#endif
scanf("%d", &N);
up (i, 1, N) scanf("%d", &a[i]);
scanf("%d", &Q);
up (i, 1, Q) {
int le, ri; scanf("%d%d", &le, &ri);
qry[i] = Query(le, ri, i);
}
sort(qry + 1, qry + Q + 1);
Build(1, N, 1);
int o = N + 1;
down (i, Q, 1) {
while (qry[i].le < o) {
o--;
while (!q_mx.empty() && a[o] > a[q_mx.back()]) {
int cl = q_mx.back(), cr;
q_mx.pop_back();
cr = q_mx.empty() ? N : (q_mx.back() - 1);
cg(1, N, 1, cl, cr, a[o] - a[cl], 0);
}
while (!q_mn.empty() && a[o] < a[q_mn.back()]) {
int cl = q_mn.back(), cr;
q_mn.pop_back();
cr = q_mn.empty() ? N : (q_mn.back() - 1);
cg(1, N, 1, cl, cr, a[cl] - a[o], 0);
}
cg(1, N, 1, o, N, -1, 0);
cg(1, N, 1, o, N, 0, 1);
q_mx.push_back(o);
q_mn.push_back(o);
}
ans[qry[i].o] = get(1, N, 1, qry[i].le, qry[i].ri);
}
up (i, 1, Q) printf("%lld\n", ans[i]);
return 0;
}