 # DCP-463: Sort Query Again Back to All Problems

Hard Data Structures > Binary Indexed Tree

Given an integer array a of size n and q operation. There will be 2 types of operation. 1. [update] Each of type one operation is in the form of: i X, denotes - replace the ith element of the array with the value X. Namely set a[i]=x ,where **0 <= i < n, -10<sup>6</sup> <= a[i],x < 10<sup>6</sup>** 2. [query] Type 2 operation has 2 parameter l,r. Where **0 <= l <= r < n** , you’ve to find out whether subarray a[l..r] is sorted (in non decreasing order) or not. **n <= 10<sup>5</sup> , q<=2*10<sup>5</sup>** Input: ------ First line will contain a integer t, will denote number of test case. Each test case start with a number n. Denote the size of the array Next line will contain n space separated integer. 3rd line of each test case will contain a single integer q , which is the number of operation. Next q line will contain 3 integer each. First of them is p, the type of operation (1<=p<=2) If p is 1 then other 2 integer is i and x , ask you to set a[i]=x If p is 2 then other 2 integer is l,r ask you to find whether a[l...r] is sorted (in non decreasing order) or not. Output: ------- For each type 2 operation print ‘yes’ if a[l..r] is sorted in non decreasing order, ‘no’ otherwise , (without quote) in a line. **Maximum number of test case is 10** Sample Input ------------ 3 5 26 43 61 80 88 7 1 1 64 2 4 4 2 1 3 2 1 2 1 1 46 2 2 4 1 0 12 3 7 74 100 6 2 0 0 2 0 2 2 1 2 2 2 2 1 2 52 1 2 85 1 34 7 2 0 0 2 0 0 1 0 10 1 0 15 2 0 0 2 0 0 1 0 41 Sample Output ------------- yes no no yes yes yes yes yes yes yes yes yes

### Problem Limits

 Language Time Limit (seconds) C 2.50 C++ 2.50 C++14 2.50 C# 3.00 Go 3.00 Java 3.00 JavaScript 3.00 Objective-C 3.00 Perl 3.00 PHP 3.00 Python 3.00 Python3 3.00 Ruby 3.00 VB.Net 3.00

# 19/47

Solve/Submission

### Ranking

# User Language Timing
01 rafael Cpp 0.45s
02 feodorv C 0.46s
03 tariqiitju Cpp14 0.51s
04 Robbinb1993 Cpp14 0.55s
05 Tahmid Cpp14 0.58s
06 mir003 Cpp 0.66s
07 skmonir Cpp14 0.84s
08 clkjwdhc Cpp 0.86s
09 SakibAlamin Cpp14 0.95s
10 Sajid13 Cpp14 1.10s
11 ehsan_sshuvo96 Cpp 1.13s
12 kamrulashraf Cpp 1.16s
13 prodipdatta7 Cpp14 1.18s
14 anik_JU Cpp 1.43s
Feedback