Блог пользователя National_Wind

Автор National_Wind, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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.