把叉积平方和展开成 (Σx²)(Σy²)−(Σx·y)²,用树状数组同时维护三个分量,单点改速度与区间询问都是 O(log n)。
OJ: roj
题目 ID: 1741
难度:提高
标签:树状数组前缀和数学python
创建: 2026-10-07 20:34
更新: 2026-10-07 20:34
形式化题目
平面上有
需要支持
- 修改:给定
,把 改成 ; - 询问:给定
,求 对 取模的值。
约束:
正解
思路
先把被求的量化开。平面向量叉积只有
第一个和式是"有序对"求和,可以拆成全体减对角:
第二个和式同理,
这一步是整个解法的关键:它把"两两配对"的二次代价降成了三个可加的量。对任意一个下标集合
于是问题变成"三个可加量的区间和":单点修改只会同时改变
前缀和带单点修改 —— 树状数组。三棵树分别维护
取模细节。树内每个结点的每个分量恒保存在 long long 内,最后统一取模。
单点修改时增量取 long long 精确,最后调整符号到
注意区间内
代码
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++ 正解(三个分量合并到一棵树状数组,配手写快读快写以承受
/**
* 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;
}复杂度
- 时间:初始化
,每次操作 ,总计 。 - 空间:树状数组与速度数组各
;C++ 约 MB( 个结点,每结点三个 8 字节分量),Python 约 个长度为 的列表。
总结
- 遇到"两两配对的平方和 / 叉积和",先试着把求和式展开成"整体量减对角量"的形式;
一旦展开成
这种只含可加量的表达式,带修区间询问就退化成 若干条前缀和的维护,树状数组(或线段树)即可。 - 同一个下标集合上的多个可加量,若修改点、查询点相同,可以塞进同一棵树状数组的结点里,
一次
走完,不必开三棵树重复遍历。 - 模意义下维护树状数组,只要保证每个结点恒在
(加法后减一次), 查询时累加量就不会溢出 long long。
数据说明:本题所在目录的测试数据由
data.py用 cyaron 生成(生成脚本随素材提供), 题面为网络重建版本,与官方原题的数据强度可能略有差异;做法本身即公开题解中流传的 "三个树状数组"标程思路(叉积平方和 =)。