問題
$D$ 次元空間に $N$ 個の点 $(x_{i,1}, \ldots, x_{i,D})$（座標 $0 \le x_d < K$）と値 $v_i$ がある。各クエリは $D$ 次元矩形 $[l_1, r_1] \times \cdots \times [l_D, r_D]$ 内の値の総和。
制約
$1 \le D \le 5$
$2 \le K \le 200$
$1 \le N, Q \le 10^5$
入出力例
入力例 1
2 3 3 2
0 0 1
1 1 2
2 2 3
0 1 0 1
1 2 1 2出力例 1
3
5ヒント (段階的開示)
ヒント1: 方向性
$D$ 次元累積和を構築。クエリは包除原理で $O(2^D)$ 個の端点参照。
ヒント2: アプローチ
各次元 $d$ について独立に 1 次元前置和を取れば $D$ 次元累積和になる。stride $K^{D-1-d}$。
ヒント3: 誘導
$[l_d, r_d]$ クエリでは
l_d - 1 のとき $l_d = 0$ なら無効化（負インデックス回避）。模範解答 (Python)
import sys
input = sys.stdin.readline
def solve():
D, K, N, Q = map(int, input().split())
total_size = K ** D
grid = [0] * total_size
def to_flat(coords):
idx = 0
for c in coords:
idx = idx * K + c
return idx
for _ in range(N):
line = list(map(int, input().split()))
coords = line[:D]
v = line[D]
grid[to_flat(coords)] += v
for d in range(D):
stride = K ** (D - 1 - d)
for flat in range(total_size):
coord_d = (flat // stride) % K
if coord_d > 0:
grid[flat] += grid[flat - stride]
out = []
for _ in range(Q):
bounds = list(map(int, input().split()))
ans = 0
for s in range(1 << D):
coords = []
sign = 1
valid = True
for d in range(D):
l, r = bounds[2 * d], bounds[2 * d + 1]
if s >> d & 1:
if l == 0:
valid = False; break
coords.append(l - 1)
sign = -sign
else:
coords.append(r)
if valid:
ans += sign * grid[to_flat(coords)]
out.append(ans)
print('\n'.join(map(str, out)))
solve()Step-by-Step 解説
1フラット化
$D$ 次元配列を 1 次元化。$(x_1, \ldots, x_D)$ → $x_1 K^{D-1} + \cdots + x_D$。
$D$ 次元配列を 1 次元化。$(x_1, \ldots, x_D)$ → $x_1 K^{D-1} + \cdots + x_D$。
2累積和構築
各次元 $d$ について他次元固定で 1 次元前置和。$O(D \cdot K^D)$。
各次元 $d$ について他次元固定で 1 次元前置和。$O(D \cdot K^D)$。
3矩形クエリ
$\sum_{s \in \{0,1\}^D} (-1)^{|s|} f[p(s)]$ で $O(2^D)$。
$\sum_{s \in \{0,1\}^D} (-1)^{|s|} f[p(s)]$ で $O(2^D)$。
4計算量
大きな $K^D$ には座標圧縮を併用する。
大きな $K^D$ には座標圧縮を併用する。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| l=0 で l-1 が負 | 境界チェック忘れ | if l == 0: valid = False |
| K^D メモリ不足 | D=5,K=200 | 座標圧縮 / 次元制限 |
| stride 計算ミス | 次元順序を間違える | stride = K**(D-1-d) |
次のステップ
- 動的 D 次元 BIT（点挿入・削除）
- SOS DP（ビット部分集合和）