题解 P6309

Jsxts_ · 2021-11-09 21:06:46 · 题解

树状数组写法，两只 \log 跑到最优解。

这是一个类似货仓选址的问题，对于每个询问，我们求出整个区间一共住着多少人 s，然后二分或倍增找到第 \lfloor \frac{s}{2}\rfloor 个人住哪间房，选那个房子建避难所，注意要先离散化坐标。

那么怎么统计答案呢？

设避难所的位置为 z，则在 z 前面的房屋的贡献是 v_i\times(z-x_i)，同理在 z 后面的房屋的贡献是 v_i\times(x_i-z)。把括号展开得到总贡献为

所以我们只需要维护区间 v_i 和 v_i\times x_i 的和，单点修改，开两个树状数组即可。

代码很短，只有 60 多行。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
    int s = 0,f = 1;
    char ch = getchar();
    while (!isdigit(ch)) f = ch == '-' ? -1 : 1, ch = getchar();
    while (isdigit(ch)) s = s * 10 + ch - '0', ch = getchar();
    return s * f;
}
ll c[900010],c2[900010];//维护vi,vixi的和 
int x[300010],v[300010],h[1200010],n,m,tot;
void upd(int x,int s,int ss) {
    for (;x <= tot;x += (x & -x)) c[x] += s, c2[x] += 1ll * s * ss;
}
ll getsum(int x) {
    ll res = 0;
    for (;x;x -= (x & -x)) res += c[x];
    return res;
}
ll getsum2(int x) {
    ll res = 0;
    for (;x;x -= (x & -x)) res += c2[x];
    return res;
}
struct ask {
    int op,l,r,x;
}q[300010];
int main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i ++ ) x[i] = read(), h[++tot] = x[i];
    for (int i = 1;i <= n;i ++ ) v[i] = read();
    for (int i = 1;i <= m;i ++ ) {//离线离散化 
        q[i].op = read(), q[i].l = read(), q[i].r = read();
        if (q[i].op == 2) q[i].x = read(), h[++tot] = q[i].r;
        else h[++tot] = q[i].l, h[++tot] = q[i].r;
    }
    sort(h+1,h+tot+1);
    tot = unique(h+1,h+tot+1)-h-1;
    for (int i = 1;i <= n;i ++ ) {
        x[i] = lower_bound(h+1,h+tot+1,x[i]) - h;
        upd(x[i],v[i],h[x[i]]);
    }
    for (int i = 1;i <= m;i ++ ) {
        if (q[i].op == 2) {
            q[i].r = lower_bound(h+1,h+tot+1,q[i].r) - h;
            int t = q[i].l;
            upd(x[t],-v[t],h[x[t]]);//直接单点修改 
            x[t] = q[i].r, v[t] = q[i].x;
            upd(x[t],v[t],h[x[t]]);
        }
        else {
            q[i].r = lower_bound(h+1,h+tot+1,q[i].r) - h;//离散 
            q[i].l = lower_bound(h+1,h+tot+1,q[i].l) - h;
            ll t = getsum(q[i].l-1),s = getsum(q[i].r) - t >> 1;
            int l = q[i].l - 1;
            for (int j = 1 << 19;j;j >>= 1)//倍增找到第s/2个人住的房子 
                l += (l + j <= q[i].r && getsum(l + j) - t <= s) * j;
            l ++;
            printf("%lld\n",(getsum(l) - t) * h[l] - getsum2(l) + getsum2(q[i].l-1) - (getsum(q[i].r) - getsum(l)) * h[l] + getsum2(q[i].r) - getsum2(l));
            //直接套式子
        }
    }
    return 0;
}

线段树二分好像是一个 \log，但我懒得写（