33OJ
登录 注册

#P17738. [ICPC 2019 Xuzhou R] Yuuki and a problem

[ICPC 2019 Xuzhou R] Yuuki and a problem

题目描述

Yuuki 是一名可爱且具有出色麻将天赋的高中生,她提出了一个很酷的问题。问题描述如下:

给定一个包含 NN 个整数的序列 a1,a2,⋯ ,aNa_1, a_2, \cdots, a_N 和 QQ 次操作。操作共有两种类型。

  • 修改操作:给定 x,yx, y,将 axa_x 改为 yy。
  • 查询操作:给定 L,RL, R。将 aL,aL+1,⋯ ,aRa_L, a_{L + 1}, \cdots, a_{R} 视为面值分别为 aL,aL+1,⋯ ,aRa_L, a_{L + 1}, \cdots, a_{R} 的硬币,请找出最小的数字 yuukiyuuki,使得无法从上述硬币中选出一个子集,使得子集中硬币面值之和恰好等于 yuukiyuuki。

输入格式

第一行包含两个整数 N,QN, Q,分别表示序列的长度和操作的次数。

接下来一行包含 NN 个由空格分隔的整数 a1,a2,⋯ ,aNa_1, a_2, \cdots, a_N。

再接下来 QQ 行描述操作。每行一定符合以下两种格式之一:

  1. 1 x y:修改操作。
  2. 2 L R:查询操作。

各个变量的含义如问题描述所述!

  • 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

输出格式

对于每个查询操作,在一行中输出对应的 yuukiyuuki 值。

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

提示

翻译由 DeepSeek V4 Pro 完成