cjb-poi2010monotonicity

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <cassert>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
#define N 510000
int n,k;
int f[N],pre[N],a[N];
char s[N];
struct SegmentTree
{
    int p[3*N],l[3*N],r[3*N],tot;
    int newnode()
    {
        tot++; l[tot]=r[tot]=p[tot]=0; return tot;
    }
    void init()
    {
        tot=-1; newnode(); newnode();
    }
    void insert(int t,int ll,int rr,int k,int pos)
    {
        if (ll==rr)
        {
            if (f[p[t]]<f[pos])p[t]=pos;
            return;
        }
        int mid=(ll+rr)/2;
        if (k<=mid)
        {
            if (l[t]==0)l[t]=newnode();
            insert(l[t],ll,mid,k,pos);
        }
        else
        {
            if (r[t]==0)r[t]=newnode();
            insert(r[t],mid+1,rr,k,pos);
        }
        if (f[p[l[t]]]>f[p[r[t]]])p[t]=p[l[t]]; else p[t]=p[r[t]];
    }
    int get(int t,int ll,int rr,int a,int b)
    {
        if (t==0 || a>b)return 0;
        if (a<=ll && rr<=b)return p[t];
        int mid=(ll+rr)/2;
        int t1=0,t2=0;
        if (a<=mid)t1=get(l[t],ll,mid,a,b);
        if (b>mid)t2=get(r[t],mid+1,rr,a,b);
        if (f[t1]>f[t2])return t1; else return t2;
    }
}A,B,C;


int main()
{
    cin>>n>>k;
    rep(i,n)scanf("%d",&a[i]);
    rep(i,k){ char ts[5]; scanf("%s",ts); s[i]=ts[0]; }
    A.init(); B.init(); C.init();
    rep(i,n)
    {
        f[i]=1; pre[i]=0;
        int p1=A.get(1,1,1000001,1,a[i]-1);
        if (p1 && f[p1]+1>f[i])f[i]=f[p1]+1,pre[i]=p1;
        int p2=B.get(1,1,1000001,a[i],a[i]);
        if (p2 && f[p2]+1>f[i])f[i]=f[p2]+1,pre[i]=p2;
        int p3=C.get(1,1,1000001,a[i]+1,1000001);
        if (p3 && f[p3]+1>f[i])f[i]=f[p3]+1,pre[i]=p3;
        char c=s[(f[i]-1)%k + 1]; 
        if (c=='<')A.insert(1,1,1000001,a[i],i);
        if (c=='=')B.insert(1,1,1000001,a[i],i);
        if (c=='>')C.insert(1,1,1000001,a[i],i);
    }
    int maxp=1;
    rep(i,n)if (f[i]>f[maxp])maxp=i;
    static vector<int> ans; ans.clear();
    for(int now=maxp;now;now=pre[now])ans.pb(a[now]);
    reverse(ans.begin(),ans.end());
    cout<<f[maxp]<<endl;
    for(int i=0;i<f[maxp];i++)printf("%d%c",ans[i],i==f[maxp]-1?'\n':' ');
    return 0;
}
}}}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <cassert>
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
#define N 510000
int n,k;
int f[N],pre[N],a[N];
char s[N];
struct SegmentTree
{
    int p[3*N],l[3*N],r[3*N],tot;
    int newnode()
    {
        tot++; l[tot]=r[tot]=p[tot]=0; return tot;
    }
    void init()
    {
        tot=-1; newnode(); newnode();
    }
    void insert(int t,int ll,int rr,int k,int pos)
    {
        if (ll==rr)
        {
            if (f[p[t]]<f[pos])p[t]=pos;
            return;
        }
        int mid=(ll+rr)/2;
        if (k<=mid)
        {
            if (l[t]==0)l[t]=newnode();
            insert(l[t],ll,mid,k,pos);
        }
        else
        {
            if (r[t]==0)r[t]=newnode();
            insert(r[t],mid+1,rr,k,pos);
        }
        if (f[p[l[t]]]>f[p[r[t]]])p[t]=p[l[t]]; else p[t]=p[r[t]];
    }
    int get(int t,int ll,int rr,int a,int b)
    {
        if (t==0 || a>b)return 0;
        if (a<=ll && rr<=b)return p[t];
        int mid=(ll+rr)/2;
        int t1=0,t2=0;
        if (a<=mid)t1=get(l[t],ll,mid,a,b);
        if (b>mid)t2=get(r[t],mid+1,rr,a,b);
        if (f[t1]>f[t2])return t1; else return t2;
    }
}A,B,C;
int main()
{
    cin>>n>>k;
    rep(i,n)scanf("%d",&a[i]);
    rep(i,k){ char ts[5]; scanf("%s",ts); s[i]=ts[0]; }
    A.init(); B.init(); C.init();
    rep(i,n)
    {
        f[i]=1; pre[i]=0;
        int p1=A.get(1,1,1000001,1,a[i]-1);
        if (p1 && f[p1]+1>f[i])f[i]=f[p1]+1,pre[i]=p1;
        int p2=B.get(1,1,1000001,a[i],a[i]);
        if (p2 && f[p2]+1>f[i])f[i]=f[p2]+1,pre[i]=p2;
        int p3=C.get(1,1,1000001,a[i]+1,1000001);
        if (p3 && f[p3]+1>f[i])f[i]=f[p3]+1,pre[i]=p3;
        char c=s[(f[i]-1)%k + 1]; 
        if (c=='<')A.insert(1,1,1000001,a[i],i);
        if (c=='=')B.insert(1,1,1000001,a[i],i);
        if (c=='>')C.insert(1,1,1000001,a[i],i);
    }
    int maxp=1;
    rep(i,n)if (f[i]>f[maxp])maxp=i;
    static vector<int> ans; ans.clear();
    for(int now=maxp;now;now=pre[now])ans.pb(a[now]);
    reverse(ans.begin(),ans.end());
    cout<<f[maxp]<<endl;
    for(int i=0;i<f[maxp];i++)printf("%d%c",ans[i],i==f[maxp]-1?'\n':' ');
    return 0;
}