UESTC 1501 - Defense Lines 이산화 + 세그먼트 트리 최적화 DP

제목:
일렬 N 개수를 줬어요. (N<=200000)...이제 연속된 부분을 삭제할 수 있습니다.최장 상승자 꼬치 몇이냐고...
문제 풀이:
dp[p][state]로...state=0은 p로 끝나는 연속열의 최장 상승 서브열이 얼마인지를 나타낸다.state=1은 p로 끝나는 부분의 가장 긴 상승 문자열이 얼마인지를 나타낸다..
state=0 때는 유지보수가 잘 돼서...전 위치의 상태와만 관련이 있는데..
state=1 때...두 가지 상황으로 나뉘어 보면...하나 앞에는 이미 한 토막이 가져갔는데...그래서 이제 계속 이어서...이 업데이트는 위와 같은...다른 하나는 현재 이 위치의 앞부분이 비어 있다는 것이다.여기는 줄기 나무로 그것보다 작은 최장 연속 상승 서브열이 얼마나 되는지 빨리 찾아야 하는데..
주의해야 할 것은 수의 범위가 N보다 훨씬 크다는 것이다.그래서 이산화로 공간을 최적화하는...
 
Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
#include <stack>
#include<queue>
#include<algorithm>
#include<cmath>
#define oo 1000000007
#define ll long long
#define pi acos(-1.0)
#define MAXN 300005 
using namespace std;   
int dp[MAXN][2],P[MAXN<<2];
void update(int t,int l,int r,int x,int now)
{
      if (l==r) 
      {
            P[now]=max(P[now],x);
            return;
      }
      int mid=l+r>>1;
      if (t<=mid) update(t,l,mid,x,now<<1);
      if (t>mid)  update(t,mid+1,r,x,now<<1|1);
      P[now]=max(P[now<<1],P[now<<1|1]);
}
int query(int L,int R,int l,int r,int now)
{
      if (L<=l && R>=r) return P[now];
      int ans=0,mid=l+r>>1;
      if (L<=mid) ans=max(ans,query(L,R,l,mid,now<<1));
      if (R>mid)  ans=max(ans,query(L,R,mid+1,r,now<<1|1));
      return ans;
}
int D[MAXN],A[MAXN];
int Bsearch(int x,int n)
{
      int l=0,r=n+1,mid;
      while (r-l>1)
      {
             mid=l+r>>1;
             if (D[mid]>x) r=mid;
                      else l=mid;
      }
      return l;
}
int main()
{       
      int cases,i,n,x,ans; 
      scanf("%d",&cases);
      while (cases--)
      { 
              scanf("%d",&n);
              for (i=1;i<=n;i++) scanf("%d",&A[i]),D[i]=A[i];
              sort(D+1,D+1+n);
              memset(dp,0,sizeof(dp));
              memset(P,0,sizeof(P));
              ans=0;
              for (i=1;i<=n;i++)
              {
                      x=Bsearch(A[i],n);
                      if (A[i]>A[i-1])
                               dp[i][0]=dp[i-1][0]+1,dp[i][1]=dp[i-1][1]+1;
                         else  dp[i][0]=dp[i][1]=1;
                      update(x,0,n,dp[i][0],1);
                      dp[i][1]=max(dp[i][1],query(0,x-1,0,n,1)+1);
                      ans=max(ans,max(dp[i][0],dp[i][1]));                      
              } 
              printf("%d
",ans);
      } 
      return 0;
}