模板汇总 —— 杨式图表

「爱情、让人受尽委屈。」 2021-10-29 11:36 192阅读 0赞

[HDU - 6642][]

使用范围：

求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)来插入某个数的话，其实他的影响还是被原来的那个数给控制的。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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, " \n"[i==n]);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/MingSD/p/11346605.html

[HDU - 6642]: http://acm.hdu.edu.cn/showproblem.php?pid=6642
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/4915bf1f58ae42d5b7cef9073a3548e5.png