[数据结构与算法]P6588『JROI-1』线段树

题意

传送门 P6588『JROI-1』向量

题解

考虑相邻区间 $A,B$，尝试求解满足 $i\in A,j\in B$ 对叉积的贡献
$$\sum _i\sum _j{a}_i\oplus a_j=\sum _i\sum _j(x_i{y}_j?x_j{y}_i)=\sum _i{x}_i\sum _j{y}_j?\sum _i{y}_i\sum _j{x}_j$$ 对点积的处理同理。线段树维护区间点积与叉积和的同时，维护区间 $x,y$ 的和。总时间复杂度 $O(N\log N)$。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l, _ = r; i < _; ++i)
typedef long long ll;
const int maxn = 100005, sg_size = 1 << 18;
struct node
{
    int sx, sy;
    ll f, g;
} tree[sg_size];
int N, M, X[maxn], Y[maxn];

void up(node &chl, node &chr, node &p)
{
    p.sx = chl.sx + chr.sx, p.sy = chl.sy + chr.sy;
    p.f = chl.f + chr.f + (ll)chl.sx * chr.sx + (ll)chl.sy * chr.sy;
    p.g = chl.g + chr.g + (ll)chl.sx * chr.sy - (ll)chl.sy * chr.sx;
}

void init(int k = 0, int l = 0, int r = N)
{
    if (r - l == 1)
    {
        auto &u = tree[k];
        u.sx = X[l], u.sy = Y[l], u.f = u.g = 0;
        return;
    }
    int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1;
    init(chl, l, m), init(chr, m, r);
    up(tree[chl], tree[chr], tree[k]);
}

void change(int a, int op, int x, int y, int k = 0, int l = 0, int r = N)
{
    if (r - l == 1)
    {
        auto &u = tree[k];
        if (op == 3)
            u.sx *= x, u.sy *= x;
        else
            u.sx += x, u.sy += y;
        return;
    }
    int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1;
    if (a < m)
        change(a, op, x, y, chl, l, m);
    if (m <= a)
        change(a, op, x, y, chr, m, r);
    up(tree[chl], tree[chr], tree[k]);
}

node ask(int a, int b, int k = 0, int l = 0, int r = N)
{
    if (a <= l && r <= b)
        return tree[k];
    int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1;
    if (b <= m)
        return ask(a, b, chl, l, m);
    if (m <= a)
        return ask(a, b, chr, m, r);
    node res, rl = ask(a, b, chl, l, m), rr = ask(a, b, chr, m, r);
    up(rl, rr, res);
    return res;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> M;
    rep(i, 0, N) cin >> X[i] >> Y[i];
    init();
    while (M--)
    {
        int op, i, x, y, t, l, r;
        cin >> op;
        if (op == 1 || op == 2)
            cin >> i >> x >> y, change(i - 1, op, op == 1 ? x : -x, op == 1 ? y : -y);
        else if (op == 3)
            cin >> i >> t, change(i - 1, op, t, 0);
        else if (op == 4 || op == 5)
        {
            cin >> l >> r;
            auto t = ask(l - 1, r);
            cout << (op == 4 ? t.f : t.g) << '\n';
        }
    }
    return 0;
}