P4309 [TJOI2013]最长上升子序列

因为求子序列 由题意可知  后面的数对前面的数是无影响的

所以可以先构建出原序列（即最终序列）依次求出他们的前缀和即可

/*
 * @Author: CY__HHH
 * @Date: 2020-10-28 13:17:25
 * @LastEditTime: 2020-10-28 16:33:25
 */
#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
const int LEN = 1e5 + 32;
__gnu_cxx::rope<int> req;
int n, dp[LEN];
struct BinaryIndexedTree{
    int data[LEN];
    inline void update(int idx, int add){
        for(;idx <= n;idx += (idx & -idx))
            data[idx] = max(data[idx], add);
    }
    inline int query(int idx){
        int ans = 0;
        for(;idx;idx-=(idx & -idx))
            ans = max(ans, data[idx]);
        return ans;
    }
}bit;
int main(){
    scanf("%d",&n);
    int pos;
    for(int val = 1;val<=n;++val)   scanf("%d",&pos),req.insert(pos, val);
    for(int i=0,temp;i<n;++i) temp = req[i], bit.update(temp, dp[temp] = bit.query(temp) + 1);
    for(int i=1;i<=n;++i)   printf("%d
",dp[i] = max(dp[i],dp[i-1]));
}