ABC465 F - Sjeltzer?

考え方

ID の桁数が $6$ 桁あるが、こういうときは問題を小さくして考えるのがいい。
そこで、ID が $2$ 桁の場合を考えてみよう。

例えば、ID が $12$、$14$、$23$、$32$、$44$ の $5$ つのドリンクがあり、全てサイズは $1$ とする。
ここにクエリとして 22 33 が来たとする。
もちろん愚直に $5$ 個のデータを調べれば答えは出るが、それでは計算量が $O(NQ)$ でTLE。
これをどうするか、と問われれば、これはD問題レベルである。
事前に二次元累積和を取ることで $O(N+D^2+Q)$ になる。
ただし、$D$ は使える数字の個数である $10$ である。

こう考えると $6$ 桁の場合もやることは明らかで、六次元累積和をとればよい。
方針立てはこれで全部で、無事に $O(N+D^6+Q)$ で間に合う目途が立つ。

問題はコード書き。
特に大きな問題が $3$ つある。

$1$ つめは、六次元のデータをどう持つのかという問題。
しかも、累積和を取るので各方向の長さが $11$ ほしい。
これは大きく $4$ つ（他にもあるかも）思いつくが、いずれも問題点がある。
自分にとって最も気にならない方針を選ぶこと。

$2$ つめは、六方向の累積和をとる方法。
愚直に書くと $6$ 重ループを $6$ 回書くことになる。
これもいくつか方針がある。

$3$ つめは、六次元累積和には、包除原理で足す値が $2^6=64$ 個もあること。
これもいくつか方針がある。

解答例のコードでは、いずれも最後に提示した方法を採用している。

入力例1での動作

入力を受け取る。

n: 5
000000 1
314159 2
161803 10
169231 5
384400 20
q: 4

各 ID の各桁を $1$ ずつずらした位置に、サイズを加える。
累積和を取る前に $0$ でない場所は次の $5$ 箇所である。

vec[1][1][1][1][1][1]: 1
vec[4][2][5][2][6][10]: 2
vec[2][7][2][9][1][4]: 10
vec[2][7][10][3][4][2]: 5
vec[4][9][5][5][1][1]: 20

ここから $6$ 方向に累積和を取る。
例えば最初に第 $6$ 軸方向へ累積すると、000000 の $1$ は次の位置へ順に伝わる。

vec[1][1][1][1][1][1]: 1
vec[1][1][1][1][1][2]: 1
...
vec[1][1][1][1][1][10]: 1

同じ処理を残り $5$ 方向にも行うことで、六次元の累積和が完成する。

$1$ つめのクエリを見る。

x: "150001"
y: "269944"

各桁で許される数字の範囲は次の通りである。

1桁目: 1 以上 2 以下
2桁目: 5 以上 6 以下
3桁目: 0 以上 9 以下
4桁目: 0 以上 9 以下
5桁目: 0 以上 4 以下
6桁目: 1 以上 4 以下

累積和で使う半開区間の端点は次のようになる。

c0: {1, 3}
c1: {5, 7}
c2: {0, 10}
c3: {0, 10}
c4: {0, 5}
c5: {1, 5}

この $6$ 個の区間から端点を $1$ つずつ選ぶので、参照する累積和は $2^6=64$ 箇所ある。
例えば、bit 全探索の一部は次のようになる。

残りの端点も同様に、popcount(b) の偶奇で符号を決めて足し引きする。

この範囲に入るドリンクは次の $2$ つである。

161803: 10
169231: 5

したがって、$1$ つめのクエリの答えは $10+5=15$ となる。

$4$ つめのクエリでは、例えば $1$ 桁目について 9 以上 0 以下という条件になる。

x: "999000"
y: "000444"

この場合は条件を満たす ID が存在しない。
コード上でも対応する区間の長さが $0$ になり、答えは $0$ となる。

注意点

答えは int 型からはみ出る。
long long 型を用いること。

別解

特になし。