思路：我一开始看到3500ms的时候，就暴力莽。。。。。因为最多可以用两for嘛。。。然后T了之后。。。原来可以先标记最右端比a[l]小的数。。。。。。。。。。因为mod运算你最多能mod的数不会很多。。。
//#include<bits/stdc++.h> #include <stdio.h> #include <iostream> #include<algorithm> //#include <map> //#include <set> //#include <vector> //#include <queue> //#include <stack> #include <stdlib.h> #include <cstring> #include <string.h> #include <string> #include <math.h> using namespace std; typedef long long ll; #define MAXN 100005 #define INF 0x3f3f3f3f//将近ll类型最大数的一半，而且乘2不会爆ll int a[MAXN]; int Next[MAXN]; int main() { int t; cin >> t; while(t--) { memset(a, 0, sizeof(a)); memset(Next, 0, sizeof(Next)); int n, m; scanf("%d", &n); for(int i=1; i<=n; ++i) scanf("%d", &a[i]); for(int i=1; i<=n; ++i) { Next[i] = -1; for(int j=i+1; j<=n; ++j) if(a[i] >= a[j]) { Next[i] = j; break; } } scanf("%d", &m); for(int i=0; i<m; ++i) { int l, r; scanf("%d %d", &l, &r); int ans = a[l]; for(int j=Next[l]; j<=r; j = Next[j]) { if(j == -1) break; ans%=a[j]; } cout << ans << '\n'; } } return 0; }