257 . 可愛的優希

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

18.5% (5/27)

Tags

ioicamp ioicamp-2020

Description

優希，是一位可愛的女高中生，而且她很會打日麻。

現在，她想到了一個很有趣的問題，請你幫幫她。

給你一個長度為 $N$ 的序列 $a_1, a_2, \dots, a_N$，以及 $Q$ 筆操作。

操作有兩種，分別描述如下：

  • 修改：給你 $x, y$ ，請把 $a_x$ 變成 $y$ 。
  • 詢問：給你 $L, R$ 。想像你總共有 $R - L + 1$ 個硬幣，幣值分別是 $a_L, a_{L + 1}, \dots, a_{R}$ 。請找到最小的正整數 $yuuki$ ，滿足你在那 $R - L + 1$ 個硬幣中，找不到一個幣值總和恰好為 $yuuki$ 的子集合（ $yuuki$ 這個數字沒有辦法由那 $R - L + 1$ 個數字湊出來）。

Yuuki 好可愛 <3

Input Format

輸入的第一行包含兩個正整數 $N, Q$ ，分別代表序列的長度，以及操作的數量。

接下來的一行，包含 $N$ 個正整數 $a_1, a_2, \ldots, a_N$。

接下來的 $Q$ 行，每行代表一個操作。操作的格式分別如下：

  • $1 \ x \ y$ ：修改操作。
  • $2 \ L \ R$ ：詢問操作。

上述操作的意義已經在在題目敘述說明過了。

  • $1 \le N, Q \le 2 \times 10^ 5$
  • $1 \le x \le N$
  • $1 \le a_i, y \le 2 \times 10^ 5$
  • $1 \le L \le R \le N$

Output Format

對於詢問操作，請輸出該筆詢問操作的答案。

Sample Input 1

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

Sample Output 1

2
1
7
6
2

Hints

Problem Source

IOICamp 2020 Day4 pA

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~10 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 262144 65536 1 2
1 5000 262144 65536 2
2 5000 262144 65536 2
3 5000 262144 65536 2
4 5000 262144 65536 2
5 5000 262144 65536 2
6 5000 262144 65536 2
7 5000 262144 65536 2
8 5000 262144 65536 2
9 5000 262144 65536 2
10 5000 262144 65536 2
Submit
Back to Top