2016 大連網賽---Function(單調棧)，2016---function

2016 大連網賽---Function(單調棧)，2016---function

題目鏈接

http://acm.split.hdu.edu.cn/showproblem.php?pid=5875

 

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   Source 2016 ACM/ICPC Asia Regional Dalian Online   Recommend wange2014   |   We have carefully selected several similar problems for you:  5877 5876 5874 5873 5872    題意：一個長度為n的數列，q次詢問，每次輸入l 和 r 表示一個區間A[l]~A[r]  求A[l]%A[l+1]A[l+2]...A[r];   思路：a%b=r  那麼r<a 所以在區間連續取余中 如果一個數對A[i]取完余，後面的數大於A[i],則不用取余，所以只需要找A[i]後小於A[i]且最近的A[j]進行取余，依次進行下去。其實找距離最近且小於自己的數就是 單調棧，這個算法很神奇，復雜度為O（n）；   代碼如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
int A[100005];
int pos[100005];
int s[100005];

int main()
{
    int T,N,M;
    cin>>T;
    while(T--)
    {
        scanf("%d",&N);
        for(int i=1;i<=N;i++)
            scanf("%d",&A[i]);
        int num=1;
        A[N+1]=-1;
        s[1]=N+1;
        for(int i=N;i>=1;i--)///單調棧；
        {
            while(A[i]<A[s[num]]) num--;
            pos[i]=s[num];
            s[++num]=i;
        }
        scanf("%d",&M);
        while(M--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            int tmp=A[l];
            while(l<=r)
            {
                if(tmp==0) break;
                if(pos[l]>r) break;
                tmp=tmp%A[pos[l]];
                l=pos[l];
            }
            printf("%d\n",tmp);
        }
    }
    return 0;
}