首页 > 代码库 > 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;}
View Code

 

HDU 5875 st+二分区间