思路与算法

展开二维叉积平方：所有无序点对的和等于(Σx²)(Σy²)-(Σxy)²。用三组Fenwick聚合量保存x²、y²、xy，点修改以新旧差更新，区间查询由两个前缀相减。全程模20170927。

正确性说明

展开右式后，单点x²y²项相消；每一对不同点剩下x_i²y_j²+x_j²y_i²-2x_iy_ix_jy_j，恰为叉积平方。因此三个区间和完整决定答案。Fenwick不交前缀分解准确，差值更新保持真实点值。

复杂度

读入及线性建Fenwick O(n)，每次操作O(logn)，总O(n+mlogn)时间，存原点聚合与Fenwick O(n)空间。初始化同阶。

易错点

系数2已包含在平方展开，不需要再除2。单点区间答案0。乘法先用64位，差值和最终答案规范化到非负模数；新旧向量不能直接当作平方的差来平方。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const long long P = 20170927;
struct V {
    long long a, b, c;
    V(long long x = 0, long long y = 0, long long z = 0) : a(x), b(y), c(z) {
    }
};
V operator+(V x, V y) {
    return {(x.a + y.a) % P, (x.b + y.b) % P, (x.c + y.c) % P};
}
V operator-(V x, V y) {
    return {(x.a - y.a + P) % P, (x.b - y.b + P) % P, (x.c - y.c + P) % P};
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<V> bit(n + 1), val(n + 1);
    auto point = [](long long x, long long y) {
        return V{x * x % P, y * y % P, x * y % P};
    };
    auto add = [&](int i, V z) {
        for (; i <= n; i += i & -i)
            bit[i] = bit[i] + z;
    };
    auto sum = [&](int i) {
        V z;
        for (; i; i -= i & -i)
            z = z + bit[i];
        return z;
    };
    for (int i = 1; i <= n; i++) {
        long long x, y;
        cin >> x >> y;
        val[i] = point(x, y);
        bit[i] = bit[i] + val[i];
        int j = i + (i & -i);
        if (j <= n)
            bit[j] = bit[j] + bit[i];
    }
    while (m--) {
        int t, l;
        long long x, y;
        cin >> t >> l >> x;
        if (t == 1) {
            cin >> y;
            V z = point(x, y);
            add(l, z - val[l]);
            val[l] = z;
        } else {
            V z = sum(x) - sum(l - 1);
            cout << (z.a * z.b % P - z.c * z.c % P + P) % P << '\n';
        }
    }
}