
Simple Queries
|
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Given an array A consisting of N positive integers, and Q queries on it. The queries can be of five types:
- 1 l r - let S - sorted set of elements with indices between l and r. You need to find:
- 2 x y - assign the value y to element at position x.
- 3 x - delete element at position x from array.
- 4 z y - insert y after element at position z. If z equal 0 then y should insert before the first element.
- 5 l r - count the number of distinct numbers in array between indices l and r.
All the indices in the queries are 1-based.
Array always contains at least one element.
Input
The first line of input contains two integers N and Q denoting the number of elements in A, and the number of queries to be executed. The second line of input contains N integers denoting the array A. Each of the next Q lines contains one query.
Output
For each query of type 1 or type 5, output the answer to the query in a single line.
Constraints
- 1 ≤ N, Q ≤ 105
- 1 ≤ Ai, y ≤ 109 + 6
- 1 ≤ x ≤ |A|
- 1 ≤ l ≤ r ≤ |A|
- 0 ≤ z ≤ |A|
Example
Input: 5 8 1 2 3 2 1 1 1 3 5 1 5 2 2 4 1 2 4 3 3 4 0 5 1 1 2 1 1 5 Output: 6 3 24 0 78 Input: 10 15 5 4 3 5 4 1 5 4 3 1 2 8 580347 4 6 503576 1 2 5 5 8 11 1 2 6 4 7 565239 3 6 3 11 3 3 2 9 674360 1 1 6 2 2 589693 4 5 236488 1 8 9 5 2 7 Output: 60 4 107 788510349 0 6
Subtasks
- Subtask 1: Q*N ≤ 2*107. Points - 10
- Subtask 2: Queries are of type 5 only. Points - 5
- Subtask 3: Queries are of type 1 only. Points - 10
- Subtask 4: Queries are of types 2, 5 only. Points - 15
- Subtask 5: Queries are of types 1, 2, 5 only. N, Q ≤ 50000 Points - 15
- Subtask 6: Queries are of types 2, 3, 4 only. Points - 5
- Subtask 7: N, Q ≤ 50000. Points - 10
- Subtask 8: Original constraints. Points - 30
Explanation
Query 1 Sorted set of elements with positions between 1 and 3 is S = {1, 2, 3}, ans = 1 * 2 * 3 = 6.
Query 2 Set of elements with positions between 1 and 5 is S = {1, 2, 3}, ans = |S| = 3.
Query 3 After this query A = {1, 4, 3, 2, 1}.
Query 4 Sorted set of elements with positions between 2 and 4 is S = {2, 3, 4}, ans = 2 * 3 * 4 = 24.
Query 5 After this query A = {1, 4, 2, 1}.
Query 6 After this query A = {5, 1, 4, 2, 1}.
Query 7 Sorted set of elements with positions between 1 and 2 is S = {1, 5}, ans = 0.
Query 8 Sorted set of elements with positions between 1 and 5 is S = {1, 2, 4, 5}, ans = 1 * 2 * 4 + 1 * 2 * 5 + 2 * 4 * 5 + 1 * 4 * 5 = 78.
Author: | mgch |
Tester: | laycurse |
Editorial | http://discuss.codechef.com/problems/DISTNUM |
Tags | 2d, aug15, fenwick-tree, mgch, range-tree, segment-tree, sqrt-decomp, super-hard |
Date Added: | 17-07-2015 |
Time Limit: | 2 sec |
Source Limit: | 50000 Bytes |
Languages: | C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, PYP3, CLOJ, FS |
Comments
- Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. |
