Codeforces Round #782 (Div. 2)-D. Reverse Sort Sum

传送门：https://codeforces.com/contest/1659/problem/D

思路：树状数组，参考https://blog.csdn.net/weixin_46870692/article/details/124280729

• 利用 sum{ci}/n可求出 1 的数量 m
  
• B矩阵右上三角形的值为a[i]的原始值，考虑用来构建a[i]
• 对于Bi来说，若前 i 项有 m 个1，那么 从 [i-m+1,i]处都是1
• 用末尾 n到1构建，对于 a[i], 右上角形的 a[i]有 n-(n-i+1) 个 , 而 下三角对其构成的影响为 Bi 到 Bn 的
  i 处的1总数x，这个可以通过树状数组每次更新查询，a[i]=(c[i]-x)/(n-(n-i+1))​, 同时更新m -=a[i]

code:

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<map>
using namespace std;
typedef long long LL;
typedef pair<int,int> pr;

const int MAX_N=2e5+5;
int n,m,T;
int d[MAX_N];
int C[MAX_N],cn;
int res[MAX_N];

int lowbit(int x);
void update(int id,int x);
int query(int id);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin>>T;
    while(T--){
        cin>>n;
        cn=n;
        LL sum=0;
        for(int i=1;i<=n;++i)
        {
            cin>>d[i];
            sum+=d[i];
            C[i]=0;
        }
        m=sum/n;
        for(int i=n,j=1;i>1;++j,--i)
        {
            update(i-m+1,1);
            res[i]=(d[i]-query(i))/(n-j);
            m-=res[i];
        }
        res[1]=m;
        for(int i=1;i<n;++i)
            cout<<res[i]<<" ";
        cout<<res[n]<<endl;
    }

	return 0;
}

int lowbit(int x){
    return x&(-x);
}

void update(int id,int x){
    while(id<=cn){
        C[id]+=x;
        id+=lowbit(id);
    }
}

int query(int id){
    int res=0;
    while(id>0){
        res+=C[id];
        id-=lowbit(id);
    }
    return res;
}