题解：P6588 『JROI-1』 向量

HHZZLL · 2025-03-28 21:02:18 · 题解

显然这题可以用线段树维护。

那么对于前 3 个操作，即是单点修改，较为简单。

思考一下 4,5 操作怎么做。也就是左右两儿子的信息怎么合并。

假设可以直接维护 4,5 操作所要的答案，其实是可以维护的。

记为 s_1,s_2。

考虑现在左右儿子贡献为：

左区间对应 [l,mid]，右区间对应 (mid,r]。

操作 4:

当你合并他们时，是 x 加它所对应的部分，y 也同理。

所以我们考虑清楚一个那另一个也会了。这里我们考虑 x。

左儿子区间的点 i 需要加 x_i(x_{mid+1}+x_{mid+2}+\cdots+x_{r-1}+x_r)(i\in[l,mid])，再根据乘法结合律，所以就是 s_1 = s_{1_{RS}}+s_{1_{LS}} + \sum_{i=l}^{mid}x_i \times \sum_{i=mid+1}^r x_i。

发现还需要用到区间 x,y 和，顺便维护。

操作 5:

由于前面已经维护了 x,y 和。

这里记作 sX,sY。

对于 x，那么 i 加上 x_i(y_{mid+1}+y_{mid+2}+\cdots+y_{r-1}+y_{r})(i\in[l,mid])，y 也同理，只不过前面有负号。

所以，s_2=s_{2_{RS}}+s_{2_{LS}}+sX_{LS}\times sY_{RS}-sY_{LS}\times sX_{RS}。

现在我们就完成了合并。

在求解答案时，应是找到完全相等区间，再用上述步骤合并。

AC CODE:

#include <bits/stdc++.h>
#define int long long
namespace My {
    #define X first
    #define Y second
    #define vec vector
    #define p_b push_back
    #define rep(i, a, b) for(int i = a; i <= b; i++)
    #define lop(i, b, a) for(int i = b; i >= a; i--)
} using namespace My;
const int N = 1e5 + 5;
int n, m;
struct Vector {
    int x, y;
    Vector operator * (int lambda) {
        return {lambda * x, lambda * y};
    }
    friend Vector operator + (const Vector &a, const Vector &b) {
        return {a.x + b.x, a.y + b.y};
    }
    friend Vector operator - (const Vector &a, const Vector &b) {
        return {a.x - b.x, a.y - b.y};
    }
    friend int operator * (const Vector &a, const Vector &b) {
        return a.x * b.x + a.y * b.y;
    }
    friend int operator ^ (const Vector &a, const Vector &b) {
        return a.x * b.y - b.x * a.y;
    }
} c[N];
namespace SegmentTree {
#define ls k << 1
#define rs k << 1 | 1
    struct State {
        int l, r;
        int sX, sY;
        int sum1, sum2;
        bool operator ! () const {
            return !l && !r && !sX && !sY && !sum1 && !sum2;
        }
        friend State operator + (const State &Ls, const State &Rs) { // 合并
            State up;
            up.l = Ls.l, up.r = Rs.r;
            up.sX = Ls.sX + Rs.sX;
            up.sY = Ls.sY + Rs.sY;
            up.sum1 = Ls.sum1 + Rs.sum1 + Rs.sX * Ls.sX + Rs.sY * Ls.sY;
            up.sum2 = Ls.sum2 + Rs.sum2 + Rs.sY * Ls.sX - Rs.sX * Ls.sY;
            return up;
        }
    } tr[N << 2], ans;
    void pushup(int k) {
        tr[k] = tr[ls] + tr[rs];
    }
    void build(int k, int l, int r) {
        tr[k].l = l, tr[k].r = r;
        if(l == r) {
            tr[k].sX = c[l].x, tr[k].sY = c[l].y; // 一个单点是一个向量
            return;
        }
        build(ls, l, (l + r) / 2), build(rs, (l + r) / 2 + 1, r);
        pushup(k);
    }
#define l tr[k].l
#define r tr[k].r
#define mid (l + r) / 2
    void alter(int k, int p, Vector v, int op) {
        if(l == r && l == r) {
            c[l] = (op == -1 ? c[l] - v : c[l] + v);
            tr[k].sX += op * v.x, tr[k].sY += op * v.y;
            return;
        }
        p <= mid ? alter(ls, p, v, op) : alter(rs, p, v, op);
        pushup(k);
    }
    void cover(int k, int p, int lambda) {
        if(l == r && l == p) {
            c[l] = c[l] * lambda;
            tr[k].sX *= lambda, tr[k].sY *= lambda;
            return;
        }
        p <= mid ? cover(ls, p, lambda) : cover(rs, p, lambda);
        pushup(k);
    }
    void query(int k, int x, int y) {
        if(x == l && r == y) { // 完全相等区间
            if(!ans) ans = tr[k];
            else ans = ans + tr[k];
            return;
        }
        if(y <= mid) query(ls, x, y);
        else if(x > mid) query(rs, x, y);
        else query(ls, x, mid), query(rs, mid + 1, y);
    }
#undef l
#undef r
} using namespace SegmentTree;
signed main() {
    rd(n, m);
    rep(i, 1, n) c[i] = {rd(), rd()};
    build(1, 1, n);
    for(int op, i, x, y; m--;) {
        rd(op);
        if(op <= 2) {
            rd(i, x, y);
            alter(1, i, (Vector){x, y}, op == 1 ? 1 : -1);
        }
        else if(op == 3) {
            rd(i, x);
            cover(1, i, x);
        }
        else {
            rd(x, y), ans = {0, 0, 0, 0, 0, 0};
            query(1, x, y);
            wr(op == 4 ? ans.sum1 : ans.sum2, '\n');
        }
    }
    return 0;
}