动态高维空间中的量子纠缠覆盖
（Dynamic Quantum Entanglement Coverage in High-Dimensional Space）
问题描述
在 ddd 维离散空间 Zd\mathcal{Z}^dZd 中（d≤10d \leq 10d≤10），存在 nnn（n≤105n \leq 10^5n≤105）个动态量子态实体。每个实体 iii 在时刻 ttt 由以下参数定义：
1. 位置 pi⃗(t)∈[1,109]d\vec{p_i}(t) \in [1, 10^9]^dpi (t)∈[1,109]d
2. 纠缠半径 ri(t)∈[1,106]r_i(t) \in [1, 10^6]ri (t)∈[1,106]
3. 相位 ϕi(t)∈{0,1}\phi_i(t) \in \{0, 1\}ϕi (t)∈{0,1}
实体状态每秒依 量子跃迁规则 更新：
* pi⃗(t+1)=pi⃗(t)+Δpi⃗⋅(−1)ϕi(t)\vec{p_i}(t+1) = \vec{p_i}(t) + \Delta \vec{p_i} \cdot (-1)^{\phi_i(t)}pi (t+1)=pi (t)+Δpi ⋅(−1)ϕi (t)
* ri(t+1)=ri(t)⊕ϕi(t)r_i(t+1) = r_i(t) \oplus \phi_i(t)ri (t+1)=ri (t)⊕ϕi (t)
* ϕi(t+1)=ϕi(t)⊕⨁j∈Ei(t)ϕj(t)\phi_i(t+1) = \phi_i(t) \oplus \bigoplus_{j \in \mathcal{E}_i(t)} \phi_j(t)ϕi (t+1)=ϕi (t)⊕⨁j∈Ei (t) ϕj (t)
其中 Δpi⃗\Delta \vec{p_i}Δpi 为固定向量，Ei(t)\mathcal{E}_i(t)Ei (t) 表示 ttt 时刻与 iii 位置在曼哈顿距离 ≤ri(t)+rj(t)\leq r_i(t) + r_j(t)≤ri (t)+rj (t) 内的实体集合。
操作与查询
实现以下实时操作（总操作数 m≤3×105m \leq 3 \times 10^5m≤3×105，时限 4.0s）：
1. UPDATE k t：将实体 kkk 的状态同步到时刻 ttt（ttt 为当前时刻）
2. ADD t p⃗ r φ：在时刻 ttt 加入新实体
3. DEL k：删除实体 kkk
4. QUERY t S：查询时刻 ttt 时，集合 SSS（∣S∣≤5|S| \leq 5∣S∣≤5）中所有实体的量子覆盖积：
[
∏i∈S(∑j≠i∥pi⃗−pj⃗∥1≤ri+rj(−1)ϕi⊕ϕj⋅⌈rirj⌉mod 232)mod 264\prod_{i \in S} \left( \sum_{\substack{j \neq i \\ \|\vec{p_i}-\vec{p_j}\|_1 \leq r_i + r_j}} (-1)^{\phi_i \oplus \phi_j} \cdot \left\lceil \frac{r_i}{r_j} \right\rceil \mod 2^{32} \right) \mod 2^{64} i∈S∏ j=i∥pi −pj ∥1 ≤ri +rj ∑ (−1)ϕi ⊕ϕj
⋅⌈rj ri ⌉mod232 mod264
]
约束
* 内存 ≤ 512 MB
* 初始 nnn 个实体状态在 t=0t=0t=0 给出
* 所有操作按时间戳严格递增给出
* 删除操作保证实体存在且未被删除
输入格式
d n m
Δp₁ Δp₂ ... Δp_d // 每个实体的固定位移向量
<初始实体数据> // 每行：ID p⃗ r φ
<操作序列> // 每行一个操作
输出格式
对每个 QUERY 输出一行，为覆盖积的 64 位无符号整数值。
