Solution
暴力
枚举 ，对每个 做一次单调栈即可
正解
从暴力观察到对于每个 ，若对于 它是”成功点“，那么显然对于 它都是”成功点“ （证明考虑前面的点以及点 只需要少消去几个点）。因此考虑离线，对所有 query 按左端点排序，用一个 vector 存 当前 有几个点刚好是“成功点”，并插入 BIT 即可。
The code
赛时比较匆忙，码风不一定很好。简单题懒得封装了。
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define INF (0x3f3f3f3f)
using namespace std;
const int MAXN = 500005;
int n, q;
int a[MAXN], b[MAXN];
struct Que {
int l, r, id;
inline bool operator < (const Que &y) const {
return l < y.l;
}
}qr[MAXN];
int ans[MAXN];
int top, stc[MAXN];
vector<int>vec[MAXN];
inline void Solve() {
stc[top = 1] = 0;
for (int i = 1; i <= n; ++ i) {
while (top && (a[i] == a[stc[top]] || b[i] >= b[stc[top]]))
-- top;
vec[stc[top]].push_back(i);
stc[++ top] = i;
}
}
int tr[MAXN];
inline int lowbit(int x) {
return (x & (-x));
}
inline void add(int p, int x) {
while (p <= n) tr[p] += x, p += lowbit(p);
}
inline int query(int p) {
int res = 0;
while (p) res += tr[p], p -= lowbit(p);
return res;
}
inline void Calc() {
int ps = 0;
for (int i = 1; i <= q; ++ i) {
while (ps < qr[i].l) {
for (int u : vec[ps])
add(u, 1);
++ ps;
}
ans[qr[i].id] = query(qr[i].r) - query(qr[i].l - 1);
}
}
int main()
{
scanf ("%d%d", &n, &q);
for (int i = 1; i <= n; ++ i) scanf ("%d", a + i);
for (int i = 1; i <= n; ++ i) scanf ("%d", b + i);
b[0] = INF;
Solve();
for (int i = 1; i <= q; ++ i) {
scanf ("%d%d", &qr[i].l, &qr[i].r);
qr[i].id = i;
}
sort(qr + 1, qr + q + 1);
Calc();
for (int i = 1; i <= q; ++ i) printf ("%d\n", ans[i]);
return 0;
}