不让本地ide调试还是太史了

#米哈游笔试#
T1
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a.begin(),a.end());
    int r2=n+1,r1=n+1;
    int ans=0;
    for(int i=1;i<=n;i++){
        r1--;
        ans+=a[r1];
        if(i%k==0){
            r2--;
            ans+=a[r2];
        }
        cout<<ans<<" ";
    }
    cout<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

T2
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+2),b(n+2),c(n+2);
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        if(c=='A')a[i]++;
        else b[i]++;
        a[i]+=a[i-1];
        b[i]+=b[i-1];
    }
    int ans=0;
    for(int i=n;i>=1;i--)c[i]=max(c[i+1],b[i]+a[n]-a[i]);
    for(int i=0;i<=n;i++){
        // cout<<a[i]+c[i+1]<<" ";
        ans=max(ans,a[i]+c[i+1]-b[i]);
    }
    cout<<n-ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}

T3
#include <bits/stdc++.h>
using namespace std;
int seg[800005];
void build(int id,int l,int r,vector<int>& a){
    if(l==r){
        seg[id]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(id*2,l,mid,a);
    build(id*2+1,mid+1,r,a);
    seg[id]=__gcd(seg[id*2],seg[id*2+1]);
}
int find(int id,int l,int r,int q,int num){
    // cout<<l<<" "<<r<<" "<<seg[id]<<endl;
    if(r<=q){
        int g=__gcd(seg[id],num);
        // cout<<g<<endl;
        if(num==g)return -1;
        if(l==r)return l;
        int mid=(l+r)/2;
        int f=find(id*2+1,mid+1,r,q,num);
        // cout<<f<<endl;
        if(f!=-1)return f;
        return find(id*2,l,mid,q,num);
    }
    int mid=(l+r)/2;
    int f=-1;
    if(q>=mid+1)f=find(id*2+1,mid+1,r,q,num);
    if(f!=-1)return f;
    return find(id*2,l,mid,q,num);
}
void solve(){
    int n;
    cin>>n;
    vector<vector<int>> r(n+2),o(n+2);
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n,a);
    int cur=a[1];
    // cout<<find(1,1,5,3,4);
    for(int i=2;i<=n;i++){
        cur=__gcd(cur,a[i]);
        int q=i-1,g=a[i];
        vector<pair<int,int>> jl;
        // cout<<find(1,1,n,i-1,g)<<" ";
        // int cnt=0;
        while(g!=cur){
            int re=find(1,1,n,q,g);
            if(re==-1)break;
            g=__gcd(g,a[re]);
            // cout<<g<<" "<<cur<<" ";
            // cnt++;
            // if(cnt==100)break;
            jl.push_back({re,g});
        }
        // cout<<cnt<<" ";
        // cout<<endl;
        jl.push_back({0,1});
        for(int j=0;j<jl.size()-1;j++){
            o[jl[j].first].push_back(a[i]-jl[j].second);
            r[jl[j+1].first+1].push_back(a[i]-jl[j].second);
            // cout<<jl[j+1].first+1<<" "<<jl[j].first<<" "<<a[i]-jl[j].second<<endl;
        }
    }
    map<int,int> mp;
    long long ans=0;
    for(int i=1;i<n;i++){
        for(auto num:r[i]){
            mp[num]++;
            // cout<<num<<" ";
        }
        // cout<<endl;
        ans+=mp[a[i]];
        for(auto num:o[i]){
            mp[num]--;
            // cout<<num<<" ";
        }
        // cout<<endl;
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    cin>>T;
    while(T--)solve();
    return 0;
}