[POI 17 Stage 3] Monotonicity 2

作法：

首先考慮一個樸素的算法：對於每個$i$，我們知道存在一些以$i$結尾的子字串是滿足題目要求的，那麼對每個子字串來說，都可以用他的長度去更新所有$i$之後的答案（依照這個長度時下一步應該要比$a[i]$大還是小，或是等於）。具體來說，如果有一個$i$結尾的子字串長度為$L$，並且$s[L]$為$<$，那麼就可以用$L+1$去更新$i$以後的值大於$a[i]$的位子的答案。這裡有個非常不顯然的結論，就是其實對於所有$i$結尾的子字串，我們只需要紀錄最長那個的長度就可以了！（證明補在後面），因此就可以用 DP 算出每個位子結尾的最長子序列長度了。具體來說，當算完$dp[i]$時，如果$s[dp[i]]$為$<$，那麼之後如果遇到有某個$>a[i]$的數，都要把他的答案和$dp[i]+1$取 max 。如果是$<$的話也一樣，因此這就可以用一個區間修改加上單點查詢的線段樹來作了。而因為要輸出解，所以在線段樹上會多紀錄說造成這個最大值的 index 是誰。

再來則是證明為什麼紀錄最長的就可以了，假設以$x$結尾有兩個滿足條件的子序列，長度分別是$L$和$l$，其中$L>l$。記兩個子序列的 index 分別為$i_1,...,i_L$和$j_1,...,j_l$（因此有$i_L=j_l=x$），並且不妨設$s[l]$為$<$（當$s[l]$為$=$時證法幾乎一樣，在此省略），並且此時$x$準備要拿$l+1$去更新$y$的答案。令$z=i_l$，如果$a[z]<a[y]$，那麼在我們前面算到$z$的答案時早就已經拿$l+1$去更新$y$的答案了，因此這個情況下長度$l$的這個子字串是完全沒有用的。反之如果$a[z]\geq a[y]$，由$s[l]$為$<$和$x$要拿長度$l$的子字串去更新$y$的答案可以推出$a[x]<a[y]$，所以有$a[z]\geq a[y]>a[x]$，推得$a[z]>a[x]$，因此考慮子序列$a[i_l],...,a[i_L]$，裡面一定存在相鄰的兩項使得左大於右，也就是存在一個 index $i_u$（$l\leq u < L$），滿足$a[i_u]>a[i_{u+1}]$（這也代表了$s[u]$為$>$）。我們取滿足這個條件的最小的$u$，不難發現$a[z]<a[i_u]$，因此有$a[i_u]>a[z]\geq a[y]$，因此當我們在算完$i_u$的答案時，就會拿$u+1$去更新$y$的答案了，所以在這種情況長度為$l$的子序列也是沒有用的，所以就可以直接不紀錄了。

code :

#include<bits/stdc++.h>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int maxn=1000000+10 ;
 
struct node
{
    node *l,*r ;
    pii p ;
    node(){l=r=NULL ; p=pii(1,0) ;}
};
 
node *build(int l,int r)
{
    if(l==r) return new node ;
    node *u=new node ;
    int mid=(l+r)/2 ;
    u->l=build(l,mid) ;
    u->r=build(mid+1,r) ;
    return u ;
}
 
inline void up(pii &p,const pii &q){p=max(p,q);}
void modify(int l,int r,int L,int R,node *u,const pii &p)
{
    if(l==L && r==R){up(u->p,p) ; return ;}
    int mid=(L+R)/2 ;
    if(r<=mid) modify(l,r,L,mid,u->l,p) ;
    else if(l>mid) modify(l,r,mid+1,R,u->r,p) ;
    else modify(l,mid,L,mid,u->l,p) ,
        modify(mid+1,r,mid+1,R,u->r,p) ;
}
pii query(int L,int R,node *u,int pos)
{
    if(L==R) return u->p ;
    int mid=(L+R)/2 ;
    if(pos<=mid) return max(u->p,query(L,mid,u->l,pos)) ;
    else return max(u->p,query(mid+1,R,u->r,pos)) ;
}
 
int last[maxn],a[maxn],type[maxn] ;
void print(int x,int t)
{
    if(!x) return ;
    print(last[x],t+1) ;
    printf("%d%c",a[x],t?' ':'\n') ;
}
 
pii equ[maxn] ;
main()
{
    int n,k ; scanf("%d%d",&n,&k) ;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]) ;
    for(int i=1;i<=k;i++)
    {
        char s[3] ; scanf("%s",s) ;
        type[i]=(s[0]=='<' ? -1 : (s[0]=='=' ? 0 : 1)) ;
    }
    for(int i=k+1;i<n;i++) type[i]=type[i-k] ;
    for(int i=0;i<maxn;i++) equ[i]=pii(-1,-1) ;
 
    node *root=build(0,maxn) ;
    int ed=-1 , ans=-1 ;
    for(int i=1;i<=n;i++)
    {
        pii p=max(query(0,maxn,root,a[i]),equ[a[i]]) ;
        int len=p.F ; last[i]=p.S ;
        if(len>ans) ans=len , ed=i ;
        if(type[len]==0) up(equ[a[i]],pii(len+1,i)) ;
        else if(type[len]==-1) modify(a[i]+1,maxn,0,maxn,root,pii(len+1,i)) ;
        else modify(0,a[i]-1,0,maxn,root,pii(len+1,i)) ;
    }
    printf("%d\n",ans) ;
    print(ed,0) ;
}