bzoj3173: [Tjoi2013]最长上升子序列(树状数组+二分倒推)

3173: [Tjoi2013]最长上升子序列

题目：传送门

---

题解：

　　 好题！

　　 怎么说吧...是应该扇死自己...看错了两次题：

　　 每次加一个数的时候，如果当前位置有数了，是要加到那个数的前面，而不是直接替代ORZ

　　 那么我们可以用二分倒推出最终数列，顺便记录位置

　　 那么最后问题就变成给你一列数，nlogn求最长上升子序列啦

---

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int n;

 int a[],s[];

 int lowbit(int x){return x&-x;}

 void change_max(int x,int p){while(x<=n)s[x]=max(s[x],p),x+=lowbit(x);}

 void change_sum(int x){while(x<=n)s[x]++,x+=lowbit(x);}

 int find_max(int x){int ans=;while(x)ans=max(ans,s[x]),x-=lowbit(x);return ans;}

 int find_sum(int x){int ans=;while(x)ans+=s[x],x-=lowbit(x);return ans;}

 int main()

 {

     scanf("%d",&n);for(int i=;i<=n;i++)scanf("%d",&a[i]),a[i]++;//位置++

     for(int i=n;i>=;i--)//倒推位置

     {

         int l=,r=n;

         while(l<r)

         {

             int mid=(l+r)/;//二分位置

             int cnt=mid-find_sum(mid);//看一下当前位置前面已经有多少个数了

             if(cnt<a[i])l=mid+;//因为如果有重复的话是放在前面，所以是小于号

             else r=mid;

         }

         a[i]=l;change_sum(a[i]);

     }

     memset(s,,sizeof(s));

     int ans=;

     for(int i=;i<=n;i++)

     {

         int cnt=find_max(a[i])+;//算上自己就要加 1

         change_max(a[i],cnt);

         ans=max(ans,cnt);

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

     }

     return ;

 }