CNTINDX2 - Count The Indexes 2

Let's deal with an array again, the most important data structure of computer science. You will be given an array. Now you have some operations to do. There will be three types of operations:

  • Type 1: Insert a number after a given index
  • Type 2: Change the value of an index.
  • Type 3: You will get a number and two indices i and j where i <= j.

Now you will have to answer how many time the number appears in the array starting from i to j.

Input

Each file contains one test case.

The first line contains and integer N, the number of initial array elements (1 <= N <= 100000) and Q, the number of Queries (1 <= Q <= 100000). Second line contains N integers each in the range from 1 to 100000. Each of the next Q lines contains an operation. The operations will appear as the formats below:

  • 1 x y, where 1 <= x <= length of the array, which means you have to insert number y after the index x.
  • 2 x y, For this operation, you have to change the value of index x to value y.
  • 3 i j x, Here, you have to find how many times x appears in the array from i to j. Here x will always be present in the array and 1 <= i <= j <= length the array.

Output

For each operation of 3rd type, output the required answer in separated line.

Example

Input:
5 3
42 18468 6335 26501 19170
2 4 29359
2 5 5706
3 2 5 5706 Output: 1

Added by:Raihat Zaman Neloy
Date:2014-10-17
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2017-10-22 13:55:03 Shivam Garg
Thanks BlueMary. :D

Last edit: 2017-10-22 14:20:19
2017-10-20 08:36:38 [Rampage] Blue.Mary
My program has complexity near O(N+Q)*sqrt(N+Q)) and easily passed. I think the key is not complexity(sqrt(N) or log^2(n) has little difference), but small constant factor in your program.
2017-10-20 08:07:09 Shivam Garg
Can log^2 N per query pass?
2016-11-14 18:02:07
can anyone explain question type 1 with an example?
2014-12-02 19:17:25 Min_25
@Raihat Zaman Neloy
Tough problem. Thanks for setting this problem.

@abdou_93
1 <= y <= 10^5. (checked by assertion)

Last edit: 2014-12-02 19:21:03
2014-11-29 06:49:19 abdou_93
@Raihat Zaman Neloy. what is the constraint for y
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.