自动搬运

查看原文

来自洛谷，原作者为

	Jsxts_ [憨笑]

搬运于2025-08-24 22:19:33，当前版本为作者最后更新于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)$。把括号展开得到总贡献为

$$\left(\sum_l^{z-1}v_i-\sum_{z+1}^rv_i\right)\times z+\left(-\sum_l^{z-1}v_ix_i+\sum_{z+1}^rv_ix_i\right) $$

所以我们只需要维护区间 $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$，但我懒得写（