St table learning

ST The application of tables is to solve RMQ problem , Pretreatment construction ST The time complexity of the table is O（nlog n), In general, the solution of seeking interval extremum can also be maintained gcd The problem of , Advanced application is to find the maximum number of times a number appears in an interval , Count times .

The basic principles can be found in this article ++++++++++++++++++++++++++++++++++

ST Table preprocessing

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e4+10;
int f[N][20],a[N],lg[N];
int n;
void init ()
{
    
    for (int i=1;i<n;i++)
    {
    
        f[i][0] = a[i];
        if (i!=1) lg[i] = lg[i>>1]+1;
    }
    
    for (int j=1;j<=lg[n];j++)
    {
    
        for (int i=1;i<=n-(1<<j)+1;i++)
        {
    
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
        }
    }
}

Query operation

int query(int x, int y)
{
    
    int t = lg(y-x);
    int a = f[x][t];
    int b = f[y - (1 << t) + 1][t];
    return max(a,b);
}

Find the maximum number of times a number appears in the interval , Count times .

Example explanation -----------------------------------

Later done cf , Found a st Table questions , yes Codeforces #736 div2 Of D topic
Title link here +++++++++++++

Topic description

blank

B There is a senior video explanation at the station
Video link +++++++++++++++++++++++++++++++++++++++++++++