电子速度

GitHub跳转原题关系图返回列表

把叉积平方和展开成 (Σx²)(Σy²)−(Σx·y)²,用树状数组同时维护三个分量,单点改速度与区间询问都是 O(log n)。

OJ: roj

题目 ID: 1741

难度:提高

标签:树状数组前缀和数学python

创建: 2026-10-07 20:34

更新: 2026-10-07 20:34

形式化题目

平面上有 nn 个电子,第 ii 个电子的速度是向量 vi=(xi,yi)v_i = (x_i, y_i),其中 0⩽xi,yi<201709270 \leqslant x_i, y_i < 20170927。 "飘升系数"定义为

∑1⩽i<j⩽n∣vi×vj∣2.\sum_{1 \leqslant i < j \leqslant n} \bigl|v_i \times v_j\bigr|^2 .

需要支持 mm 次操作,共两种:

  • 修改:给定 p,x,yp, x, y,把 vpv_p 改成 (x,y)(x, y);
  • 询问:给定 l⩽rl \leqslant r,求 ∑l⩽i<j⩽r∣vi×vj∣2\displaystyle\sum_{l \leqslant i < j \leqslant r} \bigl|v_i \times v_j\bigr|^2 对 2017092720170927 取模的值。

约束:1⩽n,m⩽1061 \leqslant n, m \leqslant 10^6,1⩽p⩽n1 \leqslant p \leqslant n,1⩽l⩽r⩽n1 \leqslant l \leqslant r \leqslant n。

正解

思路

先把被求的量化开。平面向量叉积只有 zz 分量,∣vi×vj∣=xiyj−xjyi|v_i \times v_j| = x_i y_j - x_j y_i,于是

∑i<j(xiyj−xjyi)2=∑i<jxi2yj2+∑i<jxj2yi2−2∑i<jxixjyiyj=∑i≠jxi2yj2−2∑i<j(xiyi)(xjyj). \begin{aligned} \sum_{i<j} (x_i y_j - x_j y_i)^2 &= \sum_{i<j} x_i^2 y_j^2 + \sum_{i<j} x_j^2 y_i^2 - 2\sum_{i<j} x_i x_j y_i y_j \\ &= \sum_{i \neq j} x_i^2 y_j^2 - 2\sum_{i<j} (x_i y_i)(x_j y_j). \end{aligned}

第一个和式是"有序对"求和,可以拆成全体减对角:

∑i≠jxi2yj2=(∑ixi2)(∑jyj2)−∑ixi2yi2.\sum_{i \neq j} x_i^2 y_j^2 = \Bigl(\sum_i x_i^2\Bigr)\Bigl(\sum_j y_j^2\Bigr) - \sum_i x_i^2 y_i^2 .

第二个和式同理,∑i<jaiaj=12[(∑ai)2−∑ai2]\sum_{i<j} a_i a_j = \frac{1}{2}\bigl[(\sum a_i)^2 - \sum a_i^2\bigr],其中 ai=xiyia_i = x_i y_i,代回去正好把 ∑xi2yi2\sum x_i^2y_i^2 抵消:

 ∑i<j(xiyj−xjyi)2=(∑ixi2)(∑jyj2)−(∑ixiyi)2 \boxed{\ \sum_{i<j} (x_i y_j - x_j y_i)^2 = \Bigl(\sum_i x_i^2\Bigr)\Bigl(\sum_j y_j^2\Bigr) - \Bigl(\sum_i x_i y_i\Bigr)^2\ }

这一步是整个解法的关键:它把"两两配对"的二次代价降成了三个可加的量。对任意一个下标集合 SS(特别地,S=[l,r]S = [l, r]),

answer(S)=P(S)⋅Q(S)−R(S)2,P=∑i∈Sxi2,Q=∑i∈Syi2,R=∑i∈Sxiyi.\text{answer}(S) = P(S) \cdot Q(S) - R(S)^2, \qquad P = \sum_{i \in S} x_i^2,\quad Q = \sum_{i \in S} y_i^2,\quad R = \sum_{i \in S} x_i y_i .

于是问题变成"三个可加量的区间和":单点修改只会同时改变 P,Q,RP, Q, R 各一处,区间和用前缀和相减得到。

前缀和带单点修改 —— 树状数组。三棵树分别维护 P,Q,RP, Q, R,但三个量的修改点和查询点完全一致, 所以合并成一棵树、每个结点同时存三个分量即可:单次修改/询问都是 O(log⁡n)O(\log n)。

取模细节。树内每个结点的每个分量恒保存在 [0,MOD)[0, \mathrm{MOD}):加法后若 ⩾MOD\geqslant \mathrm{MOD} 减一次即可 (两个 <MOD< \mathrm{MOD} 的数相加 <2MOD<231< 2\mathrm{MOD} < 2^{31},不会溢出)。前缀查询把 ⩽log⁡2n+1=21\leqslant \log_2 n + 1 = 21 个这样的值相加,总量 <21⋅MOD≈4.2×108< 21 \cdot \mathrm{MOD} \approx 4.2 \times 10^8,仍在 long long 内,最后统一取模。 单点修改时增量取 (新−旧) mod MOD(\text{新} - \text{旧}) \bmod \mathrm{MOD} 归一到非负;答案 P⋅Q−R2P \cdot Q - R^2 中 P⋅Q<MOD2≈4.07×1014P \cdot Q < \mathrm{MOD}^2 \approx 4.07 \times 10^{14},long long 精确,最后调整符号到 [0,MOD)[0, \mathrm{MOD})。

注意区间内 P,Q,RP, Q, R 也是"先取模再相乘"的:恒等式两边都是整数,模运算与乘法可交换,结论不变。

代码

Python 短解法(同一算法,树状数组用三个列表):

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 20:34
# update_at: 2026-10-07 20:34

import sys

MOD = 20170927  # 题面要求的模数

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Tree = list[int]          # 树状数组:只维护「Σx² / Σy² / Σx·y」里的某一个分量
type Vel = list[tuple[int, int]]  # 每个电子当前的速度 (x, y)


def add(tree: Tree, pos: int, val: int) -> None:
    """树状数组单点加:把 val(已归一到 [0, MOD))加到下标 pos 上。"""
    size = len(tree) - 1
    while pos <= size:
        tree[pos] = (tree[pos] + val) % MOD
        pos += pos & -pos


def prefix(tree: Tree, pos: int) -> int:
    """树状数组前缀和:前 pos 个电子的该分量之和(对 MOD 取模)。"""
    total = 0
    while pos > 0:
        total += tree[pos]
        pos -= pos & -pos
    return total % MOD


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    # 三个分量各开一棵树状数组,下标 1..n;vel 记录速度以便算单点增量
    sums = [[0] * (n + 1) for _ in range(3)]  # 依次为 Σx²、Σy²、Σx·y
    ta, tb, tc = sums
    vel: Vel = [None] * (n + 1)

    for i in range(1, n + 1):
        x, y = next(data) % MOD, next(data) % MOD
        vel[i] = (x, y)
        add(ta, i, x * x % MOD)
        add(tb, i, y * y % MOD)
        add(tc, i, x * y % MOD)

    out: list[str] = []
    for _ in range(m):
        op = next(data)
        if op == 1:
            p, x, y = next(data), next(data) % MOD, next(data) % MOD
            ox, oy = vel[p]
            # 单点改速度:三个分量各自只有一处变化,增量先归一到 [0, MOD)
            add(ta, p, (x * x - ox * ox) % MOD)
            add(tb, p, (y * y - oy * oy) % MOD)
            add(tc, p, (x * y - ox * oy) % MOD)
            vel[p] = (x, y)
        else:
            l, r = next(data), next(data)
            # 区间和 = 前缀和相减;三个分量分别是 Σx²、Σy²、Σx·y
            px = (prefix(ta, r) - prefix(ta, l - 1)) % MOD
            py = (prefix(tb, r) - prefix(tb, l - 1)) % MOD
            pr = (prefix(tc, r) - prefix(tc, l - 1)) % MOD
            # Σ_{i<j} (x_i·y_j − x_j·y_i)² = (Σx²)(Σy²) − (Σx·y)²
            ans = (px * py - pr * pr) % MOD
            out.append(ans)

    if out:
        sys.stdout.write("\n".join(map(str, out)) + "\n")


if __name__ == "__main__":
    solve()

C++ 正解(三个分量合并到一棵树状数组,配手写快读快写以承受 n,m=106n, m = 10^6):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 20:34
 * update_at: 2026-10-07 20:34
 */

// 1741《电子速度》
// 题意:n 个电子,第 i 个的速度 v_i = (x_i, y_i)。
//   操作 1 p x y:把 v_p 改成 (x, y);
//   操作 2 l r :询问 Σ_{l≤i<j≤r} |v_i × v_j|² mod 20170927。
//
// 关键恒等式(叉积平方对求和可以完全展开):
//   Σ_{i<j} (x_i·y_j − x_j·y_i)²
//     = (Σ x²)·(Σ y²) − (Σ x·y)²
// 证明:左边 = Σ_{i<j} x_i²y_j² + Σ_{i<j} x_j²y_i² − 2Σ_{i<j} x_ix_jy_iy_j
//            = Σ_{i≠j} x_i²y_j² − 2Σ_{i<j} (x_iy_i)(x_jy_j)
//            = [ (Σx²)(Σy²) − Σx_i²y_i² ] − [ (Σxy)² − Σx_i²y_i² ]
//            = (Σx²)(Σy²) − (Σxy)²
// 所以区间询问只要拿到三个区间和:Σx²、Σy²、Σx·y。
// 单点修改 → 三个量都只有一处变化 → 树状数组维护三个分量即可。
//
// 数据结构:一棵树状数组,每个结点同时存三个分量(Σx²、Σy²、Σx·y)。
// 时间 O((n + m) log n),空间 O(n)(n = 10^6 时约 24 MB)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MOD = 20170927;
const int MAXN = 1000000 + 5;

int n, m;

struct Node {
    ll px; // Σ x²
    ll py; // Σ y²
    ll pr; // Σ x·y
};

struct Vec {
    int x;
    int y;
};

Node tree[MAXN]; // 树状数组:下标 i 管辖一段区间,三个分量都恒保存在 [0, MOD)
Vec vel[MAXN];   // 每个电子当前的速度

// ── 快速输入:fread 缓冲,处理 n, m ≤ 10^6 的量级 ──
static char inbuf[1 << 20];
static int inpos = 0, inlen = 0;

inline int readChar() {
    if (inpos == inlen) {
        inlen = fread(inbuf, 1, sizeof(inbuf), stdin);
        inpos = 0;
        if (inlen <= 0) return -1;
    }
    return (unsigned char)inbuf[inpos++];
}

inline int readInt() {
    int c = readChar();
    while (c != -1 && (c < '0' || c > '9')) c = readChar();
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = readChar();
    }
    return x;
}

// ── 快速输出:攒满一个缓冲区再整体写出 ──
static char outbuf[1 << 20];
static int outpos = 0;

inline void flushOut() {
    if (outpos > 0) {
        fwrite(outbuf, 1, outpos, stdout);
        outpos = 0;
    }
}

inline void writeInt(ll v) {
    char tmp[24];
    int k = 0;
    if (v == 0) tmp[k++] = '0';
    while (v > 0) {
        tmp[k++] = '0' + v % 10;
        v /= 10;
    }
    if (outpos + k + 1 > (int)sizeof(outbuf)) flushOut();
    while (k > 0) outbuf[outpos++] = tmp[--k];
    outbuf[outpos++] = '\n';
}

// 在下标 pos 处把三个分量各加上 d*(增量已归一到 [0, MOD))
void add(int pos, ll dx, ll dy, ll dr) {
    for (int i = pos; i <= n; i += i & -i) {
        tree[i].px += dx;
        if (tree[i].px >= MOD) tree[i].px -= MOD;
        tree[i].py += dy;
        if (tree[i].py >= MOD) tree[i].py -= MOD;
        tree[i].pr += dr;
        if (tree[i].pr >= MOD) tree[i].pr -= MOD;
    }
}

// 前 pos 个电子三个分量之和(各自对 MOD 取模)
Node prefixSum(int pos) {
    Node s;
    s.px = s.py = s.pr = 0;
    for (int i = pos; i > 0; i -= i & -i) {
        s.px += tree[i].px;
        s.py += tree[i].py;
        s.pr += tree[i].pr;
    }
    s.px %= MOD;
    s.py %= MOD;
    s.pr %= MOD;
    return s;
}

int main() {
    n = readInt();
    m = readInt();

    for (int i = 1; i <= n; i++) {
        int x = readInt() % MOD;
        int y = readInt() % MOD;
        vel[i].x = x;
        vel[i].y = y;
        add(i, (ll)x * x % MOD, (ll)y * y % MOD, (ll)x * y % MOD);
    }

    for (int q = 1; q <= m; q++) {
        int op = readInt();
        if (op == 1) {
            int p = readInt();
            int x = readInt() % MOD;
            int y = readInt() % MOD;
            int ox = vel[p].x, oy = vel[p].y;

            ll dx = ((ll)x * x - (ll)ox * ox) % MOD;
            if (dx < 0) dx += MOD;
            ll dy = ((ll)y * y - (ll)oy * oy) % MOD;
            if (dy < 0) dy += MOD;
            ll dr = ((ll)x * y - (ll)ox * oy) % MOD;
            if (dr < 0) dr += MOD;
            add(p, dx, dy, dr);

            vel[p].x = x;
            vel[p].y = y;
        } else {
            int l = readInt(), r = readInt();
            Node sr = prefixSum(r);
            Node sl = prefixSum(l - 1);
            ll px = (sr.px - sl.px + MOD) % MOD; // 区间内的 Σ x²
            ll py = (sr.py - sl.py + MOD) % MOD; // 区间内的 Σ y²
            ll pr = (sr.pr - sl.pr + MOD) % MOD; // 区间内的 Σ x·y

            ll ans = (px * py - pr * pr) % MOD;
            if (ans < 0) ans += MOD;
            writeInt(ans);
        }
    }

    flushOut();
    return 0;
}

复杂度

  • 时间:初始化 O(nlog⁡n)O(n \log n),每次操作 O(log⁡n)O(\log n),总计 O((n+m)log⁡n)O((n + m)\log n)。
  • 空间:树状数组与速度数组各 O(n)O(n);C++ 约 2424 MB(10610^6 个结点,每结点三个 8 字节分量),Python 约 55 个长度为 106+110^6+1 的列表。

总结

  • 遇到"两两配对的平方和 / 叉积和",先试着把求和式展开成"整体量减对角量"的形式; 一旦展开成 P⋅Q−R2P \cdot Q - R^2 这种只含可加量的表达式,带修区间询问就退化成 若干条前缀和的维护,树状数组(或线段树)即可。
  • 同一个下标集合上的多个可加量,若修改点、查询点相同,可以塞进同一棵树状数组的结点里, 一次 log⁡n\log n 走完,不必开三棵树重复遍历。
  • 模意义下维护树状数组,只要保证每个结点恒在 [0,MOD)[0, \mathrm{MOD})(加法后减一次), 查询时累加量就不会溢出 long long。

数据说明:本题所在目录的测试数据由 data.py 用 cyaron 生成(生成脚本随素材提供), 题面为网络重建版本,与官方原题的数据强度可能略有差异;做法本身即公开题解中流传的 "三个树状数组"标程思路(叉积平方和 = (Σx2)(Σy2)−(Σxy)2(Σx^2)(Σy^2) - (Σxy)^2)。