hdu 5875 Function 单调栈 + 暴力

本文主要是介绍hdu 5875 Function 单调栈 + 暴力，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

//  hdu 5875 Function 单调栈 + 暴力
//
//  题目链接：
//
//      http://acm.split.hdu.edu.cn/showproblem.php?pid=5875
//
//  题目大意：
//
//      一数组，给定区间[l,r],求a[l] % a[l + 1] % ... % a[r]
//
//  解题思路：
//
//      对于%，只有比本身小到数才会影响最后结果，所以我们维护
//  一个单调递增序列，和next数组，表示比当前数小到下一个数的
//  位置，采用单调栈即可
//
//  感悟：
//
//      有点尴尬，题目意思很明显，确实没想到这样到解题思路。
//  但看到各位大神的解题思路，就觉得十分明显，道理也都通晓。
//  继续努力 ^_^#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;const int MAXN = 1e5 + 8;int a[MAXN];
int ne[MAXN];
stack<int> st;
int n,m;void init(){memset(ne,-1,sizeof(ne));while(!st.empty())st.pop();
}void input(){scanf("%d",&n);for (int i  = 1;i <= n;i ++){scanf("%d",a + i);}for (int i = 1;i <= n;i ++){while(!st.empty() && a[i] < a[st.top()]){ne[st.top()] = i;st.pop();}st.push(i);}scanf("%d",&m);int l,r;for (int i = 1;i <= m;i ++){scanf("%d%d",&l,&r);int ans = a[l];int ind = l;while(ne[ind] <= r && ne[ind] != -1){ans %= a[ne[ind]];ind = ne[ind];}printf("%d\n",ans);}}int main(){int t;while(scanf("%d",&t)!=EOF){while(t--){init();input();}}return 0;
}

这篇关于hdu 5875 Function 单调栈 + 暴力的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---