【LOJ3009】【BZOJ2090】【POI2010】Monotonicity 2

DP+树状数组"即可"。

相信很多人看到这道题的第一反应和窝一样:这不是水题吗,只要记f(i)f(i)表示下标以ii结尾的最长合法子序列长度,转移树状数组优化一下就行了。

还有一些人可能觉得这道题需要在状态中记录长度 ,于是得到了优秀的O(nklogn)O(nk\log n)O(nk)O(nk)做法。

第一反应觉得这道题是水题之后可能会觉得不对劲,DP需要最优子结构,而这个DP看起来并不满足呀。

然而,这个DP确实是满足最优子结构的,为什么呢?

(网上的题解大都没写证明,neither_nor写了证明但窝看不懂毒瘤jcy,于是窝决定写一下用谷歌翻译看波兰文官方题解(在P152)的成果)

就是要证下标以ii结尾的最长合法子序列,一定可以由某个下标以j<ij<i结尾的最长合法子序列接上ii得到。

不失一般性,设下标以nn结尾的最长合法子序列第一个不满足这个条件,再设mm为这个子序列的上一个下标。

b1,b2,,bf(m)b_1,b_2,\cdots,b_{f(m)}为下标以mm结尾的最长合法子序列对应的下标序列,显然bf(m)=mb_{f(m)}=m,设k=f(n)k=f(n)

因为nn继承的不是mm的最优解,所以k1<f(m)k-1<f(m),即f(m)kf(m)\geq k

讨论:

  • am=ana_m=a_n,这时b1,b2,,bf(m)1,nb_1,b_2,\cdots,b_{f(m)-1},n长度为f(m)kf(m) \geq k,显然为一个不会更劣的解。
  • am<ana_m<a_n,这就是说sk1=<"s_{k-1}=``<",继续讨论:
    • abk1<ana_{b_{k-1}}<a_n,那么b1,b1,,bk1,nb_1,b_1,\cdots,b_{k-1},n长度为kk,不会更劣。
    • abk1ana_{b_{k-1}}\geq a_n,我们有abk1<abka_{b_{k-1}}<a_{b_k},但是abk1an>ama_{b_{k-1}}\geq a_n>a_m,也即一定存在一个wkw\geq k满足abw>abw+1a_{b_w}>a_{b_{w+1}},也即sw=>"s_{w}=``>",我们取第一个这样的ww,于是i[k,w),abiabi+1\forall i \in [k,w), a_{b_i}\leq a_{b_{i+1}},又abk1<abka_{b_{k-1}}<a_{b_k},于是abw>abk1ana_{b_w}>a_{b_{k-1}}\geq a_n,于是b1,b1,,bw,nb_1,b_1,\cdots,b_{w},n长度为w+1>kw+1>k,更优。
  • am>ana_m>a_n,同理得证。

这样就证完啦。

使用两个树状数组分别维护下一个是大于和小于的情况,等于直接用数组维护。

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

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("3009.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
const int maxn=1000002;
inline void tense(pii &x,pii y){
    if (x<y)
        x=y;
}
struct bit{
    int n;
    pii t[maxn];
    void add(int p,pii v){
        for(;p<=n;p+=p&-p)
            tense(t[p],v);
    }
    pii query(int p){
        pii ans;
        for(;p;p-=p&-p)
            tense(ans,t[p]);
        return ans;
    }
}b1;
struct tib{
    int n;
    pii t[maxn];
    void add(int p,pii v){
        for(;p;p-=p&-p)
            tense(t[p],v);
    }
    pii query(int p){
        pii ans;
        for(;p<=n;p+=p&-p)
            tense(ans,t[p]);
        return ans;
    }
}b2;
inline pii inc(pii x){
    x.first++;
    return x;
}
int a[maxn],dp[maxn],lst[maxn],stk[maxn];
pii qwq[maxn];
char s[maxn];
int main(){
    init();
    int n=readint(),k=readint();
    for(int i=1;i<=n;i++)
        a[i]=readint();
    for(int i=1;i<=k;i++)
        s[i]=readchar();
    b1.n=b2.n=maxn-1;
    int ans=0;
    for(int i=1;i<=n;i++){
        pii lol;
        tense(lol,inc(b1.query(a[i]-1)));
        tense(lol,inc(b2.query(a[i]+1)));
        tense(lol,inc(qwq[a[i]]));
        dp[i]=lol.first,lst[i]=lol.second;
        // printf("dp[%d]=%d lst[%d]=%d\n",i,dp[i],i,lst[i]);
        lol.second=i;
        char now=s[(dp[i]-1)%k+1];
        if (now=='=')
            tense(qwq[a[i]],lol);
        else if (now=='<')
            b1.add(a[i],lol);
        else b2.add(a[i],lol);
        // printf("dp[%d]=%d lst[%d]=%d\n",i,dp[i],i,lst[i]);
        if (dp[i]>dp[ans])
            ans=i;
    }
    printf("%d\n",dp[ans]);
    int cur=0;
    while(ans){
        stk[++cur]=ans;
        ans=lst[ans];
    }
    for(int i=cur;i;i--)
        printf("%d ",a[stk[i]]);
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

本文链接:https://www.q234rty.top/2019/02/10/loj3009/

隐藏