题解 | ***入门

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct point{
    int l,r;
    bool operator < (const point &a)const{
        if(l==a.l)return r<a.r;
        return l<a.l;
    }
};
void solve(){
    int n,k,num,ans=0;
    cin>>n>>k;
    map<int,vector<point>> m;
    for(int i=1;i<=k;i++){
        cin>>num;
        int l=0,r=n;
        while(l+1!=r){
            int mid=(l+r)/2;
            if(mid*(mid+1)/2>=num)r=mid;
            else l=mid;
        }
//        cout<<r<<'\n';
        m[r].push_back({num-r*(r-1)/2,num-r*(r-1)/2});
    }
    for(auto i=m.rbegin();i!=m.rend();i++){
        sort(i->second.begin(),i->second.end());
        int layer=i->first;
        vector<point> zhong;
        for(auto j:i->second){
            if(zhong.empty()||j.l>zhong.back().r+1)zhong.push_back(j);
            else zhong.back()={zhong.back().l,max(zhong.back().r,j.r)};
        }
//        cout<<layer<<'\n';
//        for(auto j:zhong){
//            cout<<j.l<<" "<<j.r<<'\n';
//        }
        for(auto j:zhong){
            if(j.r-j.l+1>1){
                m[layer-1].push_back({j.l,j.r-1});
                ans+=j.r-j.l+1;
            }
            else{
                ans+=1;
            }
        }
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _;
    cin>>_;
    while(_--)solve();
    return 0;
}