首页 > 代码库 > HDU 5875 st+二分区间
HDU 5875 st+二分区间
题目大意:给你n个数,q次询问,每次询问区间[l, r],问a[i]%a[i + 1] % a[i + 2]...%a[j](j <= r)的值
思路:st预处理维护,在二分区间,复杂度n*(logn)*logn
//看看会不会爆int!数组会不会少了一维!//取物问题一定要小心先手胜利的条件#include <bits/stdc++.h>using namespace std;#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se secondconst int maxn = 1e5 + 5;int a[maxn];int st[maxn][25];int n;void init(){ for (int i = 0; i < n; i++) st[i][0] = a[i]; for (int j = 1; (1 << j) <= n; j++){ for (int i = 0; i + (1 << j) - 1 < n; i++){ st[i][j] = min(st[i + (1 << (j-1))][j - 1], st[i][j - 1]); } }}inline int query(int l, int r){ int len = r - l + 1; int k = 0; while ((1 << (k + 1)) <= len) k++; return min(st[l][k], st[r - (1 << k) + 1][k]);}inline int solve(){ int l, r; scanf("%d%d", &l, &r); l--, r--; if (l == r) return a[l]; int val = a[l]; ///二分区间 l++; while (l <= r){ int lb = l, rb = r; while (lb < rb){ int mid = (lb + rb) / 2; if (query(lb, mid) <= val) rb = mid; else if (query(mid + 1, rb) <= val) lb = mid + 1; else return val; } l = lb + 1; val %= a[lb]; } return val;}int main(){ int t; scanf("%d", &t); while (t--){ scanf("%d", &n); for (int i = 0; i < n; i++){ scanf("%d", a + i); } init(); int q; scanf("%d", &q); while (q--){ printf ("%d\n", solve()); } } return 0;}
HDU 5875 st+二分区间
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。