題干：

The shorter, the simpler. With this problem, you should be convinced of this truth.?
???
??You are given an array?AA?of?NN?postive integers, and?MM?queries in the form?(l,r)(l,r). A function?F(l,r)?(1≤l≤r≤N)F(l,r)?(1≤l≤r≤N)?is defined as:?
F(l,r)={AlF(l,r?1)?modArl=r;l<r.F(l,r)={All=r;F(l,r?1)?modArl<r.?
You job is to calculate?F(l,r)F(l,r), for each query?(l,r)(l,r).

Input

There are multiple test cases.?
???
??The first line of input contains a integer?TT, indicating number of test cases, and?TT?test cases follow.?
???
??For each test case, the first line contains an integer?N(1≤N≤100000)N(1≤N≤100000).?
??The second line contains?NN?space-separated positive integers:?A1,…,AN?(0≤Ai≤109)A1,…,AN?(0≤Ai≤109).?
??The third line contains an integer?MM?denoting the number of queries.?
??The following?MM?lines each contain two integers?l,r?(1≤l≤r≤N)l,r?(1≤l≤r≤N), representing a query.

Output

For each query(l,r)(l,r), output?F(l,r)F(l,r)?on one line.

Sample Input

1 3 2 3 3 1 1 3

Sample Output

2

題目大意：

有n個(gè)數(shù)，m個(gè)查詢，每個(gè)查詢有一個(gè)區(qū)間[L, R], 求ans, ans = a[L]%a[L+1]%a[L+2]%...%a[R];

解題報(bào)告：

其實(shí)可以不用求區(qū)間[l,r]的，可以直接求后綴[l,n]的，可以簡化代碼。（比求區(qū)間的簡單，并且肯定滿足題意）這題還可以用RMQ+二分來代替線段樹求解。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int a[MAX]; int n,q; struct TREE {int l,r;int mi; } tr[MAX<<2]; void pushup(int cur) {tr[cur].mi = min(tr[cur*2].mi,tr[cur*2+1].mi); } void build(int l,int r,int cur) {tr[cur].l = l,tr[cur].r = r;if(l == r) {tr[cur].mi = a[l]; return ;}int m = (l+r)>>1;build(l,m,cur*2);build(m+1,r,cur*2+1);pushup(cur); } int query(int pl,int pr,int val,int cur) {if(tr[cur].l == tr[cur].r) {if(tr[cur].mi <= val) return tr[cur].l;else return n+1;}if(pl <= tr[cur].l && pr >= tr[cur].r) {if(tr[cur*2].mi <= val) return query(pl,pr,val,cur*2);else if(tr[cur*2+1].mi <= val) return query(pl,pr,val,cur*2+1);else return n+1;}int res = n+1;if(pl <= tr[cur*2].r) res = query(pl,pr,val,cur*2);if(res != n+1) return res;if(pr >= tr[cur*2+1].l) return query(pl,pr,val,cur*2+1); else return n+1; } int main() {int T;cin>>T;while(T--) {scanf("%d",&n);for(int i = 1; i<=n; i++) scanf("%d",a+i);build(1,n,1);scanf("%d",&q);for(int l,r,i = 1; i<=q; i++) {scanf("%d%d",&l,&r);int ans = a[l];l++;while(l <= r && ans != 0) {int x = query(l,r,ans,1);if(x <= r) ans %= a[x];l = x+1;}printf("%d\n",ans);} }return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 5875】Function（线段树，区间第一个小于某个数的数 或 RMQ二分）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。