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

【题目描述】原题来自JSOI 2008给定一个正整数数列 a1,a2,a3,⋯,an 每一个数都在 0∼p–1 之间。可以对这列数进行两种操作添加操作向序列后添加一个数序列长度变成 n1询问操作询问这个序列中最后 L 个数中最大的数是多少。程序运行的最开始整数序列为空。写一个程序读入操作的序列并输出询问操作的答案。【输入】第一行有两个正整数 m,p意义如题目描述接下来 m 行每一行表示一个操作。如果该行的内容是 Q L则表示这个操作是询问序列中最后 L 个数的最大数是多少如果是 A t则表示向序列后面加一个数加入的数是 (ta)modp。其中t 是输入的参数a 是在这个添加操作之前最后一个询问操作的答案如果之前没有询问操作则 a0。第一个操作一定是添加操作。对于询问操作L0 且不超过当前序列的长度。【输出】对于每一个询问操作输出一行。该行只有一个数即序列中最后 L 个数的最大数。【输入样例】10 100 A 97 Q 1 Q 1 A 17 Q 2 A 63 Q 1 Q 1 Q 3 A 99【输出样例】97 97 97 60 60 97【提示】样例说明最后的序列是 97,14,60,96。数据范围与提示对于全部数据1≤m≤2×10^5,1≤p≤2×10^9,0≤tp。一、 题目分析本题要求我们维护一个初始为空的序列并支持两种极高频率的操作添加操作 (A t)在序列末尾追加一个数该数的值与上一次查询的结果有关强制在线。询问操作 (Q L)查询当前序列中最后L个数的最大值。数据规模操作总数M≤2×10^5数字大小p≤2×10^9。 面对20万次的动态修改和区间查询暴力的O(N)扫描必将导致超时。我们需要一种能在O(logN)时间内完成修改和查询的数据结构——线段树。二、 思考过程化动态为静态同学们刚开始看到这道题最大的疑惑往往是“序列一开始是空的长度在不断增加我该怎么建线段树”如果每次添加数字都去动态改变线段树的管辖范围例如让根节点从管辖[1,1]变成管辖[1,2]会导致线段树在计算中点mid(lr)/2时发生偏移原本存好的底层数据会彻底“串槽”丢失。破局核心动态化静态 题目给出了一个极其关键的隐藏条件操作总数 M≤200000。这意味着无论怎么添加最终序列的长度绝对不会超过 200000。因此我们可以直接在内存中建一棵管辖范围死死固定为[1, 200000]的大线段树。一开始这栋20万个房间的大楼是空的我们维护一个全局变量cnt记录当前有几个数每来一个新数字就相当于让它住进大楼的第cnt个房间单点修改。三、 解题思路与算法设计理清了“固定地基”的概念算法设计就水到渠成了核心数据结构维护区间最大值的线段树。由于只是在尾部追加数字不涉及区间大面积修改所以不需要懒标记Lazy Tag。添加操作 (A)序列长度增加cnt。计算真实值x(ta)%p。执行单点修改在线段树中将第cnt个位置的值更新为x。查询操作 (Q)题目要求求“最后L个数”的最大值。既然当前共有cnt个数那么最后L个数对应的绝对区间就是[cnt-L1,cnt]。直接调用线段树的区间求最大值查询即可并将结果存入变量a中以备后用。四、 时空复杂度分析时间复杂度无需额外建树因为初始全为0。单次添加单点修改O(logM)。单次询问区间查询O(logM)。总时间复杂度O(MlogM)在 20 万的数据规模下耗时通常在几十毫秒内极其高效。空间复杂度线段树需要开最大容量的4倍空间O(4×M)完全在题目限制范围内。五、 易错总结地址错乱初学线段树同学极易出错 在执行update和query时根节点的右边界必须传入固定的最大容量n即操作总数M绝不能传入当前的元素个数cnt。线段树的管辖边界一旦确定一寸都不能动。数据溢出 计算(ta)%p时由于t和a都可能高达2×10^9两个int相加会瞬间撑爆导致变成负数。必须将t和a定义为long long。变量遮蔽 如果全局定义了操作次数m在递归函数中计算中点时切忌再写int m(lr)1;这会触发变量遮蔽。养成良好的工程习惯中点统一使用mid。六、完整代码//单点修改 区间求最值 线段树 #include iostream #include algorithm//对应min max函数 using namespace std; const int maxn200010;//序列元素可能出现的最大个数 int m,p; int cnt;//代表现在序列中实际有多少个数 //线段树节点封装 struct node{ long long val;//节点所所代表区间最大值 }tree[maxn2];//线段树要开四倍最大元素大小 //向上更新 把左儿子和右儿子中的最大值给到父节点 void pushup(int rt){ tree[rt].valmax(tree[rt1].val,tree[rt1|1].val); } //一开始序列为空所以更新操作替代建树操作 //原序列第K个数增加x 当前节点为rt 节点所管辖区间[l,r] void update(int k,long long x,int l,int r,int rt){ //当递归到叶子节点叶子节点区间最大值就是自己 if(lr){ tree[rt].valx; return; } int mid(lr)1; //如果k在当前节点管辖区间左半区间 递归左子树 if(kmid) update(k,x,l,mid,rt1); //如果k在当前节点管辖区间右半区间 递归右子树 else update(k,x,mid1,r,rt1|1); //最后通过左儿子和右儿子更新当前节点 pushup(rt); } //查询[L,R]区间的最大值当前节点为rt //rt所带代表区间为[l,r] long long query(int L,int R,int l,int r,int rt){ //当查询区间覆盖当前节点所管辖区间时 //直接返回当前节点所管辖区间的最大值 if(LlRr){ return tree[rt].val; } //当查询区间和当前节点所管辖区间无重叠时 //返回个不影响求最大值的极小值0不会影响结果 if(Lr||Rl) return 0; int mid(lr)1; //ans记录最大值 long long ans0; //当与左子树有重合递归查询左子树的最大值 if(Lmid) ansmax(ans,query(L,R,l,mid,rt1)); //当与右子树有重合递归查询右子树的最大值 if(Rmid) ansmax(ans,query(L,R,mid1,r,rt1|1)); return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinmp; int nm;//存储最多可能有多个数 //第一个操作一定是添加操作之前没有询问操作 //所以a0 long long a0; //总共有m次操作 while(m--){ char flag; cinflag; if(flagA){//加数 long long t; cint; long long x1ll*(ta)%p; cnt;//序列中增加了一个数字 update(cnt,x,1,n,1); } else{//询问序列中最后L个数的最大数是多少 int L; cinL; //最后L个数所表示区间为[cnt-L1,cnt] aquery(cnt-L1,cnt,1,n,1); couta\n; } } return 0; }