## CNTINDX2 - Count The Indexes 2

no tags

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 & 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) & 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 opeation. 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 appers 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 342 18468 6335 26501 191702 4 293592 5 57063 2 5 5706```
```Output:
1
```

hide comments
 Shivam Garg: 2017-10-22 13:55:03 Thanks BlueMary. :D Last edit: 2017-10-22 14:20:19 [Rampage] Blue.Mary: 2017-10-20 08:36:38 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. Shivam Garg: 2017-10-20 08:07:09 Can log^2 N per query pass? spk: 2016-11-14 18:02:07 can anyone explain question type 1 with an example? Min_25: 2014-12-02 19:17: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 abdou_93: 2014-11-29 06:49:19 @Raihat Zaman Neloy. what is the constraint for y

 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