Function

Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1083    Accepted Submission(s): 413

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

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

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

Sample Input
1 3 2 3 3 1 1 3
 

Sample Output
2
 【题意】 给一个区间L和R，求a[L]%a[L+1]%a[L+2]...%a[R]。
【一个补充】 a%b，如果a小于b，那么a不变，否则，得到的数小于等于a/2。 那么每次取余以后都会减半，那么复杂度就是log级别的了。
【解题方法】我们每次找出[L+1,R]中第一个不比最左边的数大的数的位置，并不断的缩小区间即可。关于如何找，这里用了线段树来维护一个区间内的最小值，那么我们就可以用线段树找出我们需要的东西了。。。当然这个东西也可以用单调栈来维护，然而最想不到的是竟然可以O(n^2)的暴力预处理，WTF。
【AC 代码1】 线段树维护
 
//
//Created by just_sort 2016/9/12 09:48
//Copyright (c) 2016 just_sort.All Rights Reserved
//

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100010;
struct node{
    int l,r,minn;
}Tree[maxn*4];
int a[maxn];
void pushup(int rt)
{
    Tree[rt].minn=min(Tree[rt*2].minn,Tree[rt*2+1].minn);
}
void Build(int l,int r,int rt){
    Tree[rt].l=l,Tree[rt].r=r;
    if(l==r){
        Tree[rt].minn=a[l];
        return ;
    }
    int mid=(l+r)/2;
    Build(l,mid,rt*2);
    Build(mid+1,r,rt*2+1);
    pushup(rt);
}
int queryans(int L,int R,int val,int rt)
{
    if(Tree[rt].l==Tree[rt].r){
        if(Tree[rt].minn<=val) return Tree[rt].l;
        else return -1;
    }
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    int ans=-1;
    if(L<=mid&&Tree[rt*2].minn<=val) {
        ans = queryans(L,R,val,rt*2);
        if(ans==-1){
            if(mid<R&&Tree[rt*2].minn<=val) ans=queryans(L,R,val,rt*2+1);
        }
        return ans;
    }
    else if(mid<R&&Tree[rt*2+1].minn<=val) return queryans(L,R,val,rt*2+1);
    return -1;
}
int main()
{

    int T,n;scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++) scanf("%d",&a[i]);
        Build(1,n,1);
        int q,l,r;
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d",&l,&r);
            int now=a[l];
            while(l<r){
                l=queryans(l+1,r,now,1);
                if(l==-1) break;
                now%=a[l];
            }
            printf("%d\n",now);
        }
    }
    return 0;
}

【AC 代码2】单调栈维护 
//
//Created by just_sort 2016/9/12 09:48
//Copyright (c) 2016 just_sort.All Rights Reserved
//
<span style="font-family:'Microsoft YaHei';">//这份代码是直接拔过来的，单调栈不会，顺便学习一下。
</span>
#include <stack>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int a[N],nxt[N];
stack<int> s;
int main(){
    int T,n,m,l,r;
    cin >> T;
    while(T --){
        memset(nxt,-1,sizeof(nxt));
        while(!s.empty()) s.pop();
        cin >> n;
        for(int i = 1 ; i <= n ; i ++) scanf("%d",&a[i]);
        cin >> m;
        for(int i = 1 ; i <= n ; i ++){
            // 单调递增的栈。
            if(s.empty() || a[i] >= a[s.top()]) s.push(i);
            else{
                while(!s.empty() && a[i] < a[s.top()]){
                    nxt[s.top()] = i;
                    s.pop();
                }
                s.push(i);
            }
        }
        while(m --){
            scanf("%d%d",&l,&r);
            int ret = a[l] , tmp = l;
            while(nxt[tmp] <= r && nxt[tmp] != -1){
                tmp = nxt[tmp];
                ret = ret % a[tmp];
            }
            cout << ret << endl;
        }
    }
    return 0;
}