给定一个数组和一些查询 每个查询可以是以下两种类型之一: 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");
}
}
}
}
最佳答案
你偷懒的方式是错误的。
让我们考虑这个 if 语句:
if(low<=sglow && high>=sghigh)
{
tree[index]*=val;
if(sglow!=sghigh)
{
lazy[2*index+1]=lazy[2*index+2]=val;
}
return;
}
如果您对同一范围进行 2 个查询，以值 x 增加，而其他查询则按 y 增加，会发生什么？
第一次更新后lazy[2*index+1] = x到目前为止一切正常
第二次更新后lazy[2*index+1] = y，而它应该是x*y
您应该为惰性数组1设置默认值，并且当您更新惰性时只需执行lazy[]*=val
关于java - 在一定范围内找到 gcd 并更新，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55772896/