PKU 3298 Antimonotonicity

PKU

http://poj.org/problem?id=3298

1〜nからなる数列aiの部分数列で、
Mary0 > Mary1 < Mary2 > Mary3 < ... という関係を満たす最大の長さの数列の長さを求めろというような問題。

range maximum queryで以下のようなDPを処理。

dpmax[i] = max({dpmax[aj]|ai>aj,i>j})+1
dpmin[i] = max({dpmin[aj]|aij})+1
dpmax[i]はi番目の要素で山になって終わっている数列の最大の長さ
dpmin[i]はi番目の要素で谷になって終わっている数列の最大の長さ

最初は山で始まることに注意

int minq[100000];
int maxq[100000];

int in[30000];
int n;

int query(int l,int r,int al,int ar,int k,int* arr){
  if(l<=al && ar<=r) return arr[k];
  if(r<=al || ar<=l)
    return 0;
  return
    max(query(l,r,al,(al+ar)/2,k*2+1,arr),
        query(l,r,(al+ar)/2,ar,k*2+2,arr));
}

void update(int idx,int val,int al,int ar,int k,int* arr){
  //cout<<idx<<' '<<al<<' '<<ar<<endl;
  if(ar<=idx || idx<al) return;
  if(al<=idx && idx<ar)
    arr[k]=max(arr[k],val);
  if(al+1<ar){
    update(idx,val,al,(al+ar)/2,k*2+1,arr);
    update(idx,val,(al+ar)/2,ar,k*2+2,arr);
  }
}

void solve(){
  scanf("%d", &n);
  rep(i, n){
    scanf("%d", in+i);
    --in[i];
  }

  memset(minq,0,sizeof(minq));
  memset(maxq,0,sizeof(maxq));
  rep(i,n){
    //cout<<in[i]+1<<endl;
    int va=query(in[i]+1,n,0,n,0,maxq);
    int vb=query(0,in[i],0,n,0,minq);
    if(va)update(in[i],va+1,0,n,0,minq);
    update(in[i],vb+1,0,n,0,maxq);
    //cout<<va<<' '<<vb<<endl;
  }
  cout<<max(query(0,n,0,n,0,minq),query(0,n,0,n,0,maxq))<<endl;
}

main(){
  int t;
  scanf("%d", &t);

  rep(i, t)
    solve();
}