题意，给一堆数，给你一个区间，求这个区间第一个数 模 第二个数 模 第三个数 ....模到这个区间最后一个数，最后值是多少，有多次询问。然后很明显的，一个数摸一个比他小的数就变小了，比他大的数，他不变，所以总是要找小的数，如果能知道一个数在他后面第一个比他小的数u，然后取模，再去找u后面比他小的第一个数，再取模，这样子能跳过很多不用的区间。那么问题来了，如何快速知道一个数之后第一个比他小的数呢？？单调栈，ok，解决了。
#include #include #include #include #include #include using namespace std; int n, m; int next[100005]; struct node { int pos; int val; }a[100005], tmp; stack s; int main(void) { int T; scanf("%d", &T); for (int i = 1; i < 100005; i++) a[i].pos = i; tmp.pos = 0; tmp.val = 0; while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i].val); scanf("%d", &m); memset(::next, 0x3f3f3f3f, sizeof ::next); while (!s.empty()) s.pop(); s.push(tmp); for (int i = 1; i <= n; i++) { while (s.top().val > a[i].val) { ::next[s.top().pos] = i; s.pop(); } s.push(a[i]); } int l, r; for (int i = 0; i < m; i++) { scanf("%d%d", &l, &r); int ans = a[l].val; for (int j = ::next[l]; j <= r; j = ::next[j]) { if (ans == 1 || ans == 0) break; ans %= a[j].val; } printf("%d ", ans); } } return 0; }