首页 > 代码库 > Function---hdu5875（大连网选，区间连续求余）
Function---hdu5875（大连网选，区间连续求余）
题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5875
题意：有n个数，m个查询，每个查询有一个区间[L, R], 求ans, ans = a[L]%a[L+1]%a[L+2]%...%a[R];
方法一：算是暴力吧，只能说数据太水；
用pos[i] = j 表示第 i 个元素后面的一个<= a[i]的下标是 j ；
然后直接跳到当前位置即可，（我感觉如果数中有10e5个严格递减或者严格递增的序列是会TLE吧）但是这个还是过了，我想应该是数据太弱了吧
#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<vector>#include<queue>using namespace std;#define met(a, b) memset(a, b, sizeof(a))#define N 100005#define INF 0x3f3f3f3ftypedef long long LL;#define Lson r<<1#define Rson r<<1|1int n, a[N], pos[N], m;int main(){ int T; scanf("%d", &T); while(T--) { scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &a[i]); a[0] = INF; for(int i=1; i<=n; i++) { for(int j=i+1; j<=n; j++) { if(a[j] <= a[i]) { pos[i] = j; break; } } } scanf("%d", &m); for(int i=1; i<=m; i++) { int L, R; scanf("%d %d", &L, &R); int ans = a[L]; while(ans && pos[L]<=R && L) { ans = ans%a[pos[L]]; L = pos[L]; } printf("%d\n", ans); } } return 0;}
方法二：在每个查询的时候，用线段树优化，当在区间[L, R]中找到第一个<=num的位置即可；
Function---hdu5875（大连网选，区间连续求余）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。