1109: [POI2007]堆积木Klo

树状数组维护序列，使{a[i]-i}不增，且{a[i]}递增。。。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxi=~0u>>1;
int n,ans(0);
int f[200001],t[1000001];
struct re{
    int n,h;
}a[200001];
int lowbit(int x){return x&(-x);}
bool cmp(re a,re b){return a.n==b.n? a.h<b.h:a.n>b.n;}
void change(int x,int c){
    while (x<=n){
        t[x]=max(t[x],c);
        //printf("x=%d t[x]=%d\n",x,t[x]);
        x+=lowbit(x);
    }
}
int ques(int x){
    int ans=0;
    while (x){
        ans=max(ans,t[x]);
        //printf("%d t[x]=%d\n",x,t[x]);
        x-=lowbit(x);
    }
    //printf("ans=%d\n",ans);
    return ans;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i].h);
        a[i].n=a[i].h-i;
        //printf("a[%d]=%d\n",i,a[i].n);
    }
    sort(a+1,a+n+1,cmp);
    for (int i=1;i<=n;i++){
        //printf("i=%d n=%d h=%d\n",i,a[i].n,a[i].h);
        if (a[i].n>0) continue;
        int x;
        if (a[i].h-1>0){
            //printf("%d\n",a[i].h);
            x=ques(a[i].h-1);
        }else x=0;
        //printf("x=%d\n",x);
        f[i]=x+1;
        //printf("f=%d\n",f[i]);
        ans=max(ans,f[i]);
        //printf("f[%d]=%d\n",i,f[i]);
        change(a[i].h,f[i]);
    }
    printf("%d\n",ans);
}