CF2234E Vlad, Misha and Two Arrays 题解

· · 题解

CF2234E Vlad, Misha and Two Arrays

好题。我们从小到大考虑排列中的每一个数，对于区间 [l,r] 的最小值，它如果在位置 i，那么一定有 a_i=(i-l+1)(r-i+1)。因此，哪些位置可以放最小值是确定的，且有且仅能有一个位置能放最小值，否则要么最小值放不进去，要么放进去第二个值的时候会被最小值影响。

假设我们已经找到的最小值被放在哪里，一个直观的想法是把原序列按照这个位置劈开，递归到两边继续做这个过程。我们把左右两边的最小值的位置到这个位置连边，原序列1就被转化为了一棵树。又由于左右两边因为最小值的阻隔互相没有限制，因此唯一的限制是左右两边的值大于中间的值，这就转化为了一个定形态小根堆权值为排列计数问题，可以直接套用 UVA11174 Stand in a Line 的做法。

接下来的问题就是如何求出这棵树的形态了。对于这种分治找到某一个点后原地劈开的问题，有一个经典做法：直接分治顺着扫每个位置是否满足条件显然是 O(n^2) 的，于是我们从两边往中间扫，即按 l\to r\to l+1\to r-1\dots 的顺序扫，复杂度就对了。

证明的话考虑这个东西的复杂度相当于一棵二叉树，某个点 x 的贡献为 2\max\{\text{siz}[{\text{lc}[x]}],\text{siz}[{\text{rc}[x]}]\}。2 是常数不管，总贡献等价于对于每一个点，不断跳父边，如果这个子树较小就贡献 1。注意到这个子树较小意味着跳过的子树大小翻倍，一个点至多翻倍 \log n 次，因此总复杂度为 O(n\log n)。

顺带一提，分治的时候不需要考虑有多个可行位置的情况，因为随便选一个递归下去最后一定会有一段不存在最小值的位置。

#include <bits/stdc++.h>
using namespace std;
long long t,n,a[600000],flag=1,ans=1;
const long long mod=1e9+7;
long long power(long long a,long long p)
{
    long long x=a%mod,ans=1;
    while(p)
       {
        if(p&1)ans=ans*x%mod;
        p>>=1;
        x=x*x%mod;
       }
    return ans;
}

long long solve(long long l,long long r)
{
    if(l>r)return 0;
    long long siz=0,flag=0;
    for(int i=1;i<=(r-l+2)/2;i++)
        {
            long long p=l+i-1;
            if(a[p]==(p-l+1)*(r-p+1))
               {
                flag=1,siz=solve(l,p-1)+solve(p+1,r)+1,ans=ans*power(siz,mod-2)%mod;
                break;
               }
            p=r-i+1;
            if(a[p]==(p-l+1)*(r-p+1))
               {
                flag=1,siz=solve(l,p-1)+solve(p+1,r)+1,ans=ans*power(siz,mod-2)%mod;
                break;
               }
        }
    if(flag==0)ans=0;
    return siz;
}

int main()
{
    scanf("%lld",&t);
    while(t--)
       {
        scanf("%lld",&n);
        ans=1;
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
        long long siz=solve(1,n);
        for(int i=1;i<=siz;i++)ans=ans*i%mod;
        printf("%lld\n",ans);
       }
    return 0;
}