[m_{l,r}= extrm{id}(max_{i=l}^r a_i)\
f(l,r)=
egin{cases}
(r-l+1)+f(l,m_{l,r}-1)+f(m_{l,r}+1,r)& extrm{if } lle r\
0& extrm{else}\
end{cases}
]
设 (L_i=max{j}(j<i,a_j>a_i))，(R_i=min{j}(j>i,a_j>a_i))。
考虑每个 (iin[l,r]) 成为 (m_{L_i+1,R_i-1}) 时对答案的贡献：
[ extrm{len}Big([max(l,L_i+1),min(r,R_i-1)]Big)
]
[ herefore f(l,r)=sum_{i=l}^rmin(r,R_i-1)-max(l,L_i+1)+1
]
Code
#include <bits/stdc++.h>
using namespace std;
//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair(a,b)
#define x(a) a.first
#define y(a) a.second
#define b(a) a.begin()
#define e(a) a.end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
//Data
const int N=1e6;
int n,m,a[N+7],ql[N+7],qr[N+7];
int l[N+7],r[N+7];
vector<pair<int,int> > st[N+7];
ll ans[N+7];
typedef vector<ll> bit;
bit cnt,sm;
void add(bit&c,int x,ll y){for(;x<sz(c);x+=x&-x) c[x]+=y;}
ll sum(bit&c,int x){ll y=0;for(;x;x-=x&-x) y+=c[x];return y;}
ll sum(bit&c,int x,int y){return sum(c,y)-sum(c,x-1);}
//Main
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&ql[i]),st[ql[i]-1].pb(mp(i,-1));
for(int i=1;i<=m;i++) scanf("%d",&qr[i]),st[qr[i]].pb(mp(i,1));
a[0]=a[n+1]=inf;
for(int i=1;i<=n;i++){l[i]=i-1;while(a[l[i]]<a[i]) l[i]=l[l[i]];}
for(int i=n;i>=1;i--){r[i]=i+1;while(a[r[i]]<a[i]) r[i]=r[r[i]];}
for(int i=1;i<=n;i++) l[i]++,r[i]--;
for(int i=1;i<=m;i++) ans[i]=qr[i]-ql[i]+1;
cnt=sm=bit(n+7,0);
for(int i=1;i<=n;i++){
add(cnt,l[i],1),add(sm,l[i],l[i]);
for(auto j:st[i]) ans[x(j)]-=(sum(sm,ql[x(j)],qr[x(j)])+sum(cnt,1,ql[x(j)]-1)*ql[x(j)])*y(j);
}
cnt=sm=bit(n+7,0);
for(int i=1;i<=n;i++){
add(cnt,r[i],1),add(sm,r[i],r[i]);
for(auto j:st[i]) ans[x(j)]+=(sum(sm,ql[x(j)],qr[x(j)])+sum(cnt,qr[x(j)]+1,n)*qr[x(j)])*y(j);
}
for(int i=1;i<=m;i++) printf("%lld%c",ans[i],"
"[i<m]);
return 0;
}
祝大家学习愉快！