洛谷-P1198 [JSOI2008]最大数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.io.*;
class Main{
    static Node[] tree;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter log  = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        String[] arr = read.readLine().split(" ");
        int m = Integer.valueOf(arr[0]);
        int d = Integer.valueOf(arr[1]);
        tree = new Node[4*m];
        int last = 0, n = 1;
        build(1, 1, m);
        while(m-- > 0){
            arr = read.readLine().split(" ");
            String s = arr[0];
            int x = Integer.valueOf(arr[1]);

            if(s.equals("Q")){
                //查询值
                last = query(1, n + 1 - x, n);
                log.write(last+"\n");
            }else{
                //插入值,根节点是1,修改结点从n+1开始
                modify(1, n+1, (x + last)%d);
                n++;
            }
        }
        log.flush();
    }

    // 构建线段树
    public static void build(int u, int l, int r){
        tree[u] = new Node(l, r);
        if(l == r){
            return;
        }
        // 否则构建左边、右边
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }

    // pushUp操作
    public static void pushUp(int u){
        tree[u].v = Math.max(tree[u << 1].v, tree[u << 1 | 1].v);
    }

    // 查询值
    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 void modify(int u, int x, int c){
        if(tree[u].l == x && tree[u].r == x){
            tree[u].v = c;
        }else{
            int mid = (tree[u].l + tree[u].r) >> 1;
            if(x <= mid){
                modify(u << 1, x, c);
            }else{
                modify(u << 1 | 1, x, c);
            }

            // 进行pushUp操作
            pushUp(u);
        }
    }

    static class Node{
        int l;
        int r;
        int v;
        Node(int l, int r){
            this.l = l;
            this.r = r;
        }
    }
}