CF1827B2

Mikefeng · 2023-05-15 19:09:47 · 题解

题意

对 l,r 排序的花费是 r-l，问对于每个子区间排序的花费和是多少。

做法

首先可以证明，一定不会有两次排序相交，否则一次更大的排序一定不劣。

容斥，最大花费显然是 \sum_{i=2}^n (i-1)\times(n-i+1)，考虑对于 \forall l\le i<r 来说，什么时候 l,i 和 i+1,r 可以分别排序。

发现不好计数，因为与前半段的最大值和后半段的最小值都有关系。

转化一下，枚举前半段的最大值 x，位置为 b，要求后半段的最小值比 x 大。

可以通过 set 找到前一个比 x 大的数的位置 a，后一个比 x 大的数的位置 c，c 后面第一个比 x 小的数的位置 d。

那么前半段的左端点可以在 (a,b] 中选，右端点一定是 c-1，后半段的左端点一定是 c，右端点可以在 [c,d) 中选，贡献为 (b-a)\times(d-c)。

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

代码

const int N=3e5+5;
int T,n;
int a[N],id[N];
set<int> s1,s2;
bool M2;
int main(){
    int Time=clock();
    look_memory;
    T=read();
    while(T--){
        n=read();
        F(i,1,n) a[i]=read();
        ll sum=0;
        F(i,2,n) sum+=1ll*(i-1)*(n-i+1);
        F(i,0,n+1) s1.emplace(i);
        s2.emplace(0);s2.emplace(n+1);
        F(i,1,n) id[i]=i;
        sort(id+1,id+n+1,[&](int i,int j){return a[i]<a[j];});
        F(i,1,n){
            int b=id[i];
            int a=*(--s1.lower_bound(b));
            int c=*s1.upper_bound(b);
            if(c!=n+1){
                int d=*s2.lower_bound(c);
                sum-=1ll*(b-a)*(d-c);
            }
            s1.erase(b);s2.emplace(b);
        }
        cout<<sum<<'\n';
        s1.clear();s2.clear();
    }
    look_time;
    return 0;
}