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 & 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 3
42 18468 6335 26501 19170
2 4 29359
2 5 5706
3 2 5 5706
Output: 1
hide comments
Shivam Garg:
20171022 13:55:03
Thanks BlueMary. :D Last edit: 20171022 14:20:19 

[Rampage] Blue.Mary:
20171020 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:
20171020 08:07:09
Can log^2 N per query pass?


spk:
20161114 18:02:07
can anyone explain question type 1 with an example? 

Min_25:
20141202 19:17:25
@Raihat Zaman Neloy


abdou_93:
20141129 06:49:19
@Raihat Zaman Neloy. what is the constraint for y 
Added by:  Raihat Zaman Neloy 
Date:  20141017 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 