Light OJ-1082 Array Queries(线段树最值查询)

港控/mmm° 2022-06-11 06:41 132阅读 0赞

Given an array with **N** elements, indexed from **1** to **N**. Now you will be given some queries in the form **I J**, your task is to find the minimum value from index **I** to **J**.

**Input**

Input starts with an integer **T (≤ 5)**, denoting the number of test cases.

The first line of a case is a blank line. The next line contains two integers **N (1 ≤ N ≤ 105)**, **q (1 ≤ q ≤ 50000)**. The next line contains **N** space separated integers forming the array. There integers range in **\[0, 105\]**.

The next **q** lines will contain a query which is in the form **I J (1 ≤ I ≤ J ≤ N)**.

**Output**

For each test case, print the case number in a single line. Then for each query you have to print a line containing the minimum value between index **I** and **J**.

Sample Input

5 3

78 1 22 12 3

1 2

3 5

4 4

1 1

**Sample Output**

Case 1:

Case 2:

**Hint**

Dataset is huge. Use faster I/O methods.

题解：

很水的区间最小值查询。。就不写题解了

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    using namespace std;
    struct node
    {
        int l,r;
        int minn;
    }t[100005*4];
    void Build(int l,int r,int k)
    {
        t[k].l=l;
        t[k].r=r;
        if(l==r)
        {
            scanf("%d",&t[k].minn);
            return;
        }
        int mid=(l+r)/2;
        Build(l,mid,k*2);
        Build(mid+1,r,k*2+1);
        t[k].minn=min(t[k*2].minn,t[k*2+1].minn);
    }
    int query(int l,int r,int k)
    {
        if(t[k].l==l&&t[k].r==r)
        {
            return t[k].minn;
        }
        int mid=(t[k].l+t[k].r)/2;
        if(r<=mid)
            return query(l,r,k*2);
        else if(l>mid)
            return query(l,r,k*2+1);
        else
        {
            return min(query(l,mid,k*2),query(mid+1,r,k*2+1));
        }
    }
    int main()
    {
        int i,j,k,test,n,m,x,y,q;
        scanf("%d",&test);
        for(q=1;q<=test;q++)
        {
            scanf("%d%d",&n,&m);
            Build(1,n,1);
            printf("Case %d:\n",q);
            for(i=0;i<m;i++)
            {
                scanf("%d%d",&x,&y);
                printf("%d\n",query(x,y,1));
            }
        }
        return 0;
    }