HDU5875-Function（RMQ + 二分）

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=5875

思路

对于一个数a % b，只有当b ≤ a的时候，a才会变化 因此对于每个询问[L, R]，只需要找到第一个≤a[L]的即可，先用ST表预处理出区间[L, R]的最小值，然后二分查询区间内满足条件的值

代码

#include <iostream> #include <cstring> #include <stack> #include <vector> #include <set> #include <map> #include <cmath> #include <queue> #include <sstream> #include <iomanip> #include <fstream> #include <cstdio> #include <cstdlib> #include <climits> #include <deque> #include <bitset> #include <algorithm> using namespace std; #define PI acos(-1.0) #define LL long long #define PII pair<int, int> #define PLL pair<LL, LL> #define mp make_pair #define IN freopen("in.txt", "r", stdin) #define OUT freopen("out.txt", "wb", stdout) #define scan(x) scanf("%d", &x) #define scan2(x, y) scanf("%d%d", &x, &y) #define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z) #define sqr(x) (x) * (x) const int maxn = 100000 + 5; int d[maxn][32], p[maxn][32], a[maxn]; int n, l, r; void RMQ_init() { for (int i = 0; i < n; i++) { d[i][0] = a[i]; p[i][0] = i; } for (int j = 1; (1 << j) <= n; j++) { for (int i = 0; i + (1 << j) - 1 < n; i++) { d[i][j] = d[i][j - 1]; p[i][j] = p[i][j - 1]; if (d[i + (1 << (j - 1))][j - 1] < d[i][j]) { d[i][j] = d[i + (1 << (j - 1))][j - 1]; p[i][j] = p[i + (1 << (j - 1))][j - 1]; } } } } PII RMQ(int l, int r) { int k = 0; while ((1 << (k + 1)) <= r - l + 1) k++; int t = min(d[l][k], d[r - (1 << k) + 1][k]); if (d[l][k] < d[r - (1 << k) + 1][k]) return mp(p[l][k], t); return mp(p[r - (1 << k) + 1][k], t); } int judge(int x, int L, int R) { if (R <= L) return -1; PII t = RMQ(L, R); return t.second <= x ? t.first : -1; } int query(int l, int r) { int ans = a[l]; int L = l + 1; while (L < r) { int R = r, M = (L + R) >> 1; while (L < R) { if (R == L + 1) { if (a[L] <= ans) M = L; else M = R; break; } else { M = (L + R) >> 1; if (judge(ans, L, M) != -1) R = M; else L = M; } } ans %= a[M]; L = M + 1; if (judge(ans, L, r) == -1) break; } if (l < r) ans %= a[r]; return ans; } int main() { int T, Q; scan(T); while (T--) { scan(n); for (int i = 0; i < n; i++) scan(a[i]); RMQ_init(); scan(Q); while (Q--) { scan2(l, r); l--; r--; printf("%d\n", query(l, r)); } } return 0; }