Chef and medium problem
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Chef has an array. The size of the array is equal to N.
Chef wants to make M queries. Each query has one of the two types:
- 1 l r - Calculate some interesting function F for subarray indexed from l to r inclusive.
- 2 l r - Modify the given array by removing all elements having indices in range from l to r and then putting these numbers at the beginning of
array. Order of all other elements remains same.
For example: you have array [1, 2, 3, 4, 5, 6, 7, 8] and query (2 4 6), the modified array after the operation will look like [4, 5, 6, 1, 2, 3, 7, 8].
All queries that goes after this query have to be executed at new the array.
Now let us define the interesting function F :).
Lets call this array B. Let |B| be the length of array B. Assume that B is having 1 based indexing.
Then the function F can be calculated by following code.
X = 1; for (i = 2; i <= |B|; i++) if (B[i] != B[i - 1]) X++; X is the output of the function F(B).
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of the elements in given array.
Next line contains N numbers denoting the elements of given array.
Third line contains a single integer M denoting the number of queries that Chef wants to execute.
Each of the next M lines describes a single query in the format given in the statement.
For each query of the first type output a single line containing a single integer - the answer for this query.
- 1 ≤ T ≤ 3
- 1 ≤ Ai ≤ 109
- 1 ≤ l ≤ r ≤ N
- Subtask 1 (15 points): 1 ≤ N ≤ 100, 1 ≤ M ≤ 1000
- Subtask 2 (25 points): 1 ≤ N, M ≤ 105, there is no query with type 2
- Subtask 3 (60 points): 1 ≤ N, M ≤ 105
Input: 1 5 1 1 2 1 3 5 1 1 5 1 2 4 2 2 3 1 1 5 2 3 3 Output: 4 3 4
|Tags||furko, hard, ltime16, substring, treaps|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.