HDU5875 - Function

---

做法：st表+二分的經(jīng)典題。不能使用數(shù)學(xué)函數(shù)log，否則會(huì)tle，需要預(yù)處理

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define per(i,a,b) for(int i=a;i>=b;--i) #define mem(a,b) memset(a,b,sizeof(a)) #define pb push_back #define MP make_pair #define pii pair<int,int> #define pll pair<ll,ll> #define fr first #define sc second typedef long long ll; const int N= 2e5 + 7; using namespace std; int n,m; ll a[N], st[N][50],Log[N];void init() {Log[1] = 0;for(int i = 2; i <= n; ++i) Log[i] = Log[i>>1] + 1;for(int i = 0; i <= n; ++i) st[i][0] = a[i];for(int j = 1; (1<<j) <= n; ++j){for(int i = 1; i+(1<<j)-1 <= n; ++i) {st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);}} } inline ll ask(int u,int v) {int k = Log[v-u+1];return min(st[u][k], st[v-(1<<k)+1][k]); }int fd(int l,int r,ll x) {int s = r + 1;while(l <= r) {int mid = (l+r)>>1;if(ask(l,mid) <= x) r = mid - 1, s = mid;else l = mid + 1;}return s; } ll solve(int l,int r) {ll now = st[l][0];if(l == r) return now;l++;while(l<=r && now){l = fd(l,r,now);if(l <= r) {now %= st[l][0]; ++l;}}return now; } int main() {int T;scanf("%d",&T);while(T--) {scanf("%d",&n);rep(i,1,n) scanf("%lld",&a[i]);init();scanf("%d",&m);rep(i,1,m) {int l,r;scanf("%d%d",&l,&r);printf("%lld\n",solve(l,r));}}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/9703014.html

總結(jié)

以上是生活随笔為你收集整理的HDU5875 - Function的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。