2013年杭電多校第1場第5題Deque

タイトル転送ゲート:http://acm.hdu.edu.cn/showproblem.php?pid=4604
考え方:ここで私は最初に入れた数を切り口にして、あなたはこの数が分水嶺だと思って、その前の数はすべてそれより大きくなくて、それからの数はすべてそれより小さくありません.では、元の数列では、「前」の数はその後ろの非インクリメンタルシーケンスであり、「後」の数は非インクリメンタルシーケンスである必要があります.これで、LISを簡単に思いつきました.もちろん最も素朴なアルゴリズムはn^2で、考えてみればタイムアウトしていることがわかるので、ここでは二分の方法でやっていますが、複雑度はlognしかありません.ここのすべての点はすべて1回が第1の点だと仮定して、行ってから探すのは不可能で、ここは後ろから前へ探すべきで、全体が1回すればいいので、ここで私が選んだのは配列を後ろから前へ逆順に入力して、このように探す時下の標順によって探すことができます.もちろん、見つかった非インクリメンタルシーケンスと非インクリメンタルシーケンスには重複する数がある可能性がありますが、最初に入れた数aについては、2つのシーケンスの数と、aの出現回数が少ないシーケンスの数を減算すればよいので、ここでこの数を検索するのも2点です.そうしないとタイムアウトします.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[100005],t,n;
int s1[100005],s2[100004],num1,num2;
int c1,c2,ans,f1,f2,m1,m2;
int low,high,mid;
int main()
{
    scanf("%d",&t);
    while(t--)
    {

        scanf("%d",&n);
        for(int i=n;i>0;i--)
        {
            scanf("%d",&a[i]);
        }
        num1=num2=1;
        s1[1]=a[1];
        s2[1]=a[1];
        ans=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]>=s1[num1]){s1[++num1]=a[i];c1=num1;}
            else
            {
                low=1;high=num1;
                while(low<=high)
                {
                    mid=(low+high)/2;
                    if(a[i]>=s1[mid])low=mid+1;
                    else high=mid-1;
                }
                s1[low]=a[i];
                c1=low;
            }
            if(a[i]<=s2[num2]){s2[++num2]=a[i];c2=num2;}
            else
            {
                low=1;high=num2;
                while(low<=high)
                {
                    mid=(low+high)/2;
                    if(a[i]<=s2[mid])low=mid+1;
                    else high=mid-1;
                }
                s2[low]=a[i];
                c2=low;
            }
            low=1;high=c1;
            while(low<=high)
            {
                mid=(low+high)/2;
                if(a[i]==s1[mid])high=mid-1;
                else low=mid+1;
            }
            //cout<<high<<" ";
            f1=c1-high;
            low=1;high=c2;
            while(low<=high)
            {
                mid=(low+high)/2;
                if(a[i]==s2[mid])high=mid-1;
                else low=mid+1;
            }
            //cout<<high<<endl;
            f2=c2-high;
            if(c1+c2-min(f1,f2)>ans)ans=c1+c2-min(f1,f2);
        }
        cout<<ans<<endl;
    }
    return 0;
}