UTS Open '18 P6 - Subset Sum

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 2.0s
Java 8 5.0s
Memory limit: 256M
Java 8 256M

Author:
Problem type

One day, PlasmaVortex gave insect a question to solve: the Subset Sum Problem! However, insect proved that it was NP-complete, so PlasmaVortex makes up a new problem about subset sums:

Each of the 2^N (1 \le N \le 18) subsets of the set \{1, 2, 3, \dots \,, N\} has an N-bit identifier s, where the i^{th} bit (1 \le i \le N) of s is 1 if the set contains i, and 0 if the set doesn't contain i. Each set also has a value V_s (0 \le s < 2^N, 1 \le V_s \le 10^6). There are Q queries that come in two different types:

  1. 1 s v The set whose N-bit identifier is s has its value changed to v. (0 \le s < 2^N, 1 \le v \le 10^6)
  2. 2 a b Let A and B be the sets with identifiers a and b (0 \le a, b < 2^N). Output the sum of the values of all sets X such that A \subseteq X \subseteq B. (Output 0 if there are no such sets X).

Help insect solve this modified subset sum problem!

Input Specification

The first line contains N and Q. (1 \le N \le 18, 1 \le Q \le 10^5)

The next contains V_0, V_1, V_2, \dots \, , V_{2^N-1}, the values of the 2^N subsets of \{1, 2, 3, \dots \,, N\}. (1 \le V_0, V_1, V_2, \dots \, , V_{2^N-1} \le 10^6)

Each of the next Q lines contains a query in the format specified above.

Output Specification

Output the answer to each type 2 query on a separate line.

Subtasks

Subtask 1 [20%]

1 \le N \le 10

Subtask 2 [30%]

a = 0 for all type 2 queries

Subtask 3 [50%]

No additional constraints.

Sample Input

3 4
1 1 2 3 5 8 13 21
2 4 7
2 1 2
1 3 7
2 1 3

Sample Output

47
0
8

Explanation for Sample Output

In the first query, a = 4 = 100_2 and b = 7 = 111_2 correspond to sets A = \{1\} and B = \{1, 2, 3\}. There are 4 possible sets X that satisfy A \subseteq X \subseteq B, which are \{1\}, \{1, 2\}, \{1, 3\}, \{1, 2, 3\}, and the sum of their values is 5 + 13 + 8 + 21 = 47.

In the second query, a = 1 = 001_2 and b = 2 = 010_2, so A = \{3\} and B = \{2\}. No sets X satisfy A \subseteq X \subseteq B, so the answer is 0.

The third query changed the value of \{2, 3\} to 7, and in the fourth query, the possible sets X with A = \{3\} \subseteq X \subseteq \{2, 3\} are X = \{3\} and X = \{2, 3\}. The sum of their values is 1 + 7 = 8.


Comments

There are no comments at the moment.