[Poi2010]Monotonicity 2

[Poi2010]Monotonicity 2

问题 B: [Poi2010]Monotonicity 2

时间限制: 1 Sec   内存限制: 256 MB
提交: 58   解决: 41
[ 提交][ 状态][ 讨论版]

题目描述

给出N个正整数a[1..N]，再给出K个关系符号（>、<或=）s[1..k]。
选出一个长度为L的子序列（不要求连续），要求这个子序列的第i项和第i+1项的的大小关系为s[(i-1)mod K+1]。
求出L的最大值。

输入

第一行两个正整数，分别表示N和K (N, K <= 500,000)。
第二行给出N个正整数，第i个正整数表示a[i] (a[i] <= 10^6)。
第三行给出K个空格隔开关系符号（>、<或=），第i个表示s[i]。

输出

一个正整数，表示L的最大值。

样例输入

7 3
2 4 3 1 3 5 3
< > =

样例输出

6

提示

选出的子序列为2 4 3 3 5 3，相邻大小关系分别是< > = < >。

Monotonicity2：解析: 
一眼考虑DP，不过这个DP我的确刚开始认为这是没有什么正确性的，然后我就不会辣，但是大家都说这题就是DP.. 
并且好像自己一顿想要构造也没有构造出来不合法的数据? 
那我就只能回到自己刚开始的DP思路了。 
设F[i]表示到第i位拿出来的最长序列长度。 
所以下一个符号显然是确定的。 
然后等于号的话，我们直接开一个数组记录哪一个值上一次出现的可行位置即可。 
小于号，丢到线段树里面，线段树对权值开，记录一段权值区间最大的已出现的f值，查询直接拿最大就好了。 
大于号同理，再开一个线段树丢进去即可。 
F[i]=max(F[j]+1并且i,j满足F[j]对应的大小关系) 
复杂度，查询O(1),插入O(log106) 
最坏O(nlogn)吧 

这个dp乍看不科学，仔细一看更不科学，所以作为一个执着BOY，我决定要造数据卡死波兰人民，但是我造着造着就......证出来了.........

这个就是把 < > =分开讨论每次找到f[i] 即以i为结尾的最长长度，然后一顿转移，那么我们发现如果只是讨论 符号那么由于符号顺序影响 我们的得到的是一个有后效性的dp 就是说我们这个时候找到最优解可能会影响最优解的得到，那么这个dp的正确性是怎样的呢？

证明：

首先我们假设我们找到了一个不是全部从最优转移点转移来的最优序列那么：I.最后一个点一定是从最优转移点转移过来 II. 倒数第二个点，如果不是最优转移点的结果，那么他可以把最后一个点顶掉，并且把自己换成最优转移点     （由于我们一直没有改变最优解，所以我们重复I II 就得到了一个最后两位都是最优解的最优序列） III. 然后我们看中间的点，我们总可以得到一个其之后的点都是由最优转移点转移而来的，那么我们可以把他换成最优转移er，那么得到了一个比原来肿了一点的新序列（我们先留着后面的点），那么现在我们的一串点他们之间都有符号，且他们都满足符号，只是现在不满足那个 s数组的顺序，那么我们发现在这次被操作的那个点的左右一段区间的符号是一样的，那么我们只要在这一段区间内删除掉连续的一段大小为新增长度的序列就可以了，我们从中间一个一个的删，删掉就补到中间来这样连续操作就可以了， 如果 中间那个数两边存在 = 就可以随意删，如果两边符号相同即 < < 或  > > 那么中间的店一定可以删掉 如果是 a<b>c 或 a>b<c 那么删掉b再按照a c 大小删掉左右的某个符号就好了，如果是a c相等那么就任意留一个a或c，那么如果我们现在只能删一个怎么办？如果只剩一个的话那么这个东西就是这段区间里唯一的旮沓了，那么他左右两边的符号一定相等（小证明：我们由于采取两边向中间沦陷的策略所以我们剩的点一定是要删除的区间两个边缘点之一，那么我们考虑这个区间，他一定正好覆盖两个轮回中间的一个轮回，那么边缘之一一定和另一个边缘的左出头一样）

我们重复以上操作可以把这个最优解转化为全部由最优转移点转移而来的最优解，因此要是没有一个不是全部从最优转移点转移来的最优序列那么我们的dp一定是对的如果有那么我们一定有全部由最优转移点转移而来的最优解，因此我们的dp一定可以找到最优解

这个故事告诉我们考场证dp是一个正确的选择.......

#include<iostream> #include<cmath> #include<cstring> #include<cstdio> #include<map> #include<deque> #include<cstdlib> #include<algorithm> #define V 500005 #define LL long long using namespace std; int n,mod; char s[V]; map< int , int >ma; int id; int a[V],f[V],sp[V]; int mx1[V*5],mx2[V*5],mx3[V*5]; inline void U1( int x, int zz, int rt, int l, int r) {     if (l==r)     {       mx1[rt]=max(zz,mx1[rt]);       return ;                  }        int mid=(l+r)/2;     if (x<=mid)U1(x,zz,rt*2,l,mid);     else U1(x,zz,rt*2+1,mid+1,r);     mx1[rt]=max(mx1[rt*2],mx1[rt*2+1]); } inline void U2( int x, int zz, int rt, int l, int r) { //cout<<x<<"  "<<zz<<"  $$"<<rt<<" "<<l<<"  "<<r<<endl;     if (l==r)     {           mx2[rt]=max(zz,mx2[rt]);           return ;                  }        int mid=(l+r)/2;     if (x<=mid)U2(x,zz,rt*2,l,mid);     else U2(x,zz,rt*2+1,mid+1,r);     mx2[rt]=max(mx2[rt*2],mx2[rt*2+1]); } inline void U3( int x, int zz, int rt, int l, int r) { //cout<<x<<" "<<zz<<" %% "<<rt<<" "<<l<<"  "<<r<<endl;     if (l==r)     {           mx3[rt]=max(zz,mx3[rt]);           return ;                  }        int mid=(l+r)/2;     if (x<=mid)U3(x,zz,rt*2,l,mid);     else U3(x,zz,rt*2+1,mid+1,r);     mx3[rt]=max(mx3[rt*2],mx3[rt*2+1]); } inline int Q1( int L, int R, int rt, int l, int r) { //cout<<L<<"  "<<R<<" ^^ "<<rt<<" "<<l<<"  "<<r<<endl;     if (L<=l&&r<=R)     return mx1[rt];       int mid=(l+r)/2;     int ans=0;     if (L<=mid)ans=max(ans,Q1(L,R,rt*2,l,mid));     if (mid<R)ans=max(ans,Q1(L,R,rt*2+1,mid+1,r));     return ans; } inline int Q2( int L, int R, int rt, int l, int r) {     if (L<=l&&r<=R)     return mx2[rt];     int mid=(l+r)/2;     int ans=0;     if (L<=mid)ans=max(ans,Q2(L,R,rt*2,l,mid));     if (mid<R)ans=max(ans,Q2(L,R,rt*2+1,mid+1,r));     return ans; } inline int Q3( int L, int R, int rt, int l, int r) {     if (L<=l&&r<=R)     return mx3[rt];     int mid=(l+r)/2;     int ans=0;     if (L<=mid)ans=max(ans,Q3(L,R,rt*2,l,mid));     if (mid<R)ans=max(ans,Q3(L,R,rt*2+1,mid+1,r));     return ans; } inline int haha() {      //freopen(&#","r",stdin);freopen(&#","w",stdout);      //freopen("mayan.in","r",stdin); freopen("mayan.out","w",stdout);      int k;      cin>>n>>k;      for ( int i=1;i<=n;i++)      {       cin>>a[i];        sp[i]=a[i];           }      sort(sp+1,sp+n+1);      for ( int i=1;i<=n;i++)      {        if (!ma[sp[i]])        ma[sp[i]]=++id;      }      for ( int i=1;i<=n;i++)      a[i]=ma[a[i]];      for ( int j=1;j<=n;j++)      cin>>s[j];      int ll,s1,s2,s3;           for ( int i=1;i<=n;i++)      {           s1=s2=s3=0;         if (a[i]>1)        s1=Q1(1,a[i]-1,1,1,id);        s2=Q2(a[i]+1,id,1,1,id);        if (a[i]<=id)        s3=Q3(a[i],a[i],1,1,id);        ll=max(s1,max(s2,s3));        if (s[ll%k+1]== '<' )        U1(a[i],ll+1,1,1,id);        else if (s[ll%k+1]== '>' )        U2(a[i],ll+1,1,1,id);        else if (s[ll%k+1]== '=' )        U3(a[i],ll+1,1,1,id);      }      int ans=max(Q1(1,id,1,1,id),max(Q2(1,id,1,1,id),Q3(1,id,1,1,id)));      cout<<ans; //<<"  "<<Q1(1,id,1,1,id)<<"  "<<Q2(1,id,1,1,id)<<"  "<<Q3(1,id,1,1,id)<<endl;      return 0; } int gg=haha(); int main() {;}