题意：给你一个长为n的序列，给定q次查询区间，若l==r,输出A[ l ],若区间长度不为一，输出区间最左边的数一直模一直模模区间的右边，一直到区间右端点。
方法1：对于一个数而言，模比他大的数等于它本身，所以取模操作只对比它小的数有意义，所以我们对于一个区间，若长度不等于0，若是能快速求出有哪些数比区间左端点小，然后不断取模即可，那对于一段区间，怎么求出有哪些数比它小呢，我们可以用到单调栈或者线段树。对于单调栈而言，栈内元素的下一个就是第一个比它小的数，那么它的下下一个同样也比它小，我们用单调栈求得pos【i】，pos【i】代表第一个比i下标的数字小的下一个数字的下标，利用pos【i】我们就可以进行查询操作了；
AC代码：
1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstring> 5 #include <set> 6 using namespace std; 7 int A[100005]; 8 int pos[100005]; 9 int s[100005]; 10 11 int main() 12 { 13 int T,N,M; 14 cin>>T; 15 while(T--) 16 { 17 scanf("%d",&N); 18 for(int i=1;i<=N;i++) 19 scanf("%d",&A[i]); 20 int num=1; 21 A[N+1]=-1; 22 s[1]=N+1; 23 for(int i=N;i>=1;i--)///单调栈； 24 { 25 while(A[i]<A[s[num]]) num--; 26 //s[i]用于辅助pos，是s[num]代表从当前数字往右第一大的下标，num--表示后面的数字太大，寻找第一个比自己小的数字 27 pos[i]=s[num];//pos[i]为比i下标的数字小的下一个数字的下标 28 s[++num]=i; 29 } 30 scanf("%d",&M); 31 while(M--) 32 { 33 int l,r; 34 scanf("%d%d",&l,&r); 35 int tmp=A[l]; 36 while(l<=r) 37 { 38 if(tmp==0) break; 39 if(pos[l]>r) break; 40 tmp=tmp%A[pos[l]]; 41 l=pos[l]; 42 } 43 printf("%d ",tmp); 44 } 45 } 46 return 0; 47 }
方法2：同样的思路，对于一个区间，若长度不为1，则在区间内从左到右不断查询比左端点小的数字，利用线段树，结点维护区间最小值，具体来说就是查询左子树，查询右子树，然后返回叶子结点的位置。
AC代码：
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 const int maxn=1e5+10; 5 int t,n,m; 6 int A[maxn],a[maxn<<2]; 7 void pushup(int rt){ 8 a[rt]=min(a[rt<<1],a[rt<<1|1]); 9 } 10 11 void build(int l,int r,int rt){ 12 if(l==r){ 13 a[rt]=A[l]; 14 return; 15 } 16 int m=l+r>>1; 17 build(l,m,rt<<1); 18 build(m+1,r,rt<<1|1); 19 pushup(rt); 20 } 21 22 int query(int L,int R,int ans,int l,int r,int rt){ 23 if(a[rt]>ans) return R+1; 24 int m=l+r>>1; 25 if(L<=l&&r<=R){ 26 if(l==r){ 27 return l; 28 } 29 if(a[rt<<1]<=ans) return query(L,R,ans,l,m,rt<<1); 30 if(a[rt<<1|1]<=ans) return query(L,R,ans,m+1,r,rt<<1|1); 31 } 32 else{ 33 int res; 34 if(L<=m){ 35 res=query(L,R,ans,l,m,rt<<1); 36 if(res<=R) return res; 37 } 38 39 if(R>m){ 40 res=query(L,R,ans,m+1,r,rt<<1|1); 41 if(res<=R) return res; 42 } 43 44 } 45 return R+1; 46 } 47 48 void check(){ 49 for(int i=1;i<=5;i++){ 50 cout<<a[i]<<" "; 51 }cout<<endl; 52 } 53 54 int main() 55 { 56 scanf("%d",&t); 57 while(t--){ 58 scanf("%d",&n); 59 for(int i=1;i<=n;i++){ 60 cin>>A[i]; 61 } 62 build(1,n,1); 63 //check(); 64 scanf("%d",&m); 65 int l,r; 66 while(m--){ 67 scanf("%d%d",&l,&r); 68 int ans=A[l]; 69 while(l<r){ 70 int cnt=query(l+1,r,ans,1,n,1); 71 //cout<<"此时"<<cnt<<endl; 72 if(cnt<=r) 73 ans=ans%A[cnt]; 74 l=cnt; 75 } 76 printf("%d ",ans); 77 } 78 } 79 return 0; 80 }