使用范围：
求k个不相交的子序列最大值之和。
用法：
开k个map， 每次对于新的一个v，我们插入 v 个 v 到第一层中。
插入方式：
1.如果没有数比这个v大， 我们就直接将v放入到该层。
2.否则大于v的最小的数x，用v来替换x，将x插入下一层。
因为不能一个一个插入，所以用map来一起插入。
最后答案就是所有表内的元素个数之和。
复杂度为(2^knlog(n))
原理(口胡版）：
首先考虑，用数组直接求LIS问题，我们数组的最后其实并不一定是一个LIS，我们只是求出了一个最易于后续扩张的数组。
对于杨表来讲，其实也一样，我们其实并没有保证了他的一个表内的数组完全是合法的，我们也一样找到了一个最易于后续扩张的一个数组。
对于贡献来讲， 我们一开始其实在插入数的时候，就已经把贡献给算完了，只有这个数的所有数都被其他数删除的时候，他对答案才不会有影响。
考虑 1 7 5 5 这个序列，且只有一层的杨表。
我们插入1 7之后， 表内为 1 7777777.
然后我们插入一个5， 表内为 1 5555577.
我们可以发现在这个过程中，还是由7对答案产生的一个影响。
我们再插入一个5，表内为 1 5555555 555.
我们就发现答案会加上3。
总结的话，也就是说，我们一旦成功(插入方式1)的插入某个数，我门就会对答案产生影响， 但是如果我们使用替换(插入方式2)来插入某个数的话，其实他的影响还是被原来的那个数给控制的。
#include<bits/stdc++.h> using namespace std; #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); #define LL long long #define ULL unsigned LL #define fi first #define se second #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lch(x) tr[x].son[0] #define rch(x) tr[x].son[1] #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; const int inf = 0x3f3f3f3f; const int _inf = 0xc0c0c0c0; const LL INF = 0x3f3f3f3f3f3f3f3f; const LL _INF = 0xc0c0c0c0c0c0c0c0; const LL mod = (int)1e9+7; const int N = 2e5 +100; map<int, LL> mp[5]; const int k = 5; LL ans = 0; void Insert(int v, int num, int id){ if(id == k){ return ; } map<int, LL>::iterator it; while(num){ it = mp[id].upper_bound(v); if(it == mp[id].end()) { ans += num; mp[id][v] += num; num = 0; } else { int mn = min((LL)num, it->se); it->se -= mn; if(it->se == 0) mp[id].erase(it); Insert(it->fi, mn, id+1); mp[id][v] += mn; num -= mn; } } } int main(){ int T; scanf("%d", &T); while(T--){ int n; for(int i = 0; i < 5; ++i) mp[i].clear(); scanf("%d", &n); ans = 0; for(int i = 1, v; i <= n; ++i){ scanf("%d", &v); Insert(v, v, 0); printf("%lld%c", ans, " "[i==n]); } } return 0; }