33OJ
登录 注册

#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 NN integers a1,a2,⋯ ,aNa_1, a_2, \cdots, a_N and QQ operations. There are two types of operations.

  • Modify operation: Given x,yx, y, change axa_x to yy.
  • Query operation: Given L,RL, R. Consider aL,aL+1,⋯ ,aRa_L, a_{L + 1}, \cdots, a_{R} as coins with values aL,aL+1,⋯ ,aRa_L, a_{L + 1}, \cdots, a_R, please find out the minimum number yuukiyuuki, such that it is impossible to choose a subset of the coins stated before, such that the sum of their values is yuukiyuuki.

Input Format

The first line of the input contains two integers N,QN, Q denotes the length of the sequence and the number of operations.

Then, there are NN space-separated integers a1,a2,⋯ ,aNa_1, a_2, \cdots, a_N.

Then, the following QQ lines are the operations. Each operation must follow the following two formats:

  1. 1 x y1 \ x \ y: Modify operation.
  2. 2 L R2 \ L \ R: Query operation.

The meaning of the variable are stated in the problem description!

  • 1≤N,Q,ai≤2×1051 \le N, Q, a_i \le 2 \times 10^5
  • 1≤x≤N1 \le x \le N
  • 1≤y≤2×1051 \le y \le 2 \times 10^5
  • 1≤L≤R≤N1 \le L \le R \le N

Output Format

For each query operation, output the corresponding yuukiyuuki 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