[APIO2009 convention]平衡树、贪心、2进制步长分解、离散化、字典序、单调性**

【题目】http://wenku.baidu.com/view/079ae6f9aef8941ea76e0599.html

【算法分析】非原创。。。。

首先不考虑字典序，那么就是按r排序，然后贪心取就可以了。

现在考虑字典序。

我们考虑到搞字典序有一个通法，那就是尝试加入某一个点，然后判断结果是否仍可以达到最优，如果是，那么就加进去。否则不加。然后就可以得到一个保证字典序的解了。。。

我们先对data按r排一下序，然后注意到如果一个区间包含另一个区间，那么大区间对判断能否构成最优解必然是没用的。删掉。。。

然后我们就会发现，不只R递增，连L也递增了！

然后设MIS(I,J)表示经过处理以后，第I个区间到第J个区间都可以选用，最多能连成多少个区间。

我们加入一条线段的话，那么就只需要判断是否满足

MIS(pos(preR),pos(L))+MIS(pos(R),pos(nextL))+1==MIS(pos(preR),pos(nextL))就行了。

现在来搞MIS

令right(i)^k=right(right(right(i)))…..(right()出现k次)

那么MIS(i,j)=max(k)   条件：right(i)^k<=j

如果是这样的话，就好搞多了。

我们就像rmq的ST算法一样把right(i)^(2^p)处理出来。

然后从i每次以2^step步长向后走，看什么时候不能走就行了。

因为存在一个性质：

2^0、2^1、2^2、2^3……..2^n

它们能通过每个只用一次的加法组成[1..2^(n+1)-1]这个区间里的任意数。

证明的话很容易，直接把+2^k相当于把二进制的某位数变成1，因为2进制与10进制一一对应，所以必然可以组合成。

纵观所以操作，发现平衡树可以解决。。。于是果断写了SBT。。。

【其它】代码写庛了。。。长达250行

【CODE】

#include #include #include #include using namespace std;
const int N=201111;
const int INF=1000000000;
struct Type{int l,r;}d[N],td[N];
int n,xt,tdn,ans,TOT;
int xl[N+N],lg[N],ansl[N];
int right[N][20];

struct SBTType{
    int tot,root;
    struct PointType{int l,r,s,zz;}tr[N];
   
    void update(int &p){
        if (!p) return;
        tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    }   
   
    void left(int &p){
        int k=tr[p].r;
        tr[p].r=tr[k].l;
        tr[k].l=p;
        update(p);
        update(k);
        p=k;
    }   
   
    void right(int &p){
        int k=tr[p].l;
        tr[p].l=tr[k].r;
        tr[k].r=p;
        update(p);
        update(k);
        p=k;
    }
       
    void repair(int &p){
        if (!p) return;
        bool flag=false;
        if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
          right(p);
          flag=true;
        }   
        if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
            left(tr[p].l);
            right(p);
            flag=true;
        }   
        if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
            left(p);
            flag=true;
        }   
        if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
            right(tr[p].r);
            left(p);
            flag=true;
        }   
        if (flag){
            repair(tr[p].l);
            repair(tr[p].r);
            repair(p);
        }   
    }   
   
    void ins(int &p,int i){
        if (!p){
            p=++tot;
            tr[p].l=0; tr[p].r=0; tr[p].zz=i; update(p);
        }
        else{
            tr[p].s++;
            if (d[tr[p].zz].r                                 else ins(tr[p].l,i);
            repair(p);
        }   
    }   
   
    bool cross(int &p,int l,int r){
        if (!p) return false;
        if (r        if (l>d[tr[p].zz].r) return cross(tr[p].r,l,r);
        return true;
    }
   
    int FindR(int &p,int limit){
        if (!p) return 0;
        if (d[tr[p].zz].r<=limit) return max(d[tr[p].zz].r,FindR(tr[p].r,limit));
        return FindR(tr[p].l,limit);
    }   
   
    int FindL(int &p,int limit){
        if (!p) return INF;
        if (d[tr[p].zz].l>=limit) return min(d[tr[p].zz].l,FindL(tr[p].l,limit));
        return FindL(tr[p].r,limit);
    }   
}sbt;   

void input(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d%d",&d[i].l,&d[i].r);
    lg[1]=0;
    for (int i=2;i<=n;i++)
      lg[i]=lg[i-1]+(i==1<}   

int binary(int x){
    int l=1,r=xt,mid;
    while (l        mid=(l+r)/2;
        if (x<=xl[mid]) r=mid;
                   else l=mid+1;
    }   
    return l;
}   

void LiSan(){
    xt=0;
    for (int i=1;i<=n;i++){
        xl[++xt]=d[i].l;
        xl[++xt]=d[i].r;
    }
    sort(xl+1,xl+xt+1);
    int tot=xt; xt=0;
    for (int i=1;i<=tot;i++)
      if (!xt || xl[xt]!=xl[i])
        xl[++xt]=xl[i];
    for (int i=1;i<=n;i++){
        d[i].l=binary(d[i].l);
        d[i].r=binary(d[i].r);
    }   
}   

bool cmp(Type x,Type y){
    if (x.r    if (x.r>y.r) return false;
    if (x.l>y.l) return true;
    return false;
}   

void init(){
    for (int i=1;i<=n;i++) td[i]=d[i];
    sort(td+1,td+1+n,cmp);
    tdn=0;
    for (int i=1;i<=n;i++)
      if (!tdn || td[i].l>td[tdn].l)
        td[++tdn]=td[i];
}

void getans(){
    ans=1; int R=td[1].r;
    for (int i=2;i<=tdn;i++)
      if (td[i].l>R){
          ans++;
          R=td[i].r;
      }   
}   

void make_right(){
    for (int k=0;1<    for (int i=1;i<=tdn;i++){
        int l=i+1,r=tdn,mid;
        while (l            mid=(l+r)/2;
            if (td[i].r                              else l=mid+1;
        }   
        if (l>tdn || td[i].r>=td[l].l) right[i][0]=tdn+1;
                                  else right[i][0]=l;
    }   
    for (int k=1;1<      for (int i=1;i<=n;i++)
        right[i][k]=right[right[i][k-1]][k-1];
}  

int MIS(int l,int r){
    if (r    int res=1;
    for (int cur=l,step=lg[r-l+1];step>=0;step–)
      if (right[cur][step]<=r){
          res+=1<          cur=right[cur][step];
      }   
    return res;
}  

int Findmax(int x){
    int l=1,r=tdn,mid;
    while (l        mid=(l+r)/2;
        if (td[mid].l>x) r=mid;
                    else l=mid+1;
    }   
    if (td[l].l>x) return l;
    return INF;
}

int Findmin(int x){
    int l=1,r=tdn,mid;
    while (l+1        mid=(l+r)/2;
        if (td[mid].r                    else r=mid-1;
    }   
    if (td[r].r    if (td[l].r    return -INF;
}   

bool Can(int i){
    if (sbt.cross(sbt.root,d[i].l,d[i].r)) return false;
    int L,R,l,r,tmp1=0,tmp2=0;
    L=sbt.FindR(sbt.root,d[i].l-1);
    R=sbt.FindL(sbt.root,d[i].r+1);
    if (!L) L=1;       else L=Findmax(L);
    if (R==INF) R=tdn; else R=Findmin(R);
    l=Findmin(d[i].l);
    r=Findmax(d[i].r);
    tmp1=MIS(L,l);
    tmp2=MIS(r,R);
    if (tmp1+tmp2+1!=MIS(L,R)) return false;
    return true;
}   

void work(){
    for (int i=1;i<=n;i++)
      if (Can(i)){
        sbt.ins(sbt.root,i);
        ansl[++TOT]=i;
      }   
    printf("%dn",ans);
    for (int i=1;i<=ans;i++){
        printf("%d",ansl[i]);
        if (i!=ans) printf(" ");
    }   
    printf("n");
}   

int main(){
    freopen("convention.in","r",stdin);
    freopen("convention.out","w",stdout);
    input();
    LiSan();
    init();
    getans();
    make_right();
    work();
}