subject

Enter a string of numbers and give you M inquiries. Each inquiry will give you two numbers x and Y, asking you to say the maximum number in the range from X to Y.

Input format
In the first line, there are two integers n, and M represents the number of numbers and the number of times to ask;

The number of next row N;

Next M lines, each line has two integers X,Y.

Output format
Output a total of M lines, each line outputs a number.

Data range
1 ≤ N ≤ 1 0 5 1≤N≤10^5 1≤N≤105,
1 ≤ M ≤ 1 0 6 1≤M≤10^6 1≤M≤106,
1 ≤ X ≤ Y ≤ N 1≤X≤Y≤N 1≤X≤Y≤N,
No number in the series exceeds 2 31 − 1 2^{31}−1 231−1

Solution#1 RMQ

RMQ (Range Minimum/Maximum Query), i.e. interval maximum query, refers to such A question: for sequence A with length n, answer RMQ(i,j) several times and return the minimum / maximum value of subscript in interval [i,j] in sequence A.

This paper introduces an efficient ST algorithm to solve this problem. ST (Sparse Table) algorithm can Preprocess in O(nlogn) time, and then answer each query in O(1) time.

1) Pretreatment

Let A[i] be the sequence of numbers requiring the maximum value of the interval, and F[i, j] represent the maximum value of 2^j consecutive numbers from the ith number. (status of DP)

For example:

A sequence: 3 2 4 5 6 8 1 2 9 7

F[1, 0] represents the maximum value of length 2 ^ 0 = 1 from the first number, which is actually the number 3. Similarly, F[1,1] = max(3,2) = 3, F[1,2]=max(3,2,4,5) = 5, F[1,3] = max(3,2,4,5,6,8,1,2) = 8;

And we can easily see that F[i,0] is equal to A[i]. (initial value of DP)

We divide F[i, j] into two segments on average (because F[i, j] must be an even number). From I to i + 2 ^ (j - 1) - 1 is a segment, and from i + 2 ^ (j - 1) to i + 2 ^ j - 1 is a segment (the length is 2 ^ (j - 1)). So we get the state transition equation F[i, j]=max (F[i, j-1], F[i + 2^(j-1), j-1]).

2) Inquiry

If the interval we need to query is (i,j), then we need to find the minimum power covering this closed interval (the left boundary takes i and the right boundary takes j) (which can be repeated. For example, if we query 1, 2, 3, 4, 5, we can query 1234 and 2345).

Because the length of this interval is j - i + 1, we can take k = log2 (j - i + 1), then RMQ (I, J) = max {f [I, k], f [J - 2 ^ k + 1, k]}.

For example, the maximum value of interval [1,5] is required, k = log2 (5 - 1 + 1) = 2, that is, find max (f [1,2], f [5 - 2 ^ 2 + 1,2]) = max (f [1,2], f [2,2]);

Original link

#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1e5+5;

int n,m;
int a[N],f[N][20];

int rmq(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=(r-l+1))
        k++;
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{
    scanf("%d%d", &n, &m);
    int x,y;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        f[i][0] = a[i];
    }
    
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i+(1<<j)-1<=n; i++)
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",rmq(x,y));
    }
    
    return 0;
}

Solution#2 segment tree

Modification of general segment tree:

• Originally, the parent node is the sum of the left and right subtrees. Here, it is modified to the maximum value of the left and right subtrees
• In the process of query, considering the negative number, modify the place that originally returned 0 to return the minimum value
• The time requirement is strict, and the card constant shall be used (scanf and printf)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <climits>
using namespace std;
const int N = 1e5+5;

int a[N],t[4*N];

void bulid(int node,int start,int end)
{
    if(start==end)
        t[node]=a[start];
    else
    {
        int mid=start+end>>1;
        bulid(node<<1,start,mid);
        bulid(node<<1|1,mid+1,end);
        t[node]=max(t[node<<1],t[node<<1|1]);
    }
}

int query(int node,int start,int end,int l,int r)
{
    int min_inf=INT_MIN;
    if(end<l || start>r)
        return min_inf;
    else if(start==end)
        return t[node];
    else if(l<=start && end<=r)
        return t[node];
    else
    {
        int mid = start+end>>1;
        int left_max = max(min_inf,query(node<<1,start,mid,l,r));
        int right_max = max(min_inf,query(node<<1|1,mid+1,end,l,r));
        return max(left_max,right_max);
    }
}
int main()
{
    int n,m,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)  scanf("%d",&a[i]);
    bulid(1,1,n);
    while (m -- )
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",query(1,1,n,x,y));
    }
    return 0;
}

Solution#3 tree array

Leave a hole for the time being, because you don't know much about the principle of tree array. Come back and supplement after in-depth study. Run the code step by step and find that tree array is a very magical structure, which enlivens the binary system. Paste the code for interested people to learn.

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int nums[N], bit[N], n, m;

inline int lowbit(int x) {
    return x & -x;
}

void build() { // Initialize tree array
    for (int i = 1; i <= n; ++ i) {
        bit[i] = nums[i];
        for (int j = 1; j < lowbit(i); j <<= 1)
            bit[i] = max(bit[i], bit[i - j]);
    }
}

int query(int l, int r) { // Interval query
    int maxv = INT_MIN;
    while (l <= r) {
        maxv = max(maxv, nums[r]);
        -- r;
        for (; l <= r - lowbit(r); r -= lowbit(r))
            maxv = max(maxv, bit[r]);
    }
    return maxv;
}

int main()
{
    int l, r;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d", &nums[i]);
    build();
    while (m --) {
        scanf("%d %d", &l, &r);
        printf("%d\n", query(l, r));
    }
    return 0;
}
/*from:https://www.acwing.com/solution/content/83790/*/