HDU - 5324：Boring Class （CDQ分治&树状数组&最小字典序）

题意：给定N个组合，每个组合有a和b，现在求最长序列，满足a不升，b不降。

思路：三位偏序，CDQ分治。   但是没想到怎么输出最小字典序，我好菜啊。

最小字典序： 我们倒序CDQ分治，ans[i]表示倒序的以i为结尾的最长序列，如果当前的ans[i]==目前最大，而且满足序列要求，就输出。

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

int q[maxn],Mx[maxn],x[maxn],y[maxn],b[maxn],tot,ans[maxn],res;

bool cmp(int w,int v){ if(y[w]==y[v]) return w<v;return y[w]<y[v];}

int query(int x){int res=; while(x){ res=max(res,Mx[x]);x-=(-x)&x;} return res;}

void add(int x,int y){while(x<=tot){ Mx[x]=max(y,Mx[x]);x+=(-x)&x; }}

void update(int x){while(x<=tot){ Mx[x]=;x+=(-x)&x;}}

void cdq(int L,int R)

{

    if(L==R) { ans[L]=max(ans[L],); return ;}

    int Mid=(L+R)>>;

    cdq(Mid+,R);

    int num=; rep(i,L,R) q[++num]=i;

    sort(q+,q+num+,cmp);

    for(int i=num;i>=;i--){

        if(q[i]>Mid) add(x[q[i]],ans[q[i]]);

        else ans[q[i]]=max(ans[q[i]],query(x[q[i]])+);

    }

    for(int i=num;i>=;i--)

      if(q[i]>Mid) update(x[q[i]]);

    cdq(L,Mid);

}

int main()

{

    int N;

    while(~scanf("%d",&N)){

        rep(i,,N) Mx[i]=ans[i]=; res=;

        rep(i,,N) scanf("%d",&x[i]),b[i]=x[i];

        rep(i,,N) scanf("%d",&y[i]);

        sort(b+,b+N+);

        tot=unique(b+,b+N+)-(b+);

        rep(i,,N) x[i]=lower_bound(b+,b+tot+,x[i])-b;

        cdq(,N);

        rep(i,,N) res=max(res,ans[i]);

        printf("%d\n",res);

        int X,Y; tot=res;

        rep(i,,N){

            if(ans[i]==tot){

                if(tot==res) {

                    X=x[i]; Y=y[i]; tot--;

                    printf("%d",i);

                }

                else if(x[i]<=X&&y[i]>=Y){

                    X=x[i]; Y=y[i]; tot--;

                    printf(" %d",i);

                }

            }

        }

        puts("");

    }

    return ;

}