Codeforces 1053 C - Putting Boxes Together

àì夳堔傛蜴生んèń 2021-12-22 08:09 174阅读 0赞

[C - Putting Boxes Together][]

思路：

求带权中位数

用树状数组维护修改

代码：

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #include<bits/stdc++.h>
    using namespace std;
    #define fi first
    #define se second
    #define pi acos(-1.0)
    #define LL long long
    //#define mp make_pair
    #define pb push_back
    #define ls rt<<1, l, m
    #define rs rt<<1|1, m+1, r
    #define ULL unsigned LL
    #define pll pair<LL, LL>
    #define pli pair<LL, int>
    #define pii pair<int, int>
    #define piii pair<pli, int>
    #define mem(a, b) memset(a, b, sizeof(a))
    #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout);
    //head
    
    const int N = 3e5 + 10;
    const int MOD = 1e9 + 7;
    int a[N], w[N], n;
    struct BIT {
        LL bit[N];
        int ty;
        void add(int x, LL a) {
            while(x <= n) {
                if(ty == 0) bit[x] = (bit[x] + a) % MOD;
                else bit[x] = bit[x] + a;
                x += x&-x;
            }
        }
        LL sum(int x) {
            LL res = 0;
            while(x) {
                if(ty == 0)res = (res + bit[x]) % MOD;
                else res = res + bit[x];
                x -= x&-x;
            }
            return res;
        }
    }b1, b2;
    
    void solve (int x, int y) {
        if(x == y) {
            printf("0\n");
            return ;
        }
        int l = x, r = y, m = l+r >> 1;
        LL tot = b1.sum(r) - b1.sum(l-1);
        LL sub = b1.sum(l-1);
        while(l < r) {
            if((b1.sum(m) - sub)*2 >= tot) r = m;
            else l = m+1;
            m = l+r >> 1;
        }
        LL ans = 0, cnt = a[m] - m;
        cnt %= MOD;
        ans = (ans + cnt * ((b1.sum(m) - b1.sum(x-1)) % MOD) % MOD - (b2.sum(m) - b2.sum(x-1))) % MOD;
        ans = (ans - cnt * ((b1.sum(y) - b1.sum(m)) % MOD) % MOD + (b2.sum(y) - b2.sum(m))) % MOD;
        ans = (ans + MOD) % MOD;
        printf("%lld\n", ans);
    
    }
    int main() {
        int q, x, y;
        scanf("%d %d", &n, &q);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
        b1.ty = 1;
        b2.ty = 0;
        for (int i = 1; i <= n; i++) {
            b1.add(i, w[i]);
            b2.add(i, 1LL*w[i]*(a[i]-i));
        }
        while(q--) {
            scanf("%d %d", &x, &y);
            if(x < 0) {
                x = -x;
                b1.add(x, -w[x]);
                b2.add(x, -1LL*w[x]*(a[x]-x));
    
                w[x] = y;
                b1.add(x, w[x]);
                b2.add(x, 1LL*w[x]*(a[x]-x));
            }
            else solve(x, y);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/widsom/p/9742581.html

[C - Putting Boxes Together]: http://codeforces.com/contest/1053/problem/C