с массивом и несколькими запросами. Каждый запрос может быть одного из следующих двух типов:
1.Рассчитайте запрос, где задан диапазон индексов, найдите наибольший общий делитель (GCD) среди всех чисел в этом диапазоне
2. Обновите запрос, если указан диапазон индексов, умножьте все числа в диапазоне на указанное число
.
Я пытался использовать ленивое дерево сегментов, но не смог пройти тестовые наборы (пример теста пройден)
import java.io.*;
import java.util.*;
class Create1{
int tree[];
int lazy[];
Create1(int n,int a[])
{
int x=2*(int)Math.pow(2,(int)Math.ceil(Math.log(n)/Math.log(2)))-1;
tree=new int[x];
lazy=new int[x];
MakeStree(tree,a,0,n-1,0);
}
int getMid(int a,int b)
{
return (a+b)/2;
}
// make segment tree
private void MakeStree(int ar[],int a[],int low,int high,int pos)
{
if(low==high)
{
ar[pos]=a[low];
return;
}
int mid=getMid(low,high);
MakeStree(ar,a,low,mid,2*pos+1);
MakeStree(ar,a,mid+1,high,2*pos+2);
ar[pos]=gcd(ar[2*pos+1],ar[2*pos+2]);
// System.out.println(ar[pos]+" "+ar[2*pos+1]+" "+ar[2*pos+2]);
}
private void updateVal(int low,int high,int val,int sglow,int sghigh,int index)
{
if(lazy[index]!=0)
{
tree[index]*=lazy[index];
if(sglow!=sghigh)
{
lazy[2*index+1]=lazy[2*index+2]=lazy[index];
}
lazy[index]=0;
}
if(low<=sglow && high>=sghigh)
{
tree[index]*=val;
if(sglow!=sghigh)
{
lazy[2*index+1]=lazy[2*index+2]=val;
}
return;
}
else if(low>sghigh || high<sglow)
{
return;
}
updateVal(low,high,val,sglow,(sglow+sghigh)/2,2*index+1);
updateVal(low,high,val,(sglow+sghigh)/2+1,sghigh,2*index+2);
tree[index]=gcd(tree[2*index+1], tree[2*index+2]);
}
public void update(int low,int high,int val,int n)
{
if(low<0 || high>n-1)
return ;
updateVal(low ,high,val,0,n-1,0);
}
private int findMin(int low,int high,int sglow,int sghigh,int index)
{
if(lazy[index]!=0)
{
// System.out.println("hdhhd"+index);
tree[index]*=lazy[index];
if(sglow!=sghigh)
{
lazy[2*index+1]=lazy[2*index+2]=lazy[index];
}
lazy[index]=0;
}
if(low<=sglow && high>=sghigh)
{
return tree[index];
}
else if(low>sghigh || high<sglow)
return 0;
int temp= gcd(findMin(low,high,sglow, (sglow+sghigh)/2,2*index+1),findMin(low,high,(sglow+sghigh)/2+1,sghigh,2*index+2));
// System.out.println(sglow+" "+sghigh);
// System.out.println(temp+" "+findMin(low,high,sglow, (sglow+sghigh)/2,2*index+1)+" "+findMin(low,high,(sglow+sghigh)/2+1,sghigh,2*index+2));
return temp;
}
public int Min(int low,int high,int n)
{
if(low<0 || high>n-1)
return 0;
return findMin(low, high, 0, n-1, 0);
}
static int gcd(int a,int b)
{
if(a==0)
return b;
else
return gcd(b%a,a);
}
}
class Cheating{
public static void main(String[] args) throws IOException{
Scanner s1=new Scanner(System.in);
int t=s1.nextInt();
while(t--!=0)
{
int n=s1.nextInt();
int k=s1.nextInt();
int ar[]=new int[n];
for(int i=0;i<n;i++)
{
ar[i]=s1.nextInt();
}
Create1 c =new Create1(n,ar);
for(int i=0;i<k;i++){
int temp=s1.nextInt();
if(temp==1)
{
int a=s1.nextInt();
int b=s1.nextInt();
System.out.println(c.Min(a, b, n));
}
else if(temp==2)
{
int a=s1.nextInt();
int b=s1.nextInt();
int p=s1.nextInt();
c.update(a, b, p, n);
}
// System.out.println("hshsh");
}
}
}
}