P1198 [JSOI2008] 最大数

luogu-p1198-最大数">Luogu-P1198 最大数

1. 题面梗概

• 中译中: 维护一个初始为空的序列，支持两种操作：

  1. 入队：在序列末尾追加一个数 $n$（实际上是 $(n+t) \pmod D$）。

  2. 查询：查询序列中最后 $L$ 个数里的最大值。

• 强制在线: 每次追加的数依赖于上一次查询的结果 $t$。

2. 逻辑推导

末尾追加 和 查询最后 $L$ 个数，第一反应这题可能是个 单调队列 或者 单调栈。

但问题是 $L$ 是变化的，单调栈无法回答任意长度后缀的最值。

回归本质分析，这其实是个序列问题，末尾追加 类比于 单点修改，以及区间查询。

对于这题来说，可以用普通线段树来维护，第 $i$ 个叶子节点，就是第 $i$ 次插入的那个数。这样就是简单的线段树裸题了。

2.1 动态 ST 表

但这题可以采用另类的ST表解决。传统的 ST 表面对动态数据会很乏力，是因为它的区间是从左向右定义的。（st[i][j] 覆盖 [i, i+2^j-1]）

逆向思维：既然只在末尾追加元素，且查询总是关于最后 $L$ 个元素，不妨反转 ST 表定义：st[i][j] 表示以 $i$ 结尾，长度为 $2^j$ 的区间最大值。（覆盖 [i-2^j+1, i]）

状态转移：st[i][j] = max( st[i][j-1], st[i - (1 << (j - 1) )][j-1];

这一步很奇妙，巧在前面的元素是固定的，每次追加只需要更新最后面的元素，已经它们对应的 ST 表即可。

2. 代码实现

▶

AcCode

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 2e5 + 50;
const int maxlg = 20;

int st[maxn][maxlg];
int lg2[maxn];
int cnt = 0;
int m, d;
ll t;

void lgInit( int n )
{
    lg2[1] = 0;
    for( int i = 2; i <= n; ++ i )
        lg2[i] = lg2[i >> 1] + 1;
}

void add( int val )
{
    cnt ++;
    st[cnt][0] = val;
    for( int j = 1; j < maxlg; ++ j )
    {
        if( (1 << j) > cnt ) break;
        st[cnt][j] = max( st[cnt][j-1], st[cnt - (1 << (j - 1))][j-1] );
    }
}

int query( int l, int r )
{
    if( r == 0 ) return 0;
    int k = lg2[ r - l + 1 ];
    return max( st[r][k], st[l + (1 << k) - 1][k] );
}

int main( )
{	
    lgInit( maxn - 1 );
    cin >> m >> d;
    for( int i = 1; i <= m; ++ i )
    {
        char opt;
        ll k;
        cin >> opt >> k;
        if( opt == 'Q' )
        {
            t = query( cnt - k + 1, cnt );
            cout << t << '\n';
        }
        else
        {
            add( (k + t) % d );
        }
    }   
    return 0;
}

4. 复盘

• 复杂度对比:

  • 线段树: 修改 $O(\log M)$，查询 $O(\log M)$。空间 $O(M)$。

  • 动态 ST 表: 修改 $O(\log M)$，查询 $O(1)$。空间 $O(M \log M)$。

• 适用场景:

  • 线段树更加通用，支持任意位置修改、删除、合并等复杂操作。

  • 动态 ST 表是针对“只在末尾追加”这一特定场景的特化解，查询效率极高。

• 关联笔记: 线段树基础理论 | 倍增策略