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
1 3 2 3 3 1 1 3
Sample Output
2
Source
这个题目完全可以出个单调递减的序列卡时间啊...不知道时间复杂度怎么降下来的..因为右边比当前数大的数字是造不成影响的,所以我们用单调栈预处理出每个的右边,这样就可以跳着找了..但是我觉得数据强点不靠谱啊..
///pro do this : a[l]%a[l+1]%...%a[r]#include#include #include #include #include #include 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;}
