Function HDU-5875-セグメントツリー型取り

This way
タイトル:
区間l,rの中でa[l]%a[l+1]%a[l+2]%a...a[r]はいくらですか.
問題:
セグメントツリーを使えばいいです.この区間内の最初の値が現在の余剰数以下の値をクエリーするたびにいいです.どうしてこれが正しいのですか.まず時間複雑度の問題であり,a>=b,a%b=cと仮定すると,c<=a/2は一定に成り立つ.従って時間複雑度はO(nl o g n 2)O(nlogn^2)O(nlogn 2)である.次に、なぜ現在の残高以下の最初のクエリを行うのかという質問です.まず、6%4%3=2ですが、6%3%4=0なので、順序は変更できません.それより小さいモジュールを通過すると、この値は必ず変更されます.そのため、最初のモジュールがそれ以下のモジュールを確認する必要があります.

#include
using namespace std;
const int N=1e5+5;
int mi[N*4],a[N];
void build(int l,int r,int root)
{
    if(l==r)
    {
        mi[root]=a[l];
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,root<<1);
    build(mid+1,r,root<<1|1);
    mi[root]=min(mi[root<<1],mi[root<<1|1]);
}
int query(int l,int r,int root,int ql,int qr,int val)
{
    if(l==r)
        return mi[root];
    if(l>=ql&&r<=qr)
    {
        int mid=l+r>>1;
        if(mi[root<<1]<=val)
            return query(l,mid,root<<1,ql,qr,val);
        return query(mid+1,r,root<<1|1,ql,qr,val);
    }
    int mid=l+r>>1;
    int ans=2e9;
    if(mid>=ql)
        ans=query(l,mid,root<<1,ql,qr,val);
    if(ans<=val)
        return ans;
    if(midv)
                            break;
                        v%=x;
                        if(!v)
                            break;
                    }
                    printf("%d
",v);
                }
            }
        }
    }
    return 0;
}