首页 > > 程序设计 > C/C++ >

2016 大连网赛---Function(单调栈)

2018-06-17 23:47:52来源：未知阅读 ()

题目链接

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

Input

There are multiple test cases.

The first line of input contains a integer

Output

For each query

Sample Input

2 3 3

1 3

Sample Output

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;
}