题目概述

我们需要维护平面上的整点，支持两种操作：

1. 修改操作：1 x y d w

   • 对满足 $|X-x| < d, |Y-y| < d$ 的整点 $(X,Y)$
   • 点权增加 $w \cdot (d - \max(|X-x|, |Y-y|))$
   • 这是一个菱形区域的加权修改

2. 查询操作：2 x1 x2 y1 y2

   • 查询矩形区域 $[x_1, x_2] \times [y_1, y_2]$ 内所有整点的点权之和
   • 答案对 $2^{30}$ 取模

---

问题分析

修改操作的特殊性

修改影响的区域是一个以 $(x,y)$ 为中心、边长为 $2d-1$ 的菱形（$L^\infty$ 范数下的圆）：

• 点 $(X,Y)$ 的权重 = $w \cdot (d - \max(|X-x|, |Y-y|))$
• 权重随到中心的切比雪夫距离线性递减

直接暴力不可行

• 坐标范围达到 $10^8$，不能直接存储每个点
• 操作次数 $m \le 10^5$，需要高效算法

---

核心思路：CDQ分治 + 多项式分解

关键观察

修改操作的权重函数可以表示为关于 $X$ 和 $Y$ 的低次多项式：

对于修改 $(x,y,d,w)$ 和点 $(X,Y)$，权重为：

$$w(X,Y) = w \cdot (d - \max(|X-x|, |Y-y|))$$

这个函数在菱形区域内是分片线性函数，可以分解为多个二次多项式的和。

坐标变换

通过巧妙的坐标变换，将菱形区域转化为轴对齐矩形：

• 令 $u = X + Y$, $v = X - Y$
• 菱形区域变成矩形区域
• 权重函数变成关于 $u,v$ 的简单函数

多项式分解

代码中将权重函数分解为关于 $X,Y$ 的三次多项式：

$$w(X,Y) = \sum_{i=0}^3 \sum_{j=0}^{3-i} c_{ij} X^i Y^j $$

然后使用二维前缀和的思想，通过维护多项式的各项系数来快速计算区间和。

---

算法架构

CDQ分治框架

1. 将操作序列按时间分成两半：$[l, mid]$ 和 $[mid+1, r]$
2. 递归处理左右两半
3. 计算左半的修改对右半查询的贡献

数据结构设计

修改操作 (modify)

• a, b：变换后的坐标
• w：权重系数

查询操作 (query)

• a, b：变换后的坐标边界
• id：查询编号
• t：容斥系数（+1 或 -1）

树状数组 (fenwick)

维护7个多项式的系数：

• Sy3：$Y^3$ 系数
• Sxy2：$XY^2$ 系数
• Sy2：$Y^2$ 系数
• Sxy：$XY$ 系数
• Sy：$Y$ 系数
• Sx：$X$ 系数
• S1：常数项系数

处理流程

1. 坐标离散化：对变换后的坐标进行离散化
2. 扫描线处理：按 $b$ 坐标排序，用树状数组维护多项式系数
3. 贡献计算：对于每个查询，组合各项系数得到答案
4. 坐标交换：处理对称情况

---

关键代码解析

修改操作分解

auto add = [&](int x, int y, int d, unsigned w, vector<modify> &md1, vector<modify> &md2) {
    md1.emplace_back(x - d + 1, y - d + 1, w);
    md1.emplace_back(x + d + 1, y + d + 1, -w);
    // ... 更多容斥项
};

这里使用高维前缀和的技巧，通过添加带符号的修改来实现矩形区域的覆盖。

多项式系数更新

Sy3.add(z, w), Sxy2.add(z, -3 * w), Sy2.add(z, (-3 * b + 3 * a) * w);
Sxy.add(z, (6 * b - 9) * w), Sy.add(z, (3 * b * b - 6 * a * b + 9 * a - 7) * w);
// ...

这些系数是通过对权重函数进行多项式展开得到的，使得区间和可以表示为这些系数的线性组合。

答案计算

res[id] += v * (Sy3.ask(z) * y * y * y + Sxy2.ask(z) * x * y * y 
             + Sy2.ask(z) * y * y + Sxy.ask(z) * x * y 
             + Sy.ask(z) * y + Sx.ask(z) * x + S1.ask(z));

将各项系数与对应的 $X^iY^j$ 相乘，求和得到最终结果。

---

复杂度分析

• CDQ分治：$O(m \log m)$ 层递归
• 每层处理：$O(m \log m)$（排序 + 树状数组操作）
• 总复杂度：$O(m \log^2 m)$

由于 $m \le 10^5$，$O(10^5 \times \log^2 10^5) \approx 10^5 \times 17^2 \approx 3 \times 10^7$，可以接受。

---

样例解析

样例：

5
1 3 4 5 1    # 修改：中心(3,4)，d=5，w=1
2 1 4 3 5    # 查询：[1,4]×[3,5] → 答案46
1 2 4 2 2    # 修改：中心(2,4)，d=2，w=2  
2 4 5 3 5    # 查询：[4,5]×[3,5] → 答案21
1 4 4 4 8    # 修改：中心(4,4)，d=4，w=8

算法通过CDQ分治，计算每个修改对后续查询的贡献，最终得到正确结果。

---

模运算技巧

答案对 $2^{30}$ 取模，但代码中使用 unsigned 类型和特殊的 ind 函数来处理：

• 利用 $3$ 在模 $2^{30}$ 下的逆元
• 通过数学变换避免除法

inline i64 ind(unsigned x) {
    int P = 1 << 30;
    i64 ans = (x >> 1) % P;
    while (ans % 3) ans += P;
    ans /= 3;
    return (P - ans % P) % P;
}

---

总结

这道题的解法结合了多个高级技巧：

1. CDQ分治：处理时间序列上的修改查询
2. 坐标变换：将菱形区域转化为矩形区域
3. 多项式分解：将复杂权重函数表示为低次多项式
4. 高维前缀和：通过容斥处理矩形区域
5. 扫描线+树状数组：高效维护多项式系数

这种"几何变换 + 多项式分解 + CDQ分治"的组合拳，是解决复杂二维区间问题的有力工具，特别适合处理带权重的几何操作。