Hyper Array and Hyper Queries
Time limit2sMemory limit512 MB
Given a value for every cell of an 11-dimensional array, answer range-sum queries over axis-aligned 11-dimensional boxes.
- Level
Medium6 of 10
- Topics
- Prefix sum, Array, Implementation, Math
- Solved
- No attempts yet
Problem
A hyper array A11111111111, A11111111112, ..., A**mnopqrstuvw with shape m × n × o × p × q × r × s × t × u × v × w is given. Write a program that performs the following hyper queries.
a1 b1 c1 d1 e1 f1 g1 h1 i1 j1 k1 a2 b2 c2 d2 e2 f2 g2 h2 i2 j2 k2: print the sum of Aαβγδεζηθικλ over all (α, β, γ, δ, ε, ζ, η, θ, ι, κ, λ) such that a1 ≤ α ≤ a2, b1 ≤ β ≤ b2, c1 ≤ γ ≤ c2, d1 ≤ δ ≤ d2, e1 ≤ ε ≤ e2, f1 ≤ ζ ≤ f2, g1 ≤ η ≤ g2, h1 ≤ θ ≤ h2, i1 ≤ ι ≤ i2, j1 ≤ κ ≤ j2, k1 ≤ λ ≤ k2.
Input
The first line gives the shape of the hyper array: m, n, o, p, q, r, s, t, u, v, w. (1 ≤ m, n, o, p, q, r, s, t, u, v, w, mnopqrstuvw ≤ 106)
Starting on the second line, A11111111111, A11111111112, ..., A**mnopqrstuvw are given as follows. (1 ≤ Aαβγδεζηθικλ ≤ 109)
- The second line contains the w numbers A11111111111, A11111111112, ..., A1111111111w.
- This line repeats v times, giving the vw numbers A11111111111, A11111111112, ..., A111111111vw.
- These v lines repeat u times, giving the uvw numbers A11111111111, A11111111112, ..., A11111111uvw.
- These uv lines repeat t times, giving the tuvw numbers A11111111111, A11111111112, ..., A1111111tuvw.
- ⋯ In this way, A11111111111, A11111111112, ..., A**mnopqrstuvw are given across mnopqrstuv lines.
The (2 + mnopqrstuv)-th line gives the number of hyper queries, з. (1 ≤ з ≤ 4 × 104)
From the (3 + mnopqrstuv)-th line, з lines each give one hyper query a1, b1, c1, d1, e1, f1, g1, h1, i1, j1, k1, a2, b2, c2, d2, e2, f2, g2, h2, i2, j2, k2.
Output
For each hyper query, print the answer on its own line.