### Mujh_lui's blog

By Mujh_lui, history, 5 years ago,

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

| Write comment?
 » 5 years ago, # |   0 Wait for codechef sept18 long challenge to get over. ANDSQR Our Editorialist : vijju123 will answer all your question once contest gets over.
•  » » 5 years ago, # ^ |   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
•  » » » 5 years ago, # ^ |   0