http://acm.hdu.edu.cn/showproblem.php?pid=5875
单调栈，预处理to[i]表示第一个比a[i]小的数字，一直跳就可以。
这题是数据水而已。
这里学习下单调栈。
构造一个单调递增的栈，并且记录元素大小的同时记录它的id。
每次进来一个小的元素的话，就出栈，同时出栈的这个元素的to[id] = i了，因为这个元素是当时最大的。然后这个a[i]是第一个能让它出栈的，所以就是它了。后面的同理。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 1e5 + 20; int a[maxn]; int to[maxn]; struct node { int id; int val; }stack[maxn]; void work() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } int top = 1; a[n + 1] = -1; stack[top].val = a[1]; stack[top].id = 1; for (int i = 2; i <= n + 1; ++i) { while (top >= 1 && a[i] <= stack[top].val) { to[stack[top].id] = i; top--; } ++top; stack[top].val = a[i]; stack[top].id = i; } // for (int i = 1; i <= n; ++i) { // printf("%d ", to[i]); // } // printf(" "); int m; scanf("%d", &m); for (int i = 1; i <= m; ++i) { int L, R; scanf("%d%d", &L, &R); int ans = a[L]; int t = to[L]; while (t <= R) { ans %= a[t]; if (ans == 0) break; t = to[t]; } printf("%d ", ans); } } int main() { #ifdef local freopen("data.txt","r",stdin); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }