Range Sorting (Hard Version)

· · 题解

赛时想复杂了。当时只是想做出 B1，于是考虑 n^2 枚举区间。

实际上这种题一般都是单个位置算贡献的。

先令答案为对所有区间“硬”排序的总贡献。

考虑位置为 x，如果只用对 [l,x] 和 [x+1,r] 分别排序。当前区间排序的贡献就会 -1。

那么 \max\limits_{j=l}^{x}a_j<\min\limits_{j=x+1}^{r} a_j。

发现直接枚举不好算，我们可以钦定每个 a_i 为 [x+1,r] 的最小值。（钦定为最大值也可以）。然后求当前满足要求的区间个数。

  • 实际是寻找满足上述式子的 l_{min} 和 r_{max}，那么区间数量就是 (r_{max}-i+1)\times(x-l_{min}+1)。
  • 可以发现，x 是从 i 往前第一个值小于 a_i 的位置，否则 a_i 一定不是 [x+1,r] 的最小值。
  • 根据 \max\limits_{j=l}^{x}a_j<a_i，从 x 往前找 l_{min} 即可。
  • 根据 a_i 是 [x+1,r] 的最小值，r_{max} 是从 i 往后第一个值小于 a_i 的往前一个位置，否则 a_i 一定不是 [x+1,r] 的最小值。

由于 a_i 两两不同，最小值也不同，故不会重复计算。

所以这道题难就难在想到用钦定最小值的方法来计算。

对于形如“第一个大于/小于”，可以用单调栈求。

对于 l_{min}，可以通过跳 ST 表的方式求，每次跳表时如果最大值小于 a_i，那么就可以跳。

时间复杂度 O(n\log n)。 

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int n,t,a[N],f[20][N],r[N];
long long ans;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--)
    {
        ans=0;
        cin>>n;
        a[0]=a[n+1]=0;
        for(int i=1;i<=n;i++) cin>>a[i],f[0][i]=a[i],ans+=1ll*i*(i-1)/2;
        for(int j=1;j<20;j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
                f[j][i]=max(f[j-1][i],f[j-1][i+(1<<j-1)]);
        stack<int> st;
        st.push(n+1);
        for(int i=n;i;i--)
        {
            //这里求的实际是 r_min+1，从后往前第一个小于 a[i] 的位置
            while(a[st.top()]>a[i]) st.pop();
            r[i]=st.top();
            st.push(i);
        }
        while(!st.empty()) st.pop();
        st.push(0);
        for(int i=1;i<=n;i++)
        {
            //这里求的是 x
            while(a[st.top()]>a[i]) st.pop();
            int j=st.top();
            //跳表求 l_min
            for(int k=19;~k;k--)
                if(j>(1<<k)&&f[k][j-(1<<k)]<a[i]) j-=1<<k;
            if(st.top()>0) ans-=1ll*(r[i]-i)*(st.top()-j+1);
            st.push(i);
        }
        cout<<ans<<'\n';
    }
}