A Kth Root Subarray

3.3

7 votes
Advanced Data Structures, Data Structures, XOR, Hashing algorithm, Lazy Propagation in Interval/Segment Trees, Number theory
Problem

The problem statement is simple.

You are given an array of N integers. You have to answer queries of three types.

  • 1 L R            :   Determine if the subarray [ AL , AL+1 , AL+2 , .....   AR ] is special or not. 
  • 2 L R X Y     :    Multiply all the elements of the subarray  [ AL , AL+1 , AL+2 , .....   AR ] by XY.
  • 3 L R X        :    Reset all the elements of the subarray [ AL , AL+1 , AL+2 , .....   AR ] to value X.

Let val=Ri=LAi = Product of the subarray [ AL , AL+1 , AL+2 , .....   AR ]

A subarray is special if Kval  is a integer . In other words the Kth root of product of the subarray should be a integer.

 

Input Format

First line contains three integers N K Q.

Next line contains integers A1 , A2 , A3 , .....   AN .

Next lines contains one of the three types of queries.

 

Constraints

  • 1 <=  N <= 105
  • 1 <= Q <= 5*104 ,
  • 1 <= Ai , X , Y <= 106
  • 1 <= L<=R <= N
  • 1 <= K <= 30000

 

Output

For each query of type 1 , print Yes if the subarray is special else No

   

Time Limit: 2.5
Memory Limit: 256
Source Limit:
Explanation

Array during first query : A =  [ 2  2  2  2  2  2  2  2  2  2  3 ]

A[10] * A[11] = 6 which doesnot have a integer square root.

Array during second query : A =  [ 2  2  2  2  2  2  2  2  2  2  3 ]

A[4] * A[5] * A[6] * A[7] = 16 which has a integer square root = 4

Array after third query : A =  [ 2  2  2  2  3  3  2  2  2  2  3 ]

For 4th query :

A[4] * A[5] * A[6] * A[7] = 36 which has a integer square root = 6

Array after 5th query : A = [ 2  2  6  6  9  3  2  2  2  2  3 ]

For 6th query :

A[3] * A[4] * A[5] * A[6] =  972 which doesnot have a integer square root

Editor Image

?