ADACROP  Ada and Harvest
As you might already know, Ada the Ladybug is a farmer. She has a very long furrow with many kinds of vegetables (represented by integer numbers). Whenever she wants to harvest a single vegetable, she always replace it with another vegetable (possibly same kind).
After each replacement, she wants to know the number of vegetables of the same kind (at the new vegetable) which are before it (have lower position in furrow).
Input
The first line of input contains 1 ≤ N, Q ≤ 2*10^{5} , the length of furrow and number of harvests.
The next line contains N numbers 0 ≤ A_{i} ≤ 10^{9} the kind of vegetable which is currently on i^{th} spot in furrow (indexed from 0).
The next Q lines contains two numbers 0 ≤ i < N (the index of harvested plant) and 0 ≤ a ≤ 10^{9} (the kind of newly planted vegetable)
Output
For each harvest, print the number of vegetables of the same kind before the newly planted vegetable.
Example Input
5 5 1 2 1 2 1 2 2 4 2 2 3 3 3 4 3
Example Output
1 3 0 1 2
Example Input 2
10 10 2 3 5 3 9 3 5 2 9 9 7 2 0 5 0 2 1 2 9 2 4 3 8 2 4 2 2 5 3 5
Example Output 2
1 0 0 1 3 1 3 2 0 1
hide comments
soumyadeep70:
20220831 15:04:47
I'm using bit with map as a node but still tle....wtf !! It's complexity is n(log^2n) 

changyouren:
20210922 15:58:23
treap array 

likhon5:
20200915 18:58:12
can be solved by policy based data structure, complexity (nlogn) Last edit: 20200915 18:58:42 

jonathanpl:
20200830 01:52:04
Also any O(nlog^2n) aproach (as segment tree with a map as a node) give TLE, this problem(as many others in this site) is a bad joke... Last edit: 20200830 02:09:05 

jonathanpl:
20200830 01:50:09
Approach dinamic segment tree + index compresion for each value O(nlogn) give TLE WTF??? 

mhasan01:
20200706 21:32:50
Accepted using Treap :)


daviddamian01:
20200523 17:46:26
Tried a treap with buckets (both map and unordered_map) and then segment tree with buckets (the same). Both data structures got TLE. 

urielguz33:
20200131 08:02:03
Changing unordered_map to map as xteq said changed my veredict from TLE to ACC for some reason, I thought unordered maps were supposed to be faster... 

xteq:
20190716 01:16:08
Do not use std::unordered_map with standard hashing function! It costed me many TLEs. 

DK...:
20190318 14:10:08
nlog(n) works fine! 
Added by:  Morass 
Date:  20170911 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 