Mujh_lui's blog

How to solve the problem ?
By Mujh_lui, history, 6 years ago, In English

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)

  • Vote: I like it
  • -29
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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?

    → Reply