题解：P14753 森
Acit
·
·
题解
思路
用 [l,r] 中最靠右的最小值刻画这个区间。
记 l_i 为 i 左侧最靠近 i 且值严格小于 a_i 的位置，r_i 为 i 右侧最靠近 i 且值不大于 a_i 的位置。那么如果 a_i 为区间的特征值，则一定有该区间被 [l_i+1,r_i-1] 包含，所以这样的区间个数为 (i-l_i)\times(r_i-i)。
而 $(x,l,r,y)$ 中的 $x$ 和 $y$ 可以分别在 $[1,l_i]$ 和 $[r_i,n]$ 中选择小于 $a_i$ 的数，显然可以用主席树求出。然后将求出的几个数相乘，累加计算答案即可。
时间复杂度 $O(n\log n)$。
### **Code**
```cpp
#include<bits/stdc++.h>
#define int long long
#define forr(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
#define PII pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=3e5+10,MOD=998244353;
int n,a[N];
int root[N],ccnt;
struct Node{
int ls,rs,cnt;
}tree[N<<5];
#define ls(k) tree[k].ls
#define rs(k) tree[k].rs
#define s(k) tree[k].cnt
#define mid ((l+r)>>1)
void update(int &k,int k1,int l,int r,int x,int v){
if(l>x||r<x)return k=k1,void();
if(!k)k=++ccnt;
if(l==r)return s(k)=s(k1)+v,void();
update(ls(k),ls(k1),l,mid,x,v);update(rs(k),rs(k1),mid+1,r,x,v);
s(k)=s(ls(k))+s(rs(k));
}
int ask(int k,int l,int r,int x,int y){
if(l>y||r<x)return 0;
if(x<=l&&r<=y)return s(k);
return ask(ls(k),l,mid,x,y)+ask(rs(k),mid+1,r,x,y);
}
int lf[N],rt[N];
int stk[N],tp,ans;
signed main() {
ios::sync_with_stdio(0);
cin>>n;
forr(i,1,n)cin>>a[i],update(root[i],root[i-1],1,n,a[i],1);
forr(i,1,n){
while(tp&&a[stk[tp]]>=a[i])tp--;
lf[i]=stk[tp];
stk[++tp]=i;
}
tp=0;
roff(i,n,1){
while(tp&&a[stk[tp]]>a[i])tp--;
rt[i]=stk[tp];
stk[++tp]=i;
}
forr(i,2,n){
if(!lf[i]||!rt[i])continue;
int v1=ask(root[lf[i]],1,n,1,a[i]-1);
int v2=ask(root[n],1,n,1,a[i]-1)-ask(root[rt[i]-1],1,n,1,a[i]-1);
ans+=v1*v2%MOD*(i-lf[i])%MOD*(rt[i]-i)%MOD;
ans%=MOD;
}
cout<<ans;
return 0;
}
```