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

2 3 3

1 3

Sample Output

思路：用val[l],每次%上在[l+1,r]中下一个最小的值。

#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN = ;

struct Node{

    int l, r, mn;

}a[MAXN*];

int n, m, val[MAXN];

void build(int rt, int l, int r)

{

    a[rt].l = l;

    a[rt].r = r;

    if(l == r)

    {

        scanf("%d", &val[l]);

        a[rt].mn = val[l];

        return ;

    }

    int mid = (l + r) >> ;

    build(rt << , l, mid);

    build((rt << ) | , mid + , r);

    a[rt].mn = min(a[rt<<].mn, a[(rt<<)|].mn);

}

void query(int rt, int l, int r, int &x)

{

    if(x == )  return ;

    if(a[rt].mn > x)    return ;

    if(a[rt].l == a[rt].r)

    {

        x %= a[rt].mn;

        return ;

    }

    int mid = (a[rt].l + a[rt].r) >> ;

    if(r <= mid)

    {

        query(rt << , l, r, x);

    }

    else if(mid < l)

    {

        query((rt << ) | , l, r, x);

    }

    else

    {

        query(rt << , l, mid, x);

        query((rt << ) | , mid + , r, x);

    }

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d", &n);

        build(, , n);

        scanf("%d", &m);

        while(m--)

        {

            int l, r;

            scanf("%d %d", &l, &r);

            if(l == r)

            {

                printf("%d\n", val[l]);

            }

            else

            {

                int x = val[l];

                query(, l + , r, x);

                printf("%d\n", x);

            }

        }

    }

    return ;

}

巴特西

HDOJ5875(线段树)

Function

最新文章

热门文章