HDOJ5875(线段树) 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

Input

There are multiple test cases.

The first line of input contains a integer

, representing a query.

Output

For each query

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 = 100005;
struct Node{
    int l, r, mn;
}a[MAXN*3];
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) >> 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 &x)
{
    if(x == 0)  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) >> 1;
    if(r <= mid)
    {
        query(rt << 1, l, r, x);
    }
    else if(mid < l)
    {
        query((rt << 1) | 1, l, r, x);
    }
    else
    {
        query(rt << 1, l, mid, x);
        query((rt << 1) | 1, mid + 1, r, x);
    }
}
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
", val[l]);
            }
            else
            {
                int x = val[l];
                query(1, l + 1, r, x);
                printf("%d
", x);
            }
        }
    }
    return 0;
}

相关推荐