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 Setter:

Md. Tariqul Islam

Please login to submit solution to this problem.

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

Problem Stats

18/42

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 Sajid13 Cpp14 1.10s
10 ehsan_sshuvo96 Cpp 1.13s
11 kamrulashraf Cpp 1.16s
12 prodipdatta7 Cpp14 1.18s
13 anik_JU Cpp 1.43s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support