CF782-D Reverse Sort Sum

Reverse Sort Sum

法1：首先可得数组A中的1的总个数，对于\(f(i,A)\)，如果前\(i\)位有\(x\)个1，那么数组C的\([i - x + 1, i]\)区间会+1，所以考虑反向操作，让区间-1，然后从后往前推（每次将Bi的贡献从Ci中删除），然后遍历到\(C_i\)时，如果大于0则\(A_{i}\)为1。区间修改可以利用类似于懒标记删除的东西得到\(O(n)\)做法。

#include
#include

using namespace std;
using ll = long long;

int main()
{
    int T; cin >> T;
    while(T--){
        int n; cin >> n;
        vectora(n + 1), res(n), lazy(n + 1); //类似于懒标记删除
        
        for(int i = 1; i <= n; ++i) cin >> a[i];
        
        ll num = 0;
        for(int i = 1; i <= n; ++i) num += a[i];
        num /= n; // 1的个数
        
        int tmp = 0; // 累计需要扣去的数
        
        for(int i = n; i >= 1 && num; --i) {
            tmp --;
            lazy[i - num] ++;
            tmp += lazy[i];
            if(a[i] + tmp > 0) res[i - 1] = 1, num --;
        }
        
        if(num == 1) res[0] = 1;
        
        for(auto x : res) cout << x << " ";
        cout << endl;
    }
    
    return 0;
}

法2：利用树状数组进行区间修改，思路同法1，\(O(nlogn)\)

#include
#include
#include

using namespace std;
using ll = long long;

int n;
int tr[200010];

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

void add(int x, int v){
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

ll query(int x){
    ll res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
    int T; cin >> T;
    while(T--){
        cin >> n;
        
        memset(tr, 0, sizeof tr);
        
        vectora(n + 1), d(n + 1), res(n);
        
        for(int i = 1; i <= n; ++i) cin >> a[i];
        
        for(int i = 1; i <= n; ++i) d[i] = a[i] - a[i - 1];
        
        for(int i = 1; i <= n; ++i) add(i, d[i]);
        
        ll num = 0;
        for(int i = 1; i <= n; ++i) num += a[i];
        num /= n; // 1的个数
        
        for(int i = n; i >= 1 && num; --i) {
            add(i - num + 1, -1);
            add(i + 1, 1);
            if(query(i)) res[i - 1] = 1, num --;
        }
        
        if(num == 1) res[0] = 1;
        
        for(auto x : res) cout << x << " ";
        cout << endl;
    }
    
    return 0;
}