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)

Wait for codechef sept18 long challenge to get over. ANDSQR

Our Editorialist : vijju123 will answer all your question once contest gets over.

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?

Check Here :P