HDUBeauty Of Unimodal Sequence
同NOIP2004合唱队形，原题DP部分可以直接贴。
题意：求一个最长严格先上升后下降子序列，有两问，输出字典序最小解和字典序最大解。
从后往前DP，使用线段树维护，过程中使用后继数组记录转移过程。然后顺着模拟一遍取出来就行了。思路很简单。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=300005;
long long A[MAXN];
struct tnode
{
int dpval;
int maxpos;
int minpos;
int l,r;
};
tnode operator + (const tnode &A,const tnode &B)
{
tnode C;
C.l=A.l;
C.r=B.r;
if(A.dpval>B.dpval)
{
C.dpval=A.dpval;
C.maxpos=A.maxpos;
C.minpos=A.minpos;
}
if(A.dpval<B.dpval)
{
C.dpval=B.dpval;
C.maxpos=B.maxpos;
C.minpos=B.minpos;
}
if(A.dpval==B.dpval)
{
C.dpval=A.dpval;
C.maxpos=max(A.maxpos,B.maxpos);
C.minpos=min(A.minpos,B.minpos);
}
return C;
}
struct Segment_Tree
{
tnode t[4*MAXN];
int id[MAXN];
void update (int root)
{
int ch=root<<1;
t[root]=t[ch]+t[ch+1];
}
void buildt(int root,int l,int r)
{
t[root].l=l;
t[root].r=r;
if(l!=r)
{
int mid=(l+r)>>1;
int ch=root<<1;
buildt(ch,l,mid);
buildt(ch+1,mid+1,r);
update(root);
}
else
{
t[root].dpval=t[root].maxpos=t[root].minpos=-1;
id[l]=root;
}
return;
}
void change(int tvpos,int val,int pos)
{
int now=id[tvpos];
if(t[now].dpval<val)
{
t[now].dpval=val;
t[now].minpos=pos;
t[now].maxpos=pos;
}
else if(t[now].dpval==val)
{
t[now].minpos=min(t[now].minpos,pos);
t[now].maxpos=max(t[now].maxpos,pos);
}
else
{
return;
}
now>>=1;
while(now)
{
update(now);
now>>=1;
}
return;
}
tnode query(int root,int l,int r)
{
if(l>r)
{
tnode ret;
ret.l=ret.r=ret.dpval=ret.maxpos=ret.minpos=-1;
return ret;
}
if(t[root].l==l&&t[root].r==r)
{
return t[root];
}
int mid=(t[root].l+t[root].r)>>1;
int ch=root<<1;
if(r<=mid)return query(ch,l,r);
else if(l>mid)return query(ch+1,l,r);
else return query(ch,l,mid)+query(ch+1,mid+1,r);
}
};
Segment_Tree ST0,ST1;
struct discretization_node
{
int num;
int ki;
}disc[MAXN];
bool cmp(discretization_node x,discretization_node y)
{
return x.num<y.num;
}
int discretization(int a[],int n,discretization_node disc[])
{
for(int i=1;i<=n;++i)
{
disc[i].num=a[i];
disc[i].ki=i;
}
sort(disc+1,disc+1+n,cmp);
int cnt=0,pre;
for(int i=1;i<=n;++i)
{
if(i==1||a[disc[i].ki]!=pre)++cnt;
pre=a[disc[i].ki];
a[disc[i].ki]=cnt;
}
return cnt;
}
int n,a[MAXN],nextpos[MAXN][2][2],nextstate[MAXN][2][2],numsize,dp[MAXN][2],anslen,bg0,bg1,s0,s1;
vector<int>A1,A2;
int main()
{
while(scanf("%d",&n)!=EOF)
{
anslen=0;
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
}
numsize=discretization(a,n,disc);
ST0.buildt(1,1,numsize);
ST1.buildt(1,1,numsize);
for(int i=n;i;--i)
{
tnode temp1=ST1.query(1,1,a[i]-1);
if(temp1.dpval!=-1)
{
dp[i][1]=temp1.dpval+1;
nextstate[i][1][0]=1;
nextpos[i][1][0]=temp1.minpos;
nextstate[i][1][1]=1;
nextpos[i][1][1]=temp1.maxpos;
}
else
{
dp[i][1]=1;
nextstate[i][1][0]=-1;
nextpos[i][1][0]=-1;
nextstate[i][1][1]=-1;
nextpos[i][1][1]=-1;
}
ST1.change(a[i],dp[i][1],i);
tnode temp0=ST0.query(1,a[i]+1,numsize);
if(temp1.dpval==-1&&temp0.dpval==-1)
{
dp[i][0]=1;
nextstate[i][0][0]=-1;
nextpos[i][0][0]=-1;
nextstate[i][0][1]=-1;
nextpos[i][0][1]=-1;
ST0.change(a[i],dp[i][0],i);
continue;
}
if(temp1.dpval>temp0.dpval)
{
dp[i][0]=temp1.dpval+1;
nextstate[i][0][0]=1;
nextpos[i][0][0]=temp1.minpos;
nextstate[i][0][1]=1;
nextpos[i][0][1]=temp1.maxpos;
}
else if(temp1.dpval<temp0.dpval)
{
dp[i][0]=temp0.dpval+1;
nextstate[i][0][0]=0;
nextpos[i][0][0]=temp0.minpos;
nextstate[i][0][1]=0;
nextpos[i][0][1]=temp0.maxpos;
}
else
{
dp[i][0]=temp0.dpval+1;
if(temp1.minpos<=temp0.minpos)
{
nextstate[i][0][0]=1;
nextpos[i][0][0]=temp1.minpos;
}
else
{
nextstate[i][0][0]=0;
nextpos[i][0][0]=temp0.minpos;
}
if(temp0.maxpos>=temp1.maxpos)
{
nextstate[i][0][1]=0;
nextpos[i][0][1]=temp0.maxpos;
}
else
{
nextstate[i][0][1]=1;
nextpos[i][0][1]=temp1.maxpos;
}
}
ST0.change(a[i],dp[i][0],i);
}
for(int i=1;i<=n;++i)
{
anslen=max(anslen,dp[i][0]);
}
bg0=bg1=-1;
s0=s1=0;
for(int i=1;i<=n;++i)
{
if(dp[i][0]==anslen)
{
if(bg0==-1||bg0>i)bg0=i;
if(bg1==-1||bg1<i)bg1=i;
}
}
A1.clear();
A2.clear();
while(s0!=-1)
{
A1.push_back(bg0);
int ts=nextstate[bg0][s0][0];
int tbg=nextpos[bg0][s0][0];
bg0=tbg;
s0=ts;
}
while(s1!=-1)
{
A2.push_back(bg1);
int ts=nextstate[bg1][s1][1];
int tbg=nextpos[bg1][s1][1];
bg1=tbg;
s1=ts;
}
for(int i=0;i<A1.size();++i)
{
printf("%d%c",A1[i],i==A1.size()-1?'\n':' ');
}
for(int i=0;i<A2.size();++i)
{
printf("%d%c",A2[i],i==A2.size()-1?'\n':' ');
}
}
return 0;
} 
