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
s[0]: "000000", v[0]: 1
s[1]: "314159", v[1]: 2
s[2]: "161803", v[2]: 10
s[3]: "169231", v[3]: 5
s[4]: "384400", v[4]: 20
q: 4

各ドリンクの情報を vec に入れる。
添字を $1$ ずつずらして記録するので、初期状態で $0$ でない場所は次の $5$ 箇所である。

vec[1][1][1][1][1][1]: 1    ← 000000
vec[4][2][5][2][6][10]: 2   ← 314159
vec[2][7][2][9][1][4]: 10   ← 161803
vec[2][7][10][3][4][2]: 5   ← 169231
vec[4][9][5][5][1][1]: 20   ← 384400

その後、全方向に累積和を取る。
内部の値は非常に多くなるので、ここでは全部は書かない。
累積和を取った後は、各方向について半開区間の端点を指定し、包除原理で範囲内の総和を求められるようになる。

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

x: "150001"
y: "269944"

コードでは、各桁について範囲の下端と上端を次のように持つ。
添字は $1$ ずつずらして記録しているため、条件 $x_k \leq s_k \leq y_k$ は累積和上では半開区間 $[x_k, y_k+1)$ に対応する。
$x_k > y_k$ であるものは存在しないので、総和を実行する。

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

つまり、このクエリで調べる範囲は次の通りである。

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

この範囲の総和を、$2^6$ 箇所の累積和の足し引きで求める。
実際の処理では、b を $0$ から $63$ まで動かし、popcount(b) の偶奇で符号を決める。

入力例1のドリンクのうち、この条件を満たすものは次の $2$ つである。

161803: 10
169231: 5

よって、答えは $10+5=15$ である。

result: 15

他のクエリも同様に、各方向の端点を作り、$2^6$ 箇所の累積和を足し引きして答えを求める。

注意点

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

別解

特になし。