全部从我大哥那里学习得来。。
一开始硬着头皮就是根据思路上线段树，明知是T还要写（因为线段树还不是很熟，趁机练一发）
后来果然T了，然后就去学了一发RMQ的ST算法，查询是O(1)。
ST算法主要：
//把dp[i，j]平均分成两段
//（因为dp[i，j]一定是偶数个数字），从 i 到i + 2 ^ (j - 1) - 1为一段，
//i + 2 ^ (j - 1)到i + 2 ^ j - 1为一段(长度都为2 ^ (j - 1))。
然后就在两秒内AC了…
主要是想证明那个复杂度的理解吧。
如果a>=b,那么a%b<=a/2;
那么我们每次对当前找最近小的那个，通过二分区间(O(logn))然后RMQ的查询是O(1)那么最终常熟复杂度还是log(A[i])了，总的复杂度就理所当然是qO(logn)O(logA[i])。然后叉姐题解说是卡常数。。= =、汗
下面引述我大哥的…
原文链接：http://www.wonter.net/index.php/archives/1012/
思路：
对于每一个 [l, r] 区间，也就是求 a[l] % a[l + 1] % a[l + 2] + … + a[r]
直接暴力肯定会 T 的，但我们会发现。如果一个数 % 一个比它大的数字，实际上这个数字是不变的，所以对于每个询问，我们只需要每次 % 一个比当前结果小的就好了
我们可以使用 rmq 求区间最小值，然后二分求出距离当前这个位置最近的而且小于当前结果的数，然后 % 它，更新位置和答案即可。
#include <bits/stdc++.h>
using namespace std;
int arr[100010];
int dp[100010][20];
int mm[100010];
int n;
void RMQInit()
{
mm[0] = -1;
for(int i = 1;i <= n;++i)
{
mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];
dp[i][0] = arr[i];
}
for(int j = 1; j <= mm[n]; ++j)
{
for(int i = 1; i + (1 << j) - 1 <= n; ++i)
{
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
}
}
int Query(int l, int r)
{
int t = mm[r - l + 1];
return min(dp[l][t], dp[r - (1 << t) + 1][t]);
}
int GetPos(int l, int r, int x)
{
int left = l, right = r;
while(left < right)
{
int mid = left + ((right - left) >> 1);
if(Query(l, mid) <= x)
right = mid;
else
left = mid + 1;
}
if(arr[left] <= x)
return left;
return -1;
}
int main()
{
//freopen("1.in", "r", stdin);
int T;
while(scanf("%d", &T) == 1)
{
while(T--)
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &arr[i]);
RMQInit();
int q;
scanf("%d", &q);
for(int i = 1; i <= q; ++i)
{
int l, r;
scanf("%d%d", &l, &r);
int ans = arr[l];
while(l != r)
{
int pos;
pos = GetPos(l + 1, r, ans);
if(pos == -1)
break;
l = pos;
ans %= arr[l];
}
printf("%d
", ans);
}
}
}
return 0;
}