自动搬运

查看原文

来自洛谷，原作者为

	5ab_juruo May you find some comfort here

搬运于2025-08-24 22:19:52，当前版本为作者最后更新于2023-09-26 12:50:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

设 $\operatorname{highbit}(x)$ 为 $x$ 在二进制下的最高的 $1$ 的位置，$\operatorname{lowbit}(x)$ 为 $x$ 在二进制下的最低的 $1$ 的位置，则 $(r,c)$ 能被 $(x,y)$ 贡献到当且仅当：

• $r$ 在 $\operatorname{highbit}(x)$ 以前的位和 $x$ 相同；
• $c$ 在 $\operatorname{highbit}(y)$ 以前的位和 $y$ 相同。

考虑翻转二进制位，则条件等价于：

• $r'$ 在 $\operatorname{lowbit}(x')$ 以后的位和 $x'$ 相同；
• $c'$ 在 $\operatorname{lowbit}(y')$ 以后的位和 $y'$ 相同。

注意到二进制后缀一致相当于在一段区间内。具体而言为 $[x'-\operatorname{lowbit}(x')+1,x'+\operatorname{lowbit}(x')-1]$，所以直接二维数点即可。

const int max_n = 2e5, max_m = 2e5, max_lgv = 61;

vector<tuple<ll, ll, int, int>> op;
int w[max_n], ans[max_m], tr[max_n * 3 + 1];
vector<ll> b;

ll rev(ll x)
{
	ll res = 0, bs = (1ll << max_lgv);
	while (x)
	{
		bs >>= 1;
		if (x & 1)
			res |= bs;
		x >>= 1;
	}
	return res;
}

pair<ll, ll> cov(ll x)
{
	int d = __lg(x);
	ll rx = rev(x ^ (1ll << d));
	return make_pair(rx + 1, rx + (1ll << (max_lgv - d)));
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, m;
	
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		ll sr, er, sc, ec, r, c;
		cin >> r >> c >> w[i];
		tie(sr, er) = cov(r);
		tie(sc, ec) = cov(c);
		b.push_back(sc), b.push_back(ec);
		op.emplace_back(sr, sc, 1, w[i]);
		op.emplace_back(sr, ec, 1, -w[i]);
		op.emplace_back(er, sc, 1, -w[i]);
		op.emplace_back(er, ec, 1, w[i]);
	}
	for (int i = 0; i < m; i++)
	{
		ll r, c;
		cin >> r >> c;
		r = rev(r), c = rev(c);
		b.push_back(c);
		op.emplace_back(r, c, 2, i);
	}
	sort(all(op));
	
	sort(all(b));
	b.erase(unique(all(b)), end(b));
	
	auto s = [&](ll x) { return lower_bound(all(b), x) - begin(b); };
	
	auto lowbit = [](int x) { return x & -x; };
	auto add = [&](int x, int v) {
		for (x++; x <= ssz(b); x += lowbit(x))
			tr[x] += v;
	};
	auto get = [&](int x) {
		int res = 0;
		for (x++; x; x -= lowbit(x))
			res += tr[x];
		return res;
	};
	
	for (auto [r, c, ty, v] : op)
	{
		if (ty == 1)
			add(s(c), v);
		else
			ans[v] = get(s(c));
	}
	for (int i = 0; i < m; i++)
		cout << ans[i] << "\n";
	
	return 0;
}