Codeforces 1519C.Berland Regional

题目描述：有n个人，给出所属学校和实力值，k个人才能组成一队，每个学校都按照实力值和尽可能大的方法派出队伍，问k从1~n，分别求所有学校所有队伍的实力值和。

把人按照学校分开，实力值从小到大排序做前缀和，对某个学校有m个人，派出的实力值和sum[m]-sum[m%k]。累加进ans[k]即可。
复杂度O(Σ nlogn)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct orz
{
    ll u;
    ll v;
}a[200010];
ll n;
ll sum[200010],ans[200010];
bool my(orz a,orz b)
{
    if(a.u==b.u) return a.v<b.v;
    else return a.u<b.u;
}
void ops(ll l,ll r)
{
    for(ll i=l;i<=r;++i)
    {
        sum[i-l+1]=sum[i-l]+a[i].v;
    }
    ll m=r-l+1;
    for(ll i=1;i<=m;++i)
    {
        ans[i]+=sum[m]-sum[m%i];
    }
}
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(ll i=1;i<=n;++i)
        {
            cin>>a[i].u;
        }
        for(ll i=1;i<=n;++i)
        {
            cin>>a[i].v;
        }
        sort(a+1,a+1+n,my);
        ll k=1;
        for(ll i=1;i<=n;++i)
        {
            while(a[i].u==a[k].u&&k<=n) ++k;
            ops(i,k-1);
            i=k-1;
        }
        for(ll i=1;i<=n;++i)
        {
            cout<<ans[i]<<' ';
            ans[i]=0;
        }
        cout<<endl;
    }
    //getchar();getchar();
    return 0;
}