给定长度为 (n)，的排列 (p_1, p_2, dots, p_n)，(q) 次询问，每次询问一段区间 (l, r)，计算
[f(l, r) = egin{cases} (r - l + 1) + f(l, m_{l, r} - 1) + f(m_{l, r} + 1, r) & l leq r\ 0 & l > r end{cases} ]其中 (m_{l, r}) 表示 (p_l, p_{l + 1}, dots, p_r) 中最大值的下标。
(n, q leq 10^6)。
容易发现 (f(l, r)) 是区间 ([l, r]) 笛卡尔树的节点 (size) 和。
一个点 (p_i) 的在笛卡尔树上的子树为一个区间 ([lg_i + 1, rg_i - 1])，即左右两边离他最近的比他大的两个数之间。
所以
[f(l, r) = sum_{i = l}^r (min{r, rg_i - 1} - max{l, lg_i + 1} + 1)
]
先用单调栈预处理出 (lg_i, rg_i)，区间加一 ([lg_i, rg_i])，区间求和 ([l, r])，这个可以用差分线性求出，但是多出来区间 ([l, r]) 之外的贡献。
正序扫一遍去掉 ([1, l - 1]) 的贡献，倒序扫一遍去掉 ([r + 1, n]) 的贡献，这个可以用树状数组区间加区间求和来实现。
#include <bits/stdc++.h>
#ifdef LOCAL
#define dbg(args...) std::cerr << " 33[32;1m" << #args << " -> ", err(args)
#else
#define dbg(...)
#endif
inline void err() { std::cerr << " 33[0m
"; }
template<class T, class... U>
inline void err(const T &x, const U &... a) { std::cerr << x << ' '; err(a...); }
template <class T>
inline void readInt(T &w) {
char c, p = 0;
while (!isdigit(c = getchar())) p = c == '-';
for (w = c & 15; isdigit(c = getchar());) w = w * 10 + (c & 15);
if (p) w = -w;
}
template <class T, class... U>
inline void readInt(T &w, U &... a) { readInt(w), readInt(a...); }
template <class T, class U>
inline bool smin(T &x, const U &y) { return y < x ? x = y, 1 : 0; }
template <class T, class U>
inline bool smax(T &x, const U &y) { return x < y ? x = y, 1 : 0; }
typedef long long LL;
typedef std::pair<int, int> PII;
constexpr int N(1e6 + 5);
int n, m, a[N], s[N], l[N], r[N];
class FenwickTree {
public:
void add(int l, int r) {
add(v, l, 1), add(v, r + 1, -1);
add(vi, l, l), add(vi, r + 1, -r - 1);
}
LL ask(int l, int r) {
return ask(v, r) * (r + 1) - ask(v, l - 1) * l - ask(vi, r) + ask(vi, l - 1);
}
void clear() {
memset(v, 0, sizeof v);
memset(vi, 0, sizeof vi);
}
private:
LL v[N], vi[N];
void add(LL c[], int p, int x) {
for (; p <= n; p += p & -p) c[p] += x;
}
LL ask(LL c[], int p) {
LL r = 0;
for (; p; p -= p & -p) r += c[p];
return r;
}
} t;
int ql[N], qr[N];
std::vector<int> lq[N], rq[N];
LL b[N], ans[N];
int main() {
readInt(n, m);
for (int i = 1; i <= n; i++) readInt(a[i]);
for (int i = 1; i <= n; i++) {
while (s[0] && a[s[s[0]]] < a[i]) s[0]--;
b[l[i] = s[s[0]] + 1]++;
// printf("+ %d %d
", s[s[0]], i);
s[++s[0]] = i;
}
s[0] = 0;
for (int i = n; i; i--) {
while (s[0] && a[s[s[0]]] < a[i]) s[0]--;
if (s[0])
b[r[i] = s[s[0]]]--;
else
r[i] = n + 1;
// printf("- %d %d
", i, s[s[0]]);
s[++s[0]] = i;
}
for (int i = 1; i <= n; i++) b[i] += b[i - 1];
for (int i = 1; i <= n; i++) b[i] += b[i - 1];
for (int i = 1; i <= m; i++) readInt(ql[i]), lq[ql[i]].push_back(i);
for (int i = 1; i <= m; i++) readInt(qr[i]), rq[qr[i]].push_back(i);
for (int i = 1; i <= n; i++) {
for (int j : lq[i]) ans[j] -= b[ql[j] - 1] + t.ask(ql[j], qr[j]);
t.add(l[i], r[i] - 1);
}
t.clear();
for (int i = n; i; i--) {
for (int j : rq[i]) ans[j] += b[qr[j]] - t.ask(ql[j], qr[j]);
t.add(l[i], r[i] - 1);
}
for (int i = 1; i <= m; i++) printf("%lld ", ans[i]);
return 0;
}