题解 | 拆迁入门 | 香模拟 | map 区间合并

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int K = 3e5 + 5;

LL n, k;
LL a[K];

int get_n(LL x) {
    int l = 1, r = n;
    int res = 0;
    while(l<=r) {
        LL mid = l + (r-l)/2;
        if(mid*(mid-1)/2+1<=x) {
            res = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    } 
    return res;
}

void merge(map<int,int>& mp, int l,int r) {
    auto L = mp.lower_bound(l+1), R = mp.upper_bound(r+1);
    if(L!=mp.begin()) {
        L--;
        if(L->second + 1 >= l) l = L->first;
        else L++;
    }
    int tmp = r + 1;
    while(L!=mp.end() && L->first <= tmp) {
        r = max(r, L->second);
        L = mp.erase(L);
    }
    mp[l] = r;
}

void print(map<int,int>& mp) {
    for(auto [l,r]:mp) cout << "[" << l << ", " << r << "] ";
    cout << "\n";
}

void solve() {
    map<int,map<int,int>,greater<int>> mp;
    cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        cin >> a[i];
        LL r = get_n(a[i]);
        LL c = a[i] - r * (r - 1) / 2;
        merge(mp[r], c, c);
        // print(mp[r]);
    }
    LL ans = 0;
    while(mp.size()) {
        auto& [row, S] = *mp.begin();
        // print(S);
        while(S.size()) {
            auto it = S.begin();
            int l = it->first, r= it->second;
            ans += r - l + 1;
            if(l < r) {
                // cout << "merge:" << l << " " << r - 1 << "\n";
                merge(mp[row-1], l, r-1);
            }
            it = S.erase(it);
        }
        mp.erase(mp.begin());
    }
    cout << ans << "\n";
}

int main() {
    // cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
}
// 64 位输出请用 printf("%lld")