首页 > 代码库 > HDOJ5875(线段树)

HDOJ5875(线段树)

2024-08-13 10:50:04   213人阅读

Function

Time Limit: 7000/3500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1701    Accepted Submission(s): 615


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
1
3
2 3 3
1
1 3
 

 

Sample Output
2
思路：用val[l],每次%上在[l+1,r]中下一个最小的值。
#include <cstdio>#include <algorithm>using namespace std;const int MAXN=100005;struct Node{    int mn,l,r;}a[MAXN*3];int n,m;int val[MAXN];void build(int rt,int l,int r){    a[rt].l=l;    a[rt].r=r;    if(l==r)    {        scanf("%d",&a[rt].mn);        val[l]=a[rt].mn;        return ;    }    int mid=(l+r)>>1;    build(rt<<1,l,mid);    build((rt<<1)|1,mid+1,r);    a[rt].mn=min(a[rt<<1].mn,a[(rt<<1)|1].mn);}void query(int rt,int l,int r,int &val){    if(val==0)    return ;    if(a[rt].mn>val)    return ;    if(a[rt].l==a[rt].r)    {        val%=a[rt].mn;        return ;    }    int mid=(a[rt].l+a[rt].r)>>1;    if(r<=mid)    {        query(rt<<1,l,r,val);    }    else if(mid<l)    {        query((rt<<1)|1,l,r,val);    }    else    {        query(rt<<1,l,mid,val);        query((rt<<1)|1,mid+1,r,val);    }} int main(){    int T;    scanf("%d",&T);    while(T--)    {        scanf("%d",&n);            build(1,1,n);        scanf("%d",&m);        while(m--)        {            int l,r;            scanf("%d%d",&l,&r);            if(l==r)            {                printf("%d\n",val[l]);            }            else            {                int res=val[l];                query(1,l+1,r,res);                printf("%d\n",res);            }            }    }    return 0;}

 

 

HDOJ5875(线段树)


联系
我们