1275 最大数（不带有懒标记的线段树）

绝地灬酷狼 2022-09-07 06:12 148阅读 0赞

**1. 问题描述：**

给定一个正整数数列 a1，a2，…，an，每一个数都在 0∼p−1 之间。可以对这列数进行两种操作：  
添加操作：向序列后添加一个数，序列长度变成 n+1；  
询问操作：询问这个序列中最后 L 个数中最大的数是多少。  
程序运行的最开始，整数序列为空。一共要对整数序列进行 m 次操作。写一个程序，读入操作的序列，并输出询问操作的答案。

**输入格式**

第一行有两个正整数 m,p，意义如题目描述；  
接下来 m 行，每一行表示一个操作。如果该行的内容是 Q L，则表示这个操作是询问序列中最后 L 个数的最大数是多少；  
如果是 A t，则表示向序列后面加一个数，加入的数是 (t+a) mod p。其中，t 是输入的参数，a 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 a=0）。  
第一个操作一定是添加操作。对于询问操作，L>0 且不超过当前序列的长度。

**输出格式**

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

**数据范围**

1 ≤ m ≤ 2 × 10 ^ 5,1 ≤ p ≤ 2 × 10 ^ 9,  
0 ≤ t < p

**输入样例：**

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。

来源：[https://www.acwing.com/problem/content/1277/][https_www.acwing.com_problem_content_1277]

**2. 思路分析：**

分析题目可以知道我们在添加数字的时候是在上一个序列的后面添加的，查询最大值为当前序列后面L个数字的最大值，也即查询某个区间的最大值，可以发现这些操作是动态修改与查询的过程，本质上是单点修改与区间查询的操作，根据这两个特点我们可以使用不带有懒标记的**线段树**来解决（模板题-本质上求解区间最大值问题），线段树最适合于求解区间修改的相关问题（包括单点修改与区间修改，单点修改没有懒标记，区间修改涉及到懒标记），不带有懒标记的线段树主要有4个操作，对应下面的四个方法：

*  void pushup（int u）， 将左右孩子节点的信息传递到当前根节点u的对应信息上（更新操作）
 *  void build(int u, int l, int r)，创建以当前的u为根节点，区间\[l，r\]的线段树节点，创建线段树的时候递归创建左右两边的区间，左右两个区间的分界点为mid = l + r >> 1，左边的区间为\[l, mid\]，右边的区间为\[mid + 1，r\]
 *  void modify(int u, int x, int v)，单点更新操作，当前的根节点为u，在x这个位置上加上v，在更新的时候需要递归找到更新的位置（根据当前根节点维护的区间\[l，r\]的中点与x的大小关系判断更新的区间在哪一边），在修改的过程中需要更新当前位置x涉及到所有区间的最大值
 *  void query(int u, int l, int r)，区间最大值查询操作，当前的根节点为u，查询区间\[l，r\]的区间最大值，在查询的时候当前根节点的区间包含在区间\[l ，r\]中那么返回当前根节点对应的区间最大值即可，否则根据当前根节点的区间中点与l，r的关系计算区间最大值即可

当前节点的编号为x，则左儿子节点编号为x << 1(2x)，右儿子的节点编号为x << 1 | 1（2x + 1），区间的中点为mid = l + r >> 1，左边的区间为\[l，mid\]，右边区间为\[mid + 1， r\]。

**3. 代码如下：**

**java：**

import java.util.Scanner;
    public class Main {
        static Tree []tree;
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int m = sc.nextInt();
            int p = sc.nextInt();
            // 接受回车符
            sc.nextLine();
            tree = new Tree[m * 4];
            // 初始化线段树节点
            for (int i = 0; i < m * 4; ++i){
                tree[i] = new Tree();
            }
            build(1, 1, m);
            int last = 0;
            int count = 1;
            for (int i = 0; i < m; ++i){
                String t[] = sc.nextLine().split(" ");
                int k = Integer.parseInt(t[1]);
                if (t[0].equals("A")) modify(1, count++, (k + last) % p);
                else{
                    last = query(1, count - k, count);
                    System.out.println(last);
                }
            }
        }
    
        // 创建线段树节点
        public static void build(int u, int l, int r){
            tree[u].l = l;
            tree[u].r = r;
            if (l == r) return;
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
        }
    
        // 子节点的信息传递到父节点
        public static void pushup(int u){
            tree[u].v = Math.max(tree[u << 1].v, tree[u << 1 | 1].v);
        }
    
        // 单点修改, 在x的位置上加上v
        public static void modify(int u, int x, int v){
            if (tree[u].l == x && tree[u].r == x){
                tree[u].v += v;
                return;
            }
            int mid = tree[u].l + tree[u].r >> 1;
            if (x <= mid) modify(u << 1, x, v);
            else modify(u << 1 | 1, x, v);
            pushup(u);
        }
    
        public static int query(int u, int l, int r){
            if (tree[u].l >= l && tree[u].r <= r) return tree[u].v;
            int mid = tree[u].l + tree[u].r >> 1;
            int v = 0;
            if (l <= mid) v = query(u << 1, l, r);
            if (r > mid) v = Math.max(v, query(u << 1 | 1, l, r));
            return v;
        }
        public static class Tree{
            private int l, r, v = 0;
        }
    }

**c++：**

#include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 200010;
    
    int m, p;
    struct Node
    {
        int l, r;
        int v;  // 区间[l, r]中的最大值
    }tr[N * 4];
    
    void pushup(int u)  // 由子节点的信息，来计算父节点的信息
    {
        tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
    }
    
    void build(int u, int l, int r)
    {
        tr[u] = {l, r};
        if (l == r) return;
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
    
    int query(int u, int l, int r)
    {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;   // 树中节点，已经被完全包含在[l, r]中了
    
        int mid = tr[u].l + tr[u].r >> 1;
        int v = 0;
        if (l <= mid) v = query(u << 1, l, r);
        if (r > mid) v = max(v, query(u << 1 | 1, l, r));
    
        return v;
    }
    
    void modify(int u, int x, int v)
    {
        if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
        else
        {
            int mid = tr[u].l + tr[u].r >> 1;
            if (x <= mid) modify(u << 1, x, v);
            else modify(u << 1 | 1, x, v);
            pushup(u);
        }
    }
    
    
    int main()
    {
        int n = 0, last = 0;
        scanf("%d%d", &m, &p);
        build(1, 1, m);
    
        int x;
        char op[2];
        while (m -- )
        {
            scanf("%s%d", op, &x);
            if (*op == 'Q')
            {
                last = query(1, n - x + 1, n);
                printf("%d\n", last);
            }
            else
            {
                modify(1, n + 1, (last + x) % p);
                n ++ ;
            }
        }
    
        return 0;
    }

[https_www.acwing.com_problem_content_1277]: https://www.acwing.com/problem/content/1277/