Блог

учитывая массив и некоторые запросы, каждый запрос может иметь один из следующих двух типов: 1. Вычислить запрос, где задан диапазон индексов, найти наибольший общий делитель (НОД) всех чисел в этом диапазоне 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 amp;amp; 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 amp;amp; 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 amp;amp; 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 просто выполните lazy[]*=val