P6344 [CCO2017] Vera 与现代艺术

5ab_juruo · 2023-09-26 12:50:03 · 题解

设 \operatorname{highbit}(x) 为 x 在二进制下的最高的 1 的位置，\operatorname{lowbit}(x) 为 x 在二进制下的最低的 1 的位置，则 (r,c) 能被 (x,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;
}