Function

Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 1498    Accepted Submission(s): 553 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]大的数，取余不变，主要看比a[l]小的数，所以在区间里找第一个比a[l]小的数， 然后继续在剩下的区间里面找比取完余的a[l]小的数 #include <iostream> #include <string.h> #include <stdio.h> #include <algorithm> #include <math.h> #include <string> #include <stdlib.h> #include <vector> using namespace std; const int maxn=1e5; int cmin[maxn*4+5]; int a[maxn+5]; int n,m; int l,r; int x; void PushUp(int node) { cmin[node]=min(cmin[node<<1],cmin[node<<1|1]); } void build(int node,int begin,int end) { if(begin==end) { scanf("%d",&x); cmin[node]=x; a[begin]=x; return; } int m=(begin+end)>>1; build(node<<1,begin,m); build(node<<1|1,m+1,end); PushUp(node); } bool tag; int minn; int pos; void query(int node,int begin,int end,int left,int right,int value) { if(value<cmin[node]) return; if(begin==end) { minn=cmin[node]; pos=begin; tag=true; return; } int m=(begin+end)>>1; if(left<=m) query(node<<1,begin,m,left,right,value); if(tag) return; if(right>m) query(node<<1|1,m+1,end,left,right,value); } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&n); build(1,1,n); scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&l,&r); tag=false; int x=a[l]; if(l==r) { printf("%d\n",x); continue; } query(1,1,n,l+1,r,x); if(!tag) printf("%d\n",x); else { while(1) { tag=false; x%=minn; if(pos+1>r) { printf("%d\n",x); break; } query(1,1,n,pos+1,r,x); if(!tag) { printf("%d\n",x); break; } } } } } return 0; }