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 的序列 a1,a2,…,aN，以及 Q 筆操作。

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

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

Yuuki 好可愛 <3

Input Format

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

接下來的一行，包含 N 個正整數 a1,a2,…,aN。

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

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

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

  • 1≤N,Q≤2×105
  • 1≤x≤N
  • 1≤ai,y≤2×105
  • 1≤L≤R≤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