首页 > 代码库 > HDU 5875 H - Function 用单调栈水过了
HDU 5875 H - Function 用单调栈水过了
单调栈,预处理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("\n"); 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\n", ans); } } int main() { #ifdef local freopen("data.txt","r",stdin); #endif int t; scanf("%d", &t); while (t--) work(); return 0; }
HDU 5875 H - Function 用单调栈水过了
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。