题解 | #拆迁入门#喵

首先不难发现可以从底向上递推，碰到两个相邻的就把上方的点添加进去喵～这样时间和答案成正比喵～但是答案高达 所以会超时喵～

考虑优化这个模拟喵～一层一层向上推，如果原本是个连续区间推一层这个区间长度会短 喵～长度到小男娘 就会删除喵～

所以可以考虑维护一个珂朵莉树喵～额外存储一个当前长度的有序集合，用于删除过短的连续区间喵～可以记录区间长度改变量，这样就不用每次推一层改整个珂朵莉树喵～同时只要维护一个当前段总长度就可以计算答案喵～

但是这样 还是不行喵～考虑加速这个过程，只在存在的层之间推喵～中间统计答案用等差数列求和公式就可以了喵～注意删除时也要统计喵～

时间复杂度 喵～爱你们喵～

#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <vector>
using namespace std;

using ll = long long;

int n;
int k;
vector<ll> a;

map<ll, ll> cur;
set<pair<int, ll>> intervals;
int curLevel;

ll sumLen;
ll res;

// n * (n - 1) / 2 + 1 <= x

ll Lf(ll x) {
    return x * (x - 1) / 2 + 1;
}

int Level(ll x) {
    int l = 1;
    int r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (x < Lf(mid)) {
            r = mid - 1;
            continue;
        }
        l = mid;
    }
    return l;
}

void Insert(ll x, int level) {
    ll lf = Lf(level);
    ll val = x - lf;
    auto it = cur.upper_bound(val);
    if (it == cur.begin()) {
        it = cur.emplace_hint(cur.begin(), val, val + 1 + (n - level));
        intervals.emplace(1 + (n - level), val);
        sumLen++;
    } else {
        auto lit = prev(it);
        auto& [llf, lrt] = *lit;
        ll rt = lrt - (n - level);
        if (rt > val) {
            return;
        }
        sumLen++;
        if (rt == val) {
            intervals.erase({lrt - llf, llf});
            lrt++;
            intervals.insert({lrt - llf, llf});
            it = lit;
        } else {
            it = cur.emplace_hint(it, val, val + 1 + (n - level));
            intervals.emplace(1 + (n - level), val);
        }
    }
    auto rit = next(it);
    if (rit != cur.end()) {
        auto& [rlf, rrt] = *rit;
        if (val + 1 == rlf) {
            intervals.erase({rrt - rlf, rlf});
            intervals.erase({it->second - it->first, it->first});
            it->second = rrt;
            intervals.insert({rrt - it->first, it->first});
            cur.erase(rit);
        }
    }
}

void DecreaseLevel(int level) {
    while (intervals.size()) {
        auto [len, lf] = *intervals.begin();
        if (len > n - level) {
            break;
        }
        int lastLen = len - (n - curLevel);
        res += (ll)lastLen * (lastLen + 1) / 2;
        sumLen -= lastLen;
        cur.erase(lf);
        intervals.erase(intervals.begin());
    }
    int diff = curLevel - level;
    ll sz = cur.size();
    sumLen -= sz * diff;
    res += sumLen * diff;
    res += sz * ((ll)diff * (diff + 1) / 2);
    curLevel = level;
}

void Solve() {
    cin >> n >> k;
    a.resize(k);
    for (auto& x : a) {
        cin >> x;
    }
    sort(a.begin(), a.end(), greater<>());
    curLevel = n;
    sumLen = 0;
    res = 0;
    for (const auto& x : a) {
        int level = Level(x);
        if (level < curLevel) {
            DecreaseLevel(level);
        }
        Insert(x, level);

    }
    DecreaseLevel(0);
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        Solve();
    }
}