题目大意 ??在一个数列ai里依次激活某个位置，求每次激活后的最长上升子序列（LIS）。
思路 ??可以倒着找。
??先找出全部数列的LIS，然后倒着令数列逐位失活，如果失活的那一位在LIS里，就重新找一遍LIS，否则就LIS长度不变。
??现在问题就是，怎么找LIS。
??以前都是直接dp的，这次用树状数组，居然也挺好用的。
??树状数组每个结点在变成树状之前，都表示以那个数字结尾的LIS。树状数组维护前缀最大值。
??每次重构LIS都update每一个未失活的ai。对于每次更新，都先找到它前边的（比它小的数）的最大值，然后自己的长度就为最大值+1，并记录前驱。&因为是逐位添加，所以就保证了顺序。
??记得每次清空鸭~由于每次用到的地方都只会比上次更少，所以只清空这次用了的就够！（话说这样也相当于每次都是空的吧。。）
题解 【树状数组|【HDU6635 Nonsense Time】树状数组维护最长上升子序列】??有极小的改动。。总觉得原来的题解有些地方有点奇怪。。
#include
const int N=50010;
int Case,n,i,x,a[N],b[N],ans[N],pre[N],nxt[N],f[N],g[N],used[N],bit[N];
inline void up(int& a, int b){
if(f[a] < f[b]) a = b;
}
//树状数组求最长上升子序列
inline void build(){
int i,j,k;
for(i = nxt[0];
i <= n+1;
i = nxt[i]){ //i表示数字位置
used[i] = 0;
k = 0;
for(j = a[i];
j;
j -= j&-j)//找到自己前边长度最长的比自己小的
up(k,bit[j]);
f[i] = f[k]+1;
//当前长度为最长的+1
g[i] = k;
//记录前驱
for(j = a[i];
j <= n+1;
j += j&-j)
up(bit[j], i);
//向后更新一遍最大值
}
for(i = nxt[0];
i <= n+1;
i = nxt[i])
for(j = a[i];
j <= n+1;
j += j&-j)
bit[j] = 0;
for(i = n+1;
i;
i = g[i])
used[i] = 1;
}
int main(){
scanf("%d", &Case);
while(Case --){
scanf("%d", &n);
for(i = 1;
i <= n;
i ++)
scanf("%d",&a[i]), a[i] ++;
a[n+1] = n+2;
//每一个都要用长度+1
for(i = 0;
i <= n+1;
i ++)
pre[i] = i-1,
nxt[i] = i+1,
bit[i] = used[i] = 0;
//bit应该是树状数组的本体啦
for(i = 1;
i <= n;
i ++)
scanf("%d", &b[i]);
build();
for(i = n;
i>=1;
i --){
ans[i] = f[n+1]-1;
//总会多算结尾的n+2
x = b[i];
pre[nxt[x]] = pre[x];
//把x处的数字移除
nxt[pre[x]] = nxt[x];
//pre是用来辅助nxt的
if(used[x]) //如果在最长上升子序列里，就重建
build();
}
for(i = 1;
i <= n;
i ++)
printf("%d%c", ans[i],i 推荐阅读
- 并查集|[CF938G] Shortest Path Queries
- Different Integers
- 倍增|191026考试题解
- 圆方树|uoj#189. 【集训队互测2016】火车司机出秦川 //圆方树
- LIS|最长上升子序列（模板）
- 51nod 1376 最长递增子序列的数量 树状数组