题解 | 拆迁入门

将所有被选中的麻将分层处理，从最下面的那一层开始，对于每一层，如果多个麻将连结成了一个线段，那么以这个线段为底的一个金字塔都会被推倒，同时被推倒的这个金字塔有可能和上面的某层的线段形成新的金字塔，我们就可以将金字塔在这一层和上一层之间的部分先加上，再将这个金字塔与上一层的交集插入到上一层的线段中，这样这一层产生的金字塔没计算上的部分 就会在上一层被计算，就可以求出答案

时间复杂度：不知道

#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cout<<#x<<": "<<(x)<<endl;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define int long long
using seg=vector<pair<int,int> >;

void solve(){
    int n,k;cin>>n>>k;
    vector<int> a(k+1);
    for(int i=1;i<=k;i++)cin>>a[i];

    auto get_line_num=[&](int x)->pair<int,int>{
        int l=1,r=n,mid;
        while(l<=r){
            mid=(l+r)>>1;
            if(mid*(mid+1)/2>=x)r=mid-1;
            else l=mid+1;
        }
        return {l,x-l*(l-1)/2};
    };

    map<int,seg> mp;
    for(int i=1;i<=k;i++){
        auto [line,pos]=get_line_num(a[i]);
        mp[line].emplace_back(pos,pos);
    }

    map<int,int> nxt;int last=0;
    for(auto [x,_]:mp){
        nxt[x]=last;
        last=x;
    }

    auto cal_and_push=[&](const pair<int,int>& u,int cur,int tar){
        int ret=0;
        int len=u.second-u.first+1;
        int d=cur-tar;
        if(len<=d){
            return len*(len+1)/2;
        }else{
            ret=len*(len+1)/2;
            int tar_l=u.first,tar_r=u.second-d;
            mp[tar].emplace_back(tar_l,tar_r);
            ret-=(tar_r-tar_l+1)*(tar_r-tar_l+2)/2;
            return ret;
        }
    };

    int ans=0;
    for(auto it=mp.rbegin();it!=mp.rend();it++){
        auto[cur,segments]=*it;
        sort(segments.begin(),segments.end());
        int l=-1,r=-1;
        for(auto [u_l,u_r]:segments){
            if(u_l<=r+1){
                r=max(r,u_r);
            }else{
                if(l!=-1&&r!=-1)ans+=cal_and_push({l,r},cur,nxt[cur]);
                l=u_l,r=u_r;
            }
        }
        ans+=cal_and_push({l,r},cur,nxt[cur]);
    }
    cout<<ans<<endl;
}
signed main() {
    IOS;
    int t;cin>>t;
    while(t--)solve();
    return 0;
}
// 64 位输出请用 printf("%lld")
 //        1
 //       2 3
 //     4  5  6
 //   7  8  9  10
 // 11 12  13 14  15