首页 > 代码库 > hdu 5875(单调栈)

hdu 5875(单调栈)

2024-08-13 14:38:01   209人阅读

Function

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


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
132 3 311 3
 

 

Sample Output
2
 

 

Source
2016 ACM/ICPC Asia Regional Dalian Online
 
这个题目完全可以出个单调递减的序列卡时间啊...不知道时间复杂度怎么降下来的..因为右边比当前数大的数字是造不成影响的,所以我们用单调栈预处理出每个的右边,这样就可以跳着找了..但是我觉得数据强点不靠谱啊..
///pro do this : a[l]%a[l+1]%...%a[r]#include <stdio.h>#include <iostream>#include <algorithm>#include <queue>#include <string.h>#include <vector>using namespace std;typedef long long LL;const LL INF = 1e10;const int N = 100005;LL a[N],R[N];int main(){    int tcase,n;    scanf("%d",&tcase);    while(tcase--){        scanf("%d",&n);        for(int i=1;i<=n;i++){            scanf("%lld",&a[i]);        }        memset(R,-1,sizeof(R));        for(int i=n-1;i>=1;i--){ ///单调栈维护其右边小于 a[i] 的第一个数            int t =i+1;            while(true){                if(a[i]>=a[t]){                    R[i] = t;                    break;                }                if(R[t]==-1){                    break;                }                t = R[t];            }            R[i] = t;        }        int m;        scanf("%d",&m);        while(m--){            int l,r;            scanf("%d%d",&l,&r);            LL ans = a[l];            int nxt = l;            while(R[nxt]<=r&&R[nxt]!=-1){                nxt = R[nxt];                ans = ans%a[nxt];            }            printf("%lld\n",ans);        }    }    return 0;}

 

hdu 5875(单调栈)


联系
我们