首页 > 代码库 > HDU 5875 Function st + 二分

HDU 5875 Function st + 二分

2024-08-13 03:35:59   213人阅读

Function

 

Problem Description
 
The shorter, the simpler. With this problem, you should be convinced of this truth.
  
  You are given an array A of N postive integers, and M queries in the form (l,r). A function F(l,r) (1≤l≤r≤N) is defined as:
F(l,r)={AlF(l,r−1) modArl=r;l<r.
You job is to calculate F(l,r), for each query (l,r).
 

 

Input
 
There are multiple test cases.
  
  The first line of input contains a integer T, indicating number of test cases, and T test cases follow. 
  
  For each test case, the first line contains an integer N(1≤N≤100000).
  The second line contains N space-separated positive integers: A1,…,AN (0≤Ai≤109).
  The third line contains an integer M denoting the number of queries. 
  The following M lines each contain two integers l,r (1≤l≤r≤N), representing a query.
 

 

Output
 
For each query(l,r), output F(l,r) on one line.
 

 

Sample Input
 
132 3 311 3
 

Sample Output

 

2
 

题意：

　　给你一个n,n个数

　　m个询问，每次询问你 l,r，， a[l] % a[l+1] % a[l+2] %……a[r] 结果是多少

题解；

　　每次有效的取模会使结果减半，因此只有log次有效取模，每次往右找一个不大于结果的最靠左的数，ST表+二分

　　注意RMQ查询的时候少用 log函数，这是造成我开始超时的原因

#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#include<cmath>#include<vector>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define ls i<<1#define rs ls | 1#define mid ((ll+rr)>>1)#define pii pair<int,int>#define MP make_pairtypedef long long LL;const long long INF = 1e18;const double Pi = acos(-1.0);const int N = 1e5+10, M = 1e2+11, mod = 1e9+7, inf = 2e9;int dp[N][50],a[N],n,q;void st() {        for(int j = 1; (1<<j) <= n; ++j) {            for(int i = 1; (i + (1<<j) - 1) <= n; ++i) {                dp[i][j] = min(dp[i][j-1],dp[i + (1<<(j-1))][j-1]);            }        }}int query(int l,int r) {        int len = r - l + 1;        int k = 0;        while ((1 << (k + 1)) <= len) k++;        return min(dp[l][k],dp[r - (1<<k) + 1][k]);}int _binary_search(int l,int r,int res) {        int s = r+1;        while(l <= r) {            int md = (l + r) >> 1;            if(query(l,md) <= res) r = md - 1,s = md;            else l = md + 1;        }        return s;}int main() {        int T;        scanf("%d",&T);        while(T--) {            scanf("%d",&n);            for(int i = 1; i <= n; ++i) scanf("%d",&a[i]),dp[i][0]=a[i];            st();            scanf("%d",&q);            for(int i = 1; i <= q; ++i) {                int x,y,L,R;                scanf("%d%d",&x,&y);                int res = a[x];                L = x+1, R = y;                while(L <= R && res) {                   L = _binary_search(L,R,res);                   if(L<=R) {                        res%=a[L];L++;                   }                }                printf("%d\n",res);            }        }        return 0;}

 

HDU 5875 Function st + 二分


联系
我们