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

How to solve the problem ?
Автор Mujh_lui, история, 6 лет назад, По-английски

How to find the number of contiguous subsequences in a given range ?

Example :

4 (N)

1 2 3 4 (array[i])

2 4 (Query)

Need to find the number of contiguous subsequences from 2 to 4 whose value is a perfect square.

Explanation :

{ 2 & 3 & 4 } = 0 (Perfect Square)

{ 3 & 4 } = 0 (Perfect Square )

{4 } = 4 (Perfect Square )

Range:

N <=10^5 Q<=5*10^5 (Query)

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

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

Wait for codechef sept18 long challenge to get over. ANDSQR
Our Editorialist : vijju123 will answer all your question once contest gets over.

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

    You have an array, Arr[1...N]. Initially, all values of Arr[i]=0. The array supports the following two types of queries:

    1.Increase all Arr[k] by C for all k≡A (mod B);

    2.Output Arr[D] for a given D.

    The first two lines of input consists of two integers, N and Q, representing the length of the array and the number of queries, respectively. Note that 1≤N,Q≤200000.

    The following Q lines all begin with an integer T representing the type of query. If T=1, then it will be followed by three integers representing A, B and C respectively. Note that 1≤C≤10000, 0≤A<B≤N. Else, T will be 2, and it will be followed by one integer representing D, subjected to 1≤D≤N.

    For each query of type 2, output the integer value of Arr[D] on a separate line.

    https://open.kattis.com/contests/asiasg18-prelim-open/problems/modulodatastructures

    How to solve the problem?

    → Ответить