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

Help Needed in a question !!
Автор siddhi, история, 6 лет назад, По-английски

A sequence is interesting if the greatest common divisor of all the elements from the sequence is greater than 1. Each query can be of two types: 1. Change the value at position X in the sequence to V. 2. Determine the number of interesting contiguous subarrays contained in the interval [L, R] sequence. The first line of input contains the numbers N and Q (1 <= N, Q <= 100000), representing the number of elements in the sequence and number of queries, respectively. The following line contains N natural numbers, A[i] (1 <= A[i] <= 1000000000) that represent the numbers in the initial sequence. Each of the following Q queries contains a query in the following form: 1. The first number in line can be 1 or 2 denoting the type of query. 2. If the query is of type 1, two numbers follow, X (1 <= X <= N) and V (1 <= V <= 1000000000). 3. If the query is of type 2, two numbers follow, L and R (1 <= L, R <= N), that represents the left and right interval boundary.

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

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

Lets consider starting at position L and walking forwards, keeping a list of all possible gcds and the lowest index that can start each of them as we go. We can do this in (R — L) log (10e10) because for each gcd in our list from smallest to greatest we must be a factor of the next largest gcd, therefore the largest our list can be is # of factors of A[i], which is limited to log(10e10). To keep a running count of interesting ranges, at each step we add count (i — smallest non-1 gcd index) to our running count, as that's how many interesting ranges there are with this as a right-endpoint.

Now, instead of walking linearly lets consider how we could combine two of these lists facing different directions — Say we have the list from walking forwards L->i and the list from walking backwards R->i+1. We can combine these lists and form a new rightwards-facing list for L->R by taking each gcd from the right part and applying it to the left part as if it was the next A[i]. This captures all the different transitions we might have made walking rightwards, but takes log(10e10) time instead of (R — i) time. We can do a similar combination to get a new leftwards-facing list. To keep track of our running total we multiply ranges, as each step represents some range of start points and end points with an identical gcd.

Now that we have a segment combination function we can use a segment tree to solve all the queries in Q*log(N)*log(10e10) time total.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I have 2 doubts

    I didn't understand this portion "This captures all the different transitions we might have made walking rightwards, but takes log(10e10) time instead of (R — i) time."

    2.

    How will keeping track of only distinct prime factors work and not keeping track of factors? Say for 2 and 3 how will count of the subarrays twice with gcd(6) be avoided?

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

      I'll address 2 first.

      We don't need to keep track of prime factors. I use factorizing to prove that whenever we have some right endpoint i there is at most log(10e10) different gcds that can occur on any range [j, i].

      To illustrate, lets consider the ranges [i, i], [i-1, i], ... [j, i]. The range [i, i] has some number K = A[i] as its gcd. Now, for range [i-1, i] we have a few possibilities. We can have A[i-1] be x * K, so we stay at K. This doesn't introduce a new gcd. Alternately we can have gcd(A[i-1], K) < K. In that case we know gcd(A[i-1], K) <= K/2, as otherwise we cannot satisfy gcd(A[i-1], K) divides K evenly. This could introduce a new gcd, but our K is at least halved. Similar logic applies to each A[i-x]. Since you can only halve K log(K) times, we therefore know that there is at most log(K) different gcds.

      Now on 1. When we're walking rightwards we must have many ranges where gcd over [i, j] == gcd over [i, j + 1]. Whenever we have such a range we can group it into a single transition because we're guaranteed that gcd over [k, j] == gcd over [k, j + 1] with k <= i, because we can decompose it into gcd(gcd over [k, i — 1], gcd over [i, j] == gcd over [i, j + 1]).

      Since we've guaranteed from the above that there are less than log(K) different gcd values with a given endpoint, we thus know that there are at most log(K) values for j on a range such that gcd over [i, j] != gcd over [i, j + 1] and therefore we have at most log(K) groups.

      → Ответить
  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can u please explain it by giving some example please!

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

My solution: Keep segment tree, that supports queries of the form "Find the GCD of some interval" and updates "Change the value at position X". Now for each position i calculate what is the biggest j, such that the GCD of the numbers in the interval [i; j] is greater than 1. Let this index be f(i). This could be done with binary search. Now for each query [l; r] the answer is the sum of the following for each i from l to r: min(f(i), r+1) — l. Now build a segment tree from treaps, such that every treap supports subtree sum and size queries. (The segment tree is over the indexes and the treaps are over the f(i)-s). This way you can handle the query in O(log(n)^2) by just finding the sum and the number of f(i)-s smaller than r+1 in the segment [l; r] (this way you know the number of the bigger f(i)-s). The update is: 1)Change the number and update the segment tree for the GCD-s 2)Update f(i) using binary search in O(log(n)^2). 3)Update the segment tree of treaps in O(log(n)^2). Overall complexity O((n+q)*log(n)^2).

→ Ответить