Bound on n?

Define unsolvable? Unless I understand it wrong, it is easily solvable in O(n²).

Completly misunderstood the problem, please ignore

maybe there is O(n*sqrt(n)) solution to this problem:

first enum the number of times of number occurs in the result

segments:

times from 1 to sqrt(n) and compute the answer:

for every times enum the postion i of array and count the times of

occurence of current number,if this >times , move the previous pointer

u until it ==times if (i-u)==times*kind answer++;

if times >sqrt(n) anyone has some ideas? I have some solution that is not beautiful and perfect,may it can pass..

Do you have link of this problem??

I have O(nlog²n) solution, but it's not deterministic because of hashes.

Let's solve it using divide-and-conquer algorithm. Suppose, we found number of such intervals, which lies in left or right half of array. Now we should find number of intervals with left border in left half and right border in right half. For such interval let's call number "interesting" if all of it's occurrences lies in one half of array. For example we have array [1, 2, 2, 3, 1, 6] ([1, 2, 2] is a left half). For interval [1, 2, 2, 3, 1] number 2 is interesting, and 1 is not.

Now we can notice, that there are 4 kinds of intervals:

1. No interesting numbers on the left, no interesting numbers on the right.
2. There are interesting numbers on the left, no interesting numbers on the right.
3. No interesting numbers on the left, there are interesting numbers on the right.
4. There are interesting numbers on both sides.

(Cases 2 and 3 are nearly the same).

Let's find number of intervals if type 1.

For any two numbers i and j cntl_i + cntr_i = x and cntl_j + cntr_j = x. We can rewrite it as cntl_i + cntr_i = cntl_j + cntr_j or cntl_i - cntl_j =  - (cntr_i - cntr_j).

Let's look at some interval [l;r] (m is a divide point in divide-and-conquer). For suffix [l;m] and prefix [m + 1;r] let's write array of pairs (number;number_of_its_occurrences). If we'll sort this two arrays by first element, it's clear that for good interval (and only for good interval) first elements in all pairs are equal and differences of second elements of adjacent pairs are equal by absolute values and have different signs (because of this equation cntl_i - cntl_j =  - (cntr_i - cntr_j)).

So we just need to find for each prefix/suffix hash of set of first numbers in pairs and differences of adjacent second elements in pairs. It can be easily done using treaps or any other BST.

Let's move to the second case (and third because of symmetry). Let's again look to array of pairs (number;number_of_its_occurrences) of left part. Numbers which have maximal number of occurrences are "interesting". We shouldn't add them to hash (because we won't have them in right part), but they shows us, how many occurrences of each element we will have in interval. It's quite easy to calculate hash of all values expect "ineteresting" numbers using treap (for example just store two treaps: one for numbers with maximum number of occurrences and one for all other numbers). But now we should consider, that we know number of occurrences of each number. It's quite easy: we just know, how many occurrences of number with minimal value should we have on the right, so we just store pair (hash;how_many_occurrences_of_minimal_number_on_the_right).

Cases 3 and 4 are absolutely similar to 2.

I understand, that my English is terrible and I'm very bad in describing solutions, so feel free to ask if something is hard to understand.

P.S. Looks like we don't even need treaps, simple std::map can do anything we want.

oh, it's from IZHO 2016, i think it will be helpful to understand the problem properly.

http://izho.kz/2016/1%20day.%20contest-en.pdf

Day 1, problem c