Description
给你一个长度为n的排列P，定义一段子区间是好的，当且仅当这个子区间内的值构成了连续的一段。例如对于排列({1,3,2})，([1,1],[2,2],[3,3],[2,3],[1,3])是好的区间。
共q次询问，每次询问L,R 求有多少(L leq l leq rleq R)，满足([l,r])是好的区间。(1≤n,q≤1.2×10^5).
Solution
可以发现，区间([l,r])是好的，当且仅当$ (Max - Min)=(r−l) $，考虑维护一段区间上式的最小值。
考虑固定右端点时，子区间的个数。每一个最小值为0的位置都可以和当前的r组成一个好的区间。
不难发现，一个右端点能产生的贡献为它左边的点的最小值为0的个数，于是可以在线段树上维护最小值和最小值个数，以及每个最小值为0的位置产生的贡献。
由于右边新加的点会对已有的点产生影响，考虑离线询问，按右端点排序，用两个单调栈分别维护当前Min和Max。右端点右移时，整个区间的值都会减一，又因为处理子区间，所以当右端点右移时我们必须统计当前的答案，也就是历史最小值个数。时间复杂度(O(n imes log_2^n))
在下传标记时，因为之前的统计标记还未下传到当前点，所以我们不能判断当(Min_{root} == 0)时才计算贡献，而是当$ Min_{fa[root]} == Min_{root} $时才统计。 因为当前节点一旦被打了标记就代表出现过了最小值为0的情况。
这里我们可以总结出一个套路，就是当我们要统计一个节点的所有子区间的答案时，可以先行离线从小到大统计固定右端点的答案，然后移动右端点时再统计历史值。
Code
#include<bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for(int i = (j), i##_end_ = (k); i <= i##_end_; ++i)
#define drep(i, j, k) for(int i = (j), i##_end_ = (k); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(s, ...) fprintf(stderr, s, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
char ch = getchar();
int x = 0, flag = 1;
for(;!isdigit(ch); ch = getchar()) if(ch == '-') flag *= -1;
for(;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
return x * flag;
}
void write(LL x) {
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar(x % 10 + 48);
}
#define Maxn 120009
struct Quer {
int l, id;
};
vector <Quer> s[Maxn];
int n, a[Maxn], q, stk1[Maxn], stk2[Maxn], top1, top2;
LL ans[Maxn];
namespace SGMT_tree {
int tree[Maxn << 2], cnt[Maxn << 2], add[Maxn << 2], Time[Maxn << 2];
LL Sum[Maxn << 2];
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ls rt << 1, l, mid
#define rs rt << 1 | 1, mid + 1, r
void setAdd(int rt, int val) {
tree[rt] += val;
add[rt] += val;
}
void setTime(int rt, int val) {
Sum[rt] += 1ll * cnt[rt] * val;
Time[rt] += val;
}
void (*setTag)(int, int);
void set(int dir) {
if(dir == 1) setTag = setAdd;
if(dir == 2) setTag = setTime;
}
void pushdown(int rt, int l, int r) {
if(add[rt]) {
setAdd(lc(rt), add[rt]), setAdd(rc(rt), add[rt]);
add[rt] = 0;
}
if(Time[rt]) {
if(tree[rt] == tree[lc(rt)]) setTime(lc(rt), Time[rt]);
if(tree[rt] == tree[rc(rt)]) setTime(rc(rt), Time[rt]);
Time[rt] = 0;
}
}
void pushup(int rt) {
cnt[rt] = 0;
tree[rt] = min(tree[lc(rt)], tree[rc(rt)]);
if(tree[rt] == tree[lc(rt)]) cnt[rt] += cnt[lc(rt)];
if(tree[rt] == tree[rc(rt)]) cnt[rt] += cnt[rc(rt)];
Sum[rt] = Sum[lc(rt)] + Sum[rc(rt)];
}
void build(int rt, int l, int r) {
tree[rt] = l; cnt[rt] = 1;
if(l == r) return ;
int mid = (l + r) >> 1;
build(ls), build(rs);
pushup(rt);
}
void modify(int rt, int l, int r, int x, int y, int val) {
if(x <= l && r <= y) {
setTag(rt, val);
return ;
}
int mid = (l + r) >> 1;
pushdown(rt, l, r);
if(y <= mid) modify(ls, x, y, val);
else if(x >= mid + 1) modify(rs, x, y, val);
else modify(ls, x, y, val), modify(rs, x, y, val);
pushup(rt);
}
LL query(int rt, int l, int r, int x, int y) {
if(x <= l && r <= y) return Sum[rt];
pushdown(rt, l, r);
int mid = (l + r) >> 1; LL res = 0;
if(x <= mid) res += query(ls, x, y);
if(y >= mid + 1) res += query(rs, x, y);
return res;
}
#undef lc
#undef rc
#undef ls
#undef rs
}
namespace INIT {
void Main() {
n = read();
rep(i, 1, n) a[i] = read();
q = read();
rep(i, 1, q) {
int l = read(), r = read();
s[r].push_back((Quer){l, i});
}
}
}
namespace SOLVE {
void Main() {
SGMT_tree :: build(1, 1, n);
rep(i, 1, n) {
SGMT_tree :: set(1);
SGMT_tree :: modify(1, 1, n, 1, n, -1);
for(SGMT_tree :: set(1); top1 && a[stk1[top1]] < a[i]; --top1)
SGMT_tree :: modify(1, 1, n, stk1[top1 - 1] + 1, stk1[top1], a[i] - a[stk1[top1]]);
stk1[++top1] = i;
for(SGMT_tree :: set(1); top2 && a[stk2[top2]] > a[i]; --top2)
SGMT_tree :: modify(1, 1, n, stk2[top2 - 1] + 1, stk2[top2],a[stk2[top2]] - a[i]);
stk2[++top2] = i;
SGMT_tree :: set(2);
SGMT_tree :: modify(1, 1, n, 1, n, 1);
rep(j, 0, s[i].size() - 1)
ans[s[i][j].id] = SGMT_tree :: query(1, 1, n, s[i][j].l, i);
}
rep(i, 1, q) write(ans[i]), putchar('
');
}
}
int main() {
#ifdef Qrsikno
freopen("CF997E.in", "r", stdin);
freopen("CF997E.out", "w", stdout);
#endif
INIT :: Main();
SOLVE :: Main();
return 0;
}