#P17738. [ICPC 2019 Xuzhou R] Yuuki and a problem
[ICPC 2019 Xuzhou R] Yuuki and a problem
Problem Description
Yuuki, a cute senior high school student with excellent talent in mahjong, comes up with a cool problem. The problem goes as follows:
Given a sequence with integers and operations. There are two types of operations.
- Modify operation: Given , change to .
- Query operation: Given . Consider as coins with values , please find out the minimum number , such that it is impossible to choose a subset of the coins stated before, such that the sum of their values is .
Input Format
The first line of the input contains two integers denotes the length of the sequence and the number of operations.
Then, there are space-separated integers .
Then, the following lines are the operations. Each operation must follow the following two formats:
- : Modify operation.
- : Query operation.
The meaning of the variable are stated in the problem description!
Output Format
For each query operation, output the corresponding value in one line.
3 7
1 3 2
2 1 1
2 2 2
2 1 3
1 3 1
2 1 3
1 1 5
2 1 3
2
1
7
6
2