题解：P9928 [NFLSPC #6] 来点不那么魔怔的题面
abc1234shi
·
·
题解
省流
用树状数组优化 DP，适合有树状数组基础的同学参考。
朴素DP
求长度为 k 的严格上升子序列，其他题解都有介绍，或者把最长上升子序列加个到 k 就跳出循环，总之是枚举两层，第二层找到最大的结尾小于 a_i 的最长上升子序列。
树状数组优化
从小到大枚举，找到结尾小于 a_i 的最长上升子序列，本质就是求出所有小于 a_i 的数值对应的最大 dp 值，这区间最大值，不就可以用树状数组优化了吗？
维护两个函数 qr(x) 与 up(x,y)。
$up(x,y)$ 作用是将树状数组的 $x$ 位置的值更新为 $y$。那么我们更新完 $dp_i$ 后需要再把更新后的值存入树状数组，也就是执行 $up(a_i,dp_i)$。
这样就完成了用树状数组优化 DP 的操作。
# 关键代码
```cpp
void up(int x,int v){
for(;x<=n;x+=x&-x)if(tr[x]<v)tr[x]=v;
}
int qr(int x){
int r=0;
for(;x;x-=x&-x)if(tr[x]>r)r=tr[x];
return r;
}
```