DCP-438: Chowdhury Saheb & the Queries Back to All Problems
Medium
Data Structures > Segment Tree/Interval Tree
You are given an array of **N** integers. You need to perform **Q** queries. In each query, you have to perform any of these two types of operation: **1 X C** : Calculate and print the number of maximum consecutive elements from index **X** such that, the sum of these elements doesn’t exceed **C**. **( 1 ≤ X ≤ N, 1 ≤ C ≤ 10^12 )** **2 X Y** : Change the value of **Xth** index of the array to **Y**. You need not to print anything here. **( 1 ≤ X ≤ N, 0 ≤ Y ≤ 10^6 )** Input: ------ The input starts with two integers **N (1 ≤ N ≤ 10^5)** and **Q (1 ≤ Q ≤ 10^5)** denoting the number of elements of the array and the total number of queries. The second line consist of **N** integers **ar[i] (0 ≤ ar[i] ≤ 10^6)** where **(1 ≤ i ≤ N)**. The next **Q** lines contains any of two types of query described above. Output: ------- For each query, perform the query as described above. Sample Input ------------ 5 4 1 2 4 5 6 1 1 3 1 3 15 2 2 7 1 1 3 Sample Output ------------- 2 3 1
