Given n numbers and m queries

each number a[i] satisfy this condition: 1<=a[i]<=N

there are two types of queries:

1 idx val : set the value of a[idx] to val : 1<=val<=N

2 l r : the answer is "yes" if there is a repeated value in the interval from l to r otherwise : the answer is "no".

n,m<=10^5

thanks in advance.

Given n numbers and m queries for each query (L R) find the most frequent number from L to R and how many times it occurs in this interval

for example:

input:

7 3

3 5 3 5 5 3 3

2 4

3 3

1 3

output:

5 2

3 1

3 2

thanks in advance.

I wonder if you could help me solving this problem:

there is N items and initially all of them is 0 ... and for each item there is a cost value which is also initially 0.

you have to implement a data structure which can do this operations in o(log n) time:

1. set the lower bound of numbers from L to R to k.

2. decrease the value of numbers from L to R by v ... and each number become negative we increase the cost of it by its negative value and set its value to zero again (ex. after decreasing a number become -5 we increase the cost of this number by 5 and set the value of this number to 0).

3. print the cost of the k-th number.

I try to implement it using segment tree .. but I found a problem in lazy propagation...

any help would be appreciated ... sorry for my bad english .

thanks.

Any one has the test cases for previous APIO contests ? thanks in advance.