题解 | 多米诺骨牌

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
void slove() {
    int n, m;
    std::cin >> n >> m;
    std::vector<int> h(n + 1), x(n + 1);
    for (int i = 1; i <= n; i++) std::cin >> h[i];
    std::map<int, int> mp;
    std::vector<std::pair<int, int>> v;
    for (int i = 1; i <= n; i++) {
        std::cin >> x[i];
        mp[x[i]] = 1;
        mp[x[i] + h[i]] = 1;
        v.push_back({x[i], x[i] + h[i]});
    }
    int tot = 1;
    for (auto& i : mp) i.second = tot++;
    std::vector<int> tree(tot + 1, 0);
    auto lowbit = [&](int x)->int{
        return x & -x;
    };
    auto add = [&](int x, int v)->void{
        for (int i = x; i <= tot; i += lowbit(i)) tree[i] += v;
    };
    auto qurey = [&](int x)->int{
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    };
    std::sort(v.begin(), v.end());
    std::vector<std::pair<int, int>> seg;
    int l = 0, r = 0;
    for (auto[x, y] : v) {
        if (l == 0 && r == 0) {
            l = x, r = y;
            continue;
        }
        if (x > r) {
            seg.push_back({l, r});
            l = x, r = y;
        } else {
            l = std::min(l, x);
            r = std::max(r, y);
        }
    }
    seg.push_back({l, r});
    for (int i = 1; i <= n; i++) {
        add(mp[x[i]], 1);
    }
    std::vector<int> ans;
    for (auto[x, y] : seg) {
        ans.push_back(qurey(mp[y]) - qurey(mp[x] - 1));
    }
    std::sort(ans.begin(), ans.end(), std::greater<int>());
    int sum = 0;
    for (auto x : ans) {
        if (m > 0) {
            sum += x;
            m--;
        } else break;
    }
    std::cout << sum << endl;
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T = 1;
    std::cin >> T;
    while (T--)    {
        slove();
    }
    return 0;
}

区间合并板子，最后脑子烧坏了又去写了个树状数组。其实合并的时候就能直接处理出来个数了，属于是糖完了。