题目大意:
定义F(l,r) :如果l==r F(l,r)=a[l] 否则 F[l,r]=al %al+1%al+2%...%ar
数据范围为N<=1e5,M<=1e5
解法:
注意到a%b，如果a<b 那么模不模b没有影响。而且一个数要进行取模的操作次数是不会很多的。所以问题再与怎么快速找到要模上哪些数。
我们要快速找到小于等于当前值的小下标，对它取模后，不断的重复这个操作。
我们先用RMQ预处理出ST表,query函数返回的是[l,r]区间内的最小值的下标。
代码:
1 #include<cstdio> 2 #include<cstring> 3 #define min(a,b) (a<b?a:b) 4 #define max(a,b) (a>b?a:b) 5 using namespace std; 6 const int MAXN=1e5+7; 7 int a[MAXN],dp[MAXN][25]; 8 int N,M; 9 void init_rmq()//dp[i][j]:在[i,i+(1<<j)]区间内a[k]最小值得下标 10 { 11 for(int i=1;i<=N;++i)dp[i][0]=i; 12 for(int j=1;(1<<j)<=N;++j) 13 { 14 for(int i=1;i+(1<<j)-1<=N;++i) 15 { 16 int x=dp[i][j-1]; 17 int y=dp[i+(1<<(j-1))][j-1]; 18 dp[i][j]= a[x]<a[y]?x:y; 19 } 20 } 21 } 22 int query(int l,int r)//返回[l,r]区间最小值对应得下标 23 { 24 int len=r-l+1; 25 int k=0; 26 while((1<<k)<=len)++k;--k; 27 int x=dp[l][k],y=dp[r-(1<<k)+1][k]; 28 return a[x]<a[y]?x:y; 29 } 30 int main() { 31 int T;scanf("%d",&T); 32 while(T--) 33 { 34 memset(a,0,sizeof(a)); 35 memset(dp,0,sizeof(dp)); 36 scanf("%d",&N); 37 for(int i=1;i<=N;++i)scanf("%d",&a[i]); 38 scanf("%d",&M); 39 init_rmq(); 40 while(M--) 41 { 42 int l,r;scanf("%d%d",&l,&r); 43 if(l==r) 44 { 45 printf("%d ",a[l]); 46 continue; 47 } 48 int val=a[l]; 49 int begin=l+1-1,right=r; 50 for(;begin<right;) 51 { 52 int lo=begin,hi=right; 53 while(hi-lo>1) 54 { 55 int m=(hi+lo)/2; 56 int x=query(begin,m);//[lo,m]; 57 if(a[x]<=val)hi=m; 58 else lo=m; 59 } 60 val%=a[hi]; 61 begin=hi; 62 } 63 printf("%d ",val); 64 } 65 } 66 return 0; 67 }