快进到我们有一个 $\Theta(n^2\log n)$ 的暴力：
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
int n,q,a[1000010],b[1000010];
int main() {
scanf("%d%d",&n,&q);
rep(i,1,n)scanf("%d",&a[i]);
rep(_,1,q){
int l,r,w=0;
scanf("%d%d",&l,&r);
rep(i,l,r)b[i]=a[i];
sort(b+l,b+r+1);
reverse(b+l,b+r+1);
multiset<int>st;
rep(i,l,r){
st.insert(a[i]);
if (*st.begin()==b[i])++w;
}
printf("%d\n",r-l+1-w);
}
return 0;
}我们得从这个东西开始入手优化。
首先对 $b$ 排序这种鬼东西太丑了，我们发现我们实际上只需要用“第 $k$ 大值”这一信息，也就是说，对于 $(l,r)$ 询问，若 $[l,i]$ 区间的最小值等于整体第 $(i-l+1)$ 大值，那么 $i$ 可以被统计入 $w$。
进一步考虑，这个的意思是什么呢？我们设这个第 $(i-l+1)$ 大值为 $v$，那么其实就要求，$[l,i]$ 内 $v$ 的个数 $s$ 要大于 $[i+1,r]$ 内 $>v$ 的点的个数 $t$，这个可以从排列归纳出来。
然后我们发现我们枚举 $(l,v)$ 的复杂度是能够承受的！因为从上面的情况可以看出，我们对于一个 $v$ 有用了 $l$ 只有 $a_l=v$ 的那些（不然一定可以归到他右边第一个 $a_l=v$）。因此我们考察枚举 $v$ 完倒着扫 $l$，只要我们关于 $i,r$ 维护的信息可以支持关于不同的 $v$ 相加，我们就做完了这个题。
那么考察 $(i,r)$ 到底在干些什么事情。我们固定 $l$ 后面第一个 $<v$ 的数为 $x$，那么显然 $l\le i<x$。发现此时，如果我们让 $i+1\to i$（哦这里意思是 i+=1，也就是 $i$ 移到 $i+1$，别理解错了；当然也得保证无论何时 $i<x$），那么我们发现，此时若 $a_{i+1}=v$，那么我们 $s$ 变大了 $1$，$t$ 不变；否则由 $x$ 的定义一定 $a_{i+1}>v$，那么 $t$ 减小了 $1$，$s$ 不变。
因此我们发现 $(s-t)_i=(s-t)_{i+1}-1$。这很厉害啊，因为这样的话，固定了 $l$ 和 $r$，我们就可以把这时 $i$ 的贡献写成一个数了：就是 $\max(0,s-t)$，这里 $s,t$ 分别表示 $[l,\min(x,r)]$ 内 $v$ 的个数 与 $[x+1,r]$ 内 $>v$ 的点的个数。这里要注意的一个点是 $(s-t)_{x-1}=(s-t)_x$。
发现这个时候已经几乎可以计算了，但是问题是我们要更新的并不是一个常数。具体地，我们发现在 $x$ 左边，$(l,r)$ 的贡献是不降且一次至多增加 $1$ 的；$x$ 右边反过来，不增且一次至多减少 $1$。那么怎么刻画这种东西？
考虑做差。如果 $l$ 右边的第一个值为 $v$ 的点为 $j$，那么我们发现 $(l,r)$ 的贡献表减掉 $(j,r)$ 的贡献表是一个“只有某个区间值为 $1$，其他值都为 $0$”的形态！而且这个区间左右端点也很好找：左端点是 $l$，右端点是 $x$ 后面第 $k$ 个 $>v$ 的数减一，其中 $k$ 是 $[l,x]$ 内值 $=v$ 的点的个数。而这可以用 BIT 倍增找到。
然后还要注意的一件事情是如果 $[l,j]$ 间有 $<v$ 的数，我们得把 $j$ 后面的贡献清除掉。这里不能用赋值为 $0$ 的方法，因为不满足 $v$ 之间可加性；然而暴力减法清除复杂度显然是对的，我们就用这个。
那么我们相当于要干的事情就是先枚举每个 $(v,l)$ 得到贡献三元组 $(l,L_r,R_r)$，其中这里后两元就是我们上面的贡献区间；然后最后重新扫一遍 $l$ 即可，扫的时候给所有 $l$ 上的区间加，然后查询贡献。
复杂度 $\Theta((n+q)\log n)$。
总结：这个题思考点全都很简单，但是主要是思考点有四个，思维链一长这题难度就有了。
- 写出一个合适的暴力
- 化成关于 $(v,l,r,i)$ 的 $s>t$ 形式
- 化成关于 $(v,l,r)$ 的 $\max(s-t,0)$ 形式
- 做差分发现可以维护了，得到区间，放到全局，扫描线结束
代码：
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
int n,q,a[1000010],rmn[1000010],lmn[1000010],ans[1000010];
vector<int>T[1000010];
vector<array<int,2>>Q[1000010];
vector<array<int,3>>U[1000010];
struct BIT{
int c[1000010];
void add(int o,int x){for (;o<=n+1;o+=o&-o)c[o]+=x;}
int ask(int o){int x=0;for (;o;o&=o-1)x+=c[o];return x;}
int bin(int o,int k){ // >o 后第 k 个 1
k+=ask(o),o=0;
drep(i,19,0)if ((o|1<<i)<=n&&c[o|1<<i]<k)k-=c[o|=1<<i];
return o+1;
}
}c1,c2,cc; // c1: >v; c2: <v, cc: final
int main() {
scanf("%d%d",&n,&q);
rep(i,1,n)scanf("%d",&a[i]);
rep(i,1,q){
int l,r;
scanf("%d%d",&l,&r);
Q[l].push_back({r,i});
}
rep(i,1,n){
c1.add(i,1);
T[a[i]].push_back(i);
}
{
stack<int>stk;
drep(i,n,1){
while (stk.size()&&a[stk.top()]>=a[i])stk.pop();
if (stk.size())rmn[i]=stk.top();else rmn[i]=n+1;
stk.push(i);
}
}
{
stack<int>stk;
rep(i,1,n){
while (stk.size()&&a[stk.top()]>=a[i])stk.pop();
if (stk.size())lmn[i]=stk.top();
stk.push(i);
}
}
rep(v,1,n){
for (auto i:T[v-1])c2.add(i,1);
for (auto i:T[v])c1.add(i,-1);
vector<array<int,2>>vec;
int cnt=0,m=T[v].size();
// cout<<"@@ "<<v<<'\n';
drep(o,m-1,0){
int x=rmn[T[v][o]];
if (o==m-1||rmn[T[v][o+1]]==x)++cnt;
else{
// cout<<"BAD "<<vec.size()<<' '<<lmn[T[v][o+1]]<<'\n';
cnt=1;
for (auto [l,r]:vec)
U[lmn[T[v][o+1]]].push_back({l,r,-1});
vec={};
}
x=c1.bin(x,cnt);
// cout<<T[v][o]<<' '<<x-1<<'\n';
vec.push_back({T[v][o],x-1});
U[T[v][o]].push_back({T[v][o],x-1,1});
}
for (auto [l,r]:vec)
U[lmn[T[v][0]]].push_back({l,r,-1});
}
drep(i,n,1){
for (auto [l,r,w]:U[i]){
// cout<<"ADD "<<i<<' '<<l<<' '<<r<<' '<<w<<'\n';
cc.add(l,w),cc.add(r+1,-w);
}
for (auto [j,p]:Q[i])ans[p]=j-i+1-cc.ask(j);
}
rep(i,1,q)printf("%d\n",ans[i]);
return 0;
}