RMQ问题

ST表是用来解决RMQ（区间最值）问题的算法

预处理O(nlgn) 查询O(1) 不支持在线查询

最小值可以合并但不支持分割

比如说我们知道[1,9]和[6,10]的最小值，我们可以知道[1,10]的最小值，但不能知道[6,9]的最小值

我们可以枚举以每个节点为起点经过k个节点的最值

但是预处理是O(n²)，这时候我们想到了倍增，一种十分巧妙的思想

它可以在变化规则相同的情况下加速状态转移，我们每次把k扩大一倍

f[i,j]表示[i,i+2^j-1]区间内的信息

f[i,j]:=f[i,j-1]∪f[i+2^j-1]

代码实现

//初始化
bin[0]=1;
for(int i=1;i<20;i++)
    bin[i]=bin[i-1]*2;//bin[i]表示2的i次方
Log[0]=-1;
for(int i=1;i<=200000;i++)
    Log[i]=Log[i/2]+1;//Log[i]表示log(i)
for(int i=1;i<=n;i++)
    mn[0][i]=a[i];//显然i到i+2^0-1就i一个位置，那么最小值等于自己本身的值
for(int i=1;i<=Log[n];i++)
    for(int j=1;j<=n;j++)
        if(j+bin[i]-1<=n)
            mn[i][j]=min(mn[i-1][j],mn[i-1][j+bin[i-1]]);//状态继承
//查询x到y的最小值
int t=Log[y-x+1];
printf("%d
",min(mn[t][x],mn[t][y-bin[t]+1]));

[例题1]Balanced Lineup

题目描述

每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John
决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛.
但是为了避免水平悬殊,牛的身高不应该相差太大.
John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <=
身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别.
注意: 在最大数据上, 输入和输出将占用大部分运行时间.

输入

6 3

1 5

4 6

2 2

输出

[参考程序]

#include<iostream> 
#include<cstring> 
#include<cstdio> 
#include<climits> 
#include<cmath> 
#include<algorithm> 
using namespace std; 
   
const int N = 50005; 
int FMAX[N][20], FMIN[N][20]; 
   
void RMQ(int n) 
{ 
    for(int j = 1; j != 20; ++j) 
    { 
        for(int i = 1; i <= n; ++i) 
        { 
            if(i + (1 << j) - 1 <= n) 
            { 
                FMAX[i][j] = max(FMAX[i][j - 1], FMAX[i + (1 << (j - 1))][j - 1]); 
                FMIN[i][j] = min(FMIN[i][j - 1], FMIN[i + (1 << (j - 1))][j - 1]); 
            } 
        } 
    } 
} 
   
int main() 
{ 
    int num, query; 
    int a, b; 
    while(scanf("%d %d", &num, &query) != EOF) 
    { 
        for(int i = 1; i <= num; ++i) 
        { 
            scanf("%d", &FMAX[i][0]); 
            FMIN[i][0] = FMAX[i][0]; 
        } 
        RMQ(num); 
        while(query--) 
        { 
            scanf("%d%d", &a, &b); 
            int k = (int)(log(b - a + 1.0) / log(2.0)); 
            int maxsum = max(FMAX[a][k], FMAX[b - (1 << k) + 1][k]); 
            int minsum = min(FMIN[a][k], FMIN[b - (1 << k) + 1][k]); 
            printf("%d
", maxsum - minsum); 
        } 
    } 
    return 0; 
}

[例题2] 与众不同

【题目描述】
A是某公司的CEO，每个月都会有员工把公司的盈利数据送给A，A是个与众不同的怪人，A不注重盈利还是亏本，而是喜欢研究“完美序列”：连续的互不相同的序列。A想知道区间[L,R]之间最长的完美序列。
【输入格式】
第一行两个整数N，M(1<=N,M<=200000)，N表示连续N个月,编号为0到N-1，M表示询问的次数。第二行N个整数(绝对值不超过106),第i个数表示该公司第i个月的盈利值。接下来M行每行两个整数L,R(0<=L<=R<=N-1),表示A询问的区间。
【输出格式】
输出M行，每行一个整数对应询问区间内的完美序列的最长长度。
【样例输入】
9 2
2 5 4 1 2 3 6 2 4
0 8
2 6
4 8
【样例输出】
6
5
4

[分析]

本题是RMQ较复杂的问题。用last[value]表示盈利值value最近出现的位置，一开始全部赋为0。

用st[i]表示以第i个数为结尾的最长完美序列的起始位置，st[i]=max(st[i-1],last[a[i]]+1)(a[i]表示第i个月的盈利值)，用f[i]表示第i个数为结尾的最长完美序列的长度，显然f[i]=i-st[i]+1

for i:=1 to n do begin
  read(a[i]);
  st[i]:=max(st[i-1],last[a[i]]+1);
  q[i]:=i-st[i]+1;
  last[a[i]]:=i;
end;

可以发现st数组单调不减。
于是对于一个分割点mm有两种情况：
1、mm左边一部分st[]值<=l-1
2、mm右边一部分st[]值>=l
因为st[]是单调的，所以可以用二分法。
左半部分最大值即mm-l，右半部分最大值即q[mm..r]的最大值

uses math;
var
  a,st,q:array[0..200001]of longint;
    last:array[-1000001..1000001]of longint;
    rmq:array[0..200001,0..21]of longint;
    i,j,ans,n,m,l,r,mm,len:longint;
function search(x,y:longint):longint;
var
  ll,rr,mid:longint;
begin
  if st[x]=x then exit(x);
    if st[y]<x then exit(y+1);
    ll:=x;rr:=y;
    while ll<=rr do begin
      mid:=(ll+rr) div 2;
        if st[mid]<x then ll:=mid+1 else rr:=mid-1;
    end;
    exit(ll);
end;
begin
  readln(n,m);
    for i:=1 to n do begin
        read(a[i]);
      st[i]:=max(st[i-1],last[a[i]]+1);
        q[i]:=i-st[i]+1;
      last[a[i]]:=i;
  end;
    for i:=1 to n do rmq[i,0]:=q[i];
    for j:=1 to trunc(ln(n)/ln(2)) do
      for i:=1 to n-(1 shl j)+1 do
            rmq[i,j]:=max(rmq[i,j-1],rmq[i+(1 shl (j-1)),j-1]);
    for i:=1 to m do begin
      readln(l,r);
        mm:=search(l,r);
        if mm>l then ans:=mm-l;
        if mm<=r then begin
          len:=trunc(ln(r-mm+1)/ln(2));
          ans:=max(ans,max(rmq[mm,len],rmq[r-(1 shl len)+1,len]));
        end;
        writeln(ans);
    end;
end.