CF1454F - Array Partition（ST表/线段树+二分/双指针）

题意

比赛链接：Problem - F - Codeforces
给你一个长度为$n(3\leq n\leq 2\times 10^5)$序列，问你是否能够将其分成三段使其满足如下条件：第一段Max=第二段Min=第三段Max，如果存在则输出"YES"和每段的长度，否则输出"NO"。

思路

看到这个数据我第一反应是双指针+贪心，但是wa2中的testcase721...最终放弃，去补题了，后来发现是自己贪心的方法不对，这里用二分+贪心过的。

这里枚举第一段的范围（时间复杂度$O(n)$），然后去二分第二个区间的长度，这样第三个区间也确定下来了，这个时间复杂度是$O(logn)$。

这么理解，一个长度为$n$的序列要分成三段，就会有两个断点$l,r$，枚举$l$然后二分$r$，三个区间都能确定下来，然后我们用ST表来用$O(logn)$的时间复杂度来求每一段的Max或者Min，这样时间复杂度是$O(nlog^2n)$

然后来看每次如何check，其实我们每次是单调的：对于第三个区间，越来越大的话，说明你的Max是不递减的，就是有可能递增的；对于第二个区间来看，每次减小的话，说明你的Min是不递减的，有可能越来越大的。

这样我们分为四种情况：

res1,res2,res3分别代表三段的Max,Min,Max

if (res1>res2||res1>res3) r=mid-1;
else if (res1<res2||res1<res3) l=mid+1;

1）如果res1大于res2，也就是说res2需要扩大，也就是需要缩小范围，才可能使自己的Min越来越大
2）如果res1大于res3，同理，需要让自己越来越大
3）如果res1小于res2，也就是说需要让res2越来越小，需要扩大范围，才可能让自己的Min变得更小
4）如果res1小于res3，同理，需要让自己越来越小，需要缩小范围

前两种情况需要缩小，则r=mid-1;后两种情况需要扩大，则l=mid+1。

代码

inline void init()
{
    for (int i=2;i<N;i++)
        lg2[i]=lg2[i>>1]+1;
}
inline int getMin(int l,int r)
{
    int w=lg2[r-l+1];
    return Min(Mi[l][w],Mi[r-(1<<w)+1][w]);
}
inline int getMax(int l,int r)
{
    int w=lg2[r-l+1];
    return Max(Ma[l][w],Ma[r-(1<<w)+1][w]);
}
inline void Case_Test()
{
    cin>>n;
    rep(i,1,n) {cin>>a[i];Mi[i][0]=a[i];Ma[i][0]=a[i];}
    for (int i=n;i>=1;i--)
        for (int j=1;i+(1<<j)-1<=n;j++)
            Mi[i][j]=Min(Mi[i][j-1],Mi[i+(1<<j-1)][j-1]),
            Ma[i][j]=Max(Ma[i][j-1],Ma[i+(1<<j-1)][j-1]);

    for (int i=1;i<n-1;i++)
    {
        int l=i+1,r=n-1,mid;
        int res1=getMax(1,i),res2,res3;
        while (l<=r)
        {
            mid=(l+r)>>1;
            res2=getMin(i+1,mid);
            res3=getMax(mid+1,n);
            if (res1>res2||res1>res3) r=mid-1;
            else if (res1<res2||res1<res3) l=mid+1;
            else 
            {
                cout<<"YES"<<endl;
                cout<<i<<" "<<mid-i<<" "<<n-mid<<endl;
                return;
            }
        }
    }
    cout<<"NO"<<endl;

}