National_Wind's blog

Sum of distinct numbers
By National_Wind, history, 3 years ago, In English

Hey guys!

Today I want to ask about this problem.

Given an array A size N and q queries. (|A[i]| <= 1e5, N <= 1e5, q <= 1e5)

Define F(B), B is a subarray (consecutive) of array A, is the number of distinct values of B. For example: F({1, 2, 3, 4}) = 4

For every query i x, change value A[i] to x, and calculate the sum of all F(B) in the new array A. For a query when A = {1, 1, 2}

  • F({1}) = F({1}) = F({2}) = F({1, 1}) = 1;
  • F({1, 2}) = F({1, 1, 2}) = 2;

The sum result is 1 * 4 + 2 * 2 = 8;

Test: Input

4

1 2 3 4

3

1 1

2 1

3 1

Output

20

17

13

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the first part of this problem, you can probably make a segment tree which contains a set at each of its nodes.

I'm not entirely sure about the second part (sum of all subarrays), but I might have seen a similar problem in the segment tree EDU section before.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I don't see how your idea would work without spending a lot of time merging sets for each query.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Make an array $$$B$$$ such that $$$B[i]$$$ is the least $$$j > i$$$ with $$$A[i] = A[j]$$$ or $$$\infty$$$ if such $$$j$$$ doesn't exist. It is easy to see that an update to $$$A$$$ triggers $$$O(1)$$$ updates to $$$B$$$.

Now the queries become "count elements in range $$$l \ldots r$$$ with $$$B[i] > r$$$" which you can solve with sone 2D stuff.

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

The number of distinct elements in the subarray is the same as the number of elements in the subarray that are the first with their value.

So we can reverse the order of counting and for each element $$$i$$$ calculate the number of subarrays where there is no same element to the left. If we know $$$left(i)$$$ which is the largest $$$j<i$$$ with $$$A[j]=A[i]$$$ (or $$$0$$$ if there is no such $$$j$$$) then the number of such subarrays is $$$(i-left(i)) \times (n-i+1)$$$.

As -is-this-fft- stated, an update will change at most three $$$f(i)$$$, so you can maintain them in set and simply recalculate the contribution of changed values.

→ Reply