最大数（信息学奥赛一本通- P1549）（洛谷-P1198）

原题来自：JSOI 2008

给定一个正整数数列 a1,a2,a3,⋯,an ，每一个数都在 0∼p–1 之间。可以对这列数进行两种操作：

添加操作：向序列后添加一个数，序列长度变成 n+1；

询问操作：询问这个序列中最后 L 个数中最大的数是多少。

程序运行的最开始，整数序列为空。写一个程序，读入操作的序列，并输出询问操作的答案。

第一行有两个正整数 m,p，意义如题目描述；

接下来 m 行，每一行表示一个操作。如果该行的内容是 Q L，则表示这个操作是询问序列中最后 L 个数的最大数是多少；如果是 A t，则表示向序列后面加一个数，加入的数是 (t+a)modp。其中，t 是输入的参数，a 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 a=0）。

第一个操作一定是添加操作。对于询问操作，L>0 且不超过当前序列的长度。

对于每一个询问操作，输出一行。该行只有一个数，即序列中最后 L 个数的最大数。

样例说明

最后的序列是 97,14,60,96。

数据范围与提示：

对于全部数据，1≤m≤2×10^5,1≤p≤2×10^9,0≤t<p。

一、 题目分析

本题要求我们维护一个初始为空的序列，并支持两种极高频率的操作：

1. 添加操作 (A t)：在序列末尾追加一个数，该数的值与上一次查询的结果有关（强制在线）。

2. 询问操作 (Q L)：查询当前序列中，最后L个数的最大值。

数据规模：操作总数M≤2×10^5，数字大小p≤2×10^9。 面对20万次的动态修改和区间查询，暴力的O(N)扫描必将导致超时。我们需要一种能在O(logN)时间内完成修改和查询的数据结构——线段树。

二、 思考过程：化动态为静态

同学们刚开始看到这道题，最大的疑惑往往是：“序列一开始是空的，长度在不断增加，我该怎么建线段树？”

如果每次添加数字都去动态改变线段树的管辖范围（例如让根节点从管辖[1,1]变成管辖[1,2]），会导致线段树在计算中点mid=(l+r)/2时发生偏移，原本存好的底层数据会彻底“串槽”丢失。

破局核心（动态化静态）： 题目给出了一个极其关键的隐藏条件：操作总数 M≤200000。这意味着，无论怎么添加，最终序列的长度绝对不会超过 200000。因此，我们可以直接在内存中建一棵管辖范围死死固定为[1, 200000]的大线段树。一开始这栋20万个房间的大楼是空的，我们维护一个全局变量cnt记录当前有几个数，每来一个新数字，就相当于让它住进大楼的第cnt个房间（单点修改）。

三、 解题思路与算法设计

理清了“固定地基”的概念，算法设计就水到渠成了：

1. 核心数据结构：维护区间最大值的线段树。由于只是在尾部追加数字，不涉及区间大面积修改，所以不需要懒标记（Lazy Tag）。

2. 添加操作 (A)：

   • 序列长度增加：cnt++。

   • 计算真实值：x=(t+a)%p。

   • 执行单点修改：在线段树中将第cnt个位置的值更新为x。

3. 查询操作 (Q)：

   • 题目要求求“最后L个数”的最大值。

   • 既然当前共有cnt个数，那么最后L个数对应的绝对区间就是：[cnt-L+1,cnt]。

   • 直接调用线段树的区间求最大值查询即可，并将结果存入变量a中以备后用。

四、 时空复杂度分析

• 时间复杂度：

  • 无需额外建树（因为初始全为0）。

  • 单次添加（单点修改）：O(logM)。

  • 单次询问（区间查询）：O(logM)。

  • 总时间复杂度：O(MlogM)，在 20 万的数据规模下，耗时通常在几十毫秒内，极其高效。

• 空间复杂度：线段树需要开最大容量的4倍空间，O(4×M)，完全在题目限制范围内。

五、 易错总结

1. 地址错乱（初学线段树同学极易出错）： 在执行update和query时，根节点的右边界必须传入固定的最大容量n（即操作总数M），绝不能传入当前的元素个数cnt。线段树的管辖边界一旦确定，一寸都不能动。

2. 数据溢出： 计算(t+a)%p时，由于t和a都可能高达2×10^9，两个int相加会瞬间撑爆导致变成负数。必须将t和a定义为long long。

3. 变量遮蔽： 如果全局定义了操作次数m，在递归函数中计算中点时，切忌再写int m=(l+r)>>1;，这会触发变量遮蔽。养成良好的工程习惯，中点统一使用mid。

六、完整代码

//单点修改 区间求最值 线段树 #include <iostream> #include <algorithm>//对应min max函数 using namespace std; const int maxn=200010;//序列元素可能出现的最大个数 int m,p; int cnt;//代表现在序列中实际有多少个数 //线段树节点封装 struct node{ long long val;//节点所所代表区间最大值 }tree[maxn<<2];//线段树要开四倍最大元素大小 //向上更新 把左儿子和右儿子中的最大值给到父节点 void pushup(int rt){ tree[rt].val=max(tree[rt<<1].val,tree[rt<<1|1].val); } //一开始序列为空，所以更新操作替代建树操作 //原序列第K个数增加x 当前节点为rt 节点所管辖区间[l,r] void update(int k,long long x,int l,int r,int rt){ //当递归到叶子节点，叶子节点区间最大值就是自己 if(l==r){ tree[rt].val=x; return; } int mid=(l+r)>>1; //如果k在当前节点管辖区间左半区间 递归左子树 if(k<=mid) update(k,x,l,mid,rt<<1); //如果k在当前节点管辖区间右半区间 递归右子树 else update(k,x,mid+1,r,rt<<1|1); //最后通过左儿子和右儿子更新当前节点 pushup(rt); } //查询[L,R]区间的最大值，当前节点为rt //rt所带代表区间为[l,r] long long query(int L,int R,int l,int r,int rt){ //当查询区间覆盖当前节点所管辖区间时 //直接返回当前节点所管辖区间的最大值 if(L<=l&&R>=r){ return tree[rt].val; } //当查询区间和当前节点所管辖区间无重叠时 //返回个不影响求最大值的极小值0（不会影响结果） if(L>r||R<l) return 0; int mid=(l+r)>>1; //ans记录最大值 long long ans=0; //当与左子树有重合，递归查询左子树的最大值 if(L<=mid) ans=max(ans,query(L,R,l,mid,rt<<1)); //当与右子树有重合，递归查询右子树的最大值 if(R>mid) ans=max(ans,query(L,R,mid+1,r,rt<<1|1)); return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>m>>p; int n=m;//存储最多可能有多个数 //第一个操作一定是添加操作，之前没有询问操作 //所以a=0 long long a=0; //总共有m次操作 while(m--){ char flag; cin>>flag; if(flag=='A'){//加数 long long t; cin>>t; long long x=1ll*(t+a)%p; cnt++;//序列中增加了一个数字 update(cnt,x,1,n,1); } else{//询问序列中最后L个数的最大数是多少 int L; cin>>L; //最后L个数所表示区间为[cnt-L+1,cnt] a=query(cnt-L+1,cnt,1,n,1); cout<<a<<"\n"; } } return 0; }