【线段树入门】 P1198 最大数(区间最大值+无懒标记+末尾插入)

 1 //笔记-自用
 2 //#pragma GCC optimize("Ofast")
 3 //#pragma GCC optimize("unroll-loops")
 4 #define _CRT_SECURE_NO_WARNINGS
 5 #define All(a) a.begin(),a.end()
 6 #define INF 2147483647
 7 #include<bits/stdc++.h>
 8 #include<numeric>
 9 using namespace std;
10 typedef unsigned long long ull;
11 #define int long long//再也不用担心开longlong了><
12 typedef pair<int, int>PII;
13 const int N = 2e5 + 5;
14 #define lc p<<1
15 #define rc p<<1|1
16 struct node {
17     int l, r, val;
18 }tr[N*4];
19 int w[N];
20 void pushup(int p) {
21     tr[p].val = max(tr[lc].val, tr[rc].val);
22 }
23 void build(int p, int l, int r) {
24     tr[p] = { l,r,w[l]};
25     if (l == r)return;
26     int mid = l + r >> 1;
27     build(lc, l, mid);
28     build(rc, mid + 1, r);
29     pushup(p);
30 }
31 void update(int p, int x,int k) {//末尾插入操作等价于单点修改+扩容，所以建树的时候就应该建到最大值，并且用一个变量代表数组真实长度
32     if (x <= tr[p].l && tr[p].r <= x) {
33         tr[p].val = k;
34         return;
35     }
36     int mid = tr[p].l + tr[p].r >> 1;
37     if (x <= mid)update(lc, x, k);
38     if (x > mid)update(rc, x, k);
39     pushup(p);
40 }
41 int query(int p, int x, int y) {
42     if (x <= tr[p].l && tr[p].r <= y) {
43         return tr[p].val;
44     }
45     int mid = tr[p].l + tr[p].r >> 1;
46     int res = 0;
47     if (x <= mid)res = max(res, query(lc, x, y));
48     if (y > mid)res = max(res, query(rc, x, y));
49     return res;
50 }
51 signed main() {
52     ios::sync_with_stdio(false);
53     cin.tie(nullptr);
54     cout.tie(nullptr);
55     int n,mod;
56     int pre=0, len=0;
57     cin >> n >> mod;
58     build(1, 1, n);
59     while (n--) {
60         char op; int x;
61         cin >> op >> x;
62         if (op == 'A') {//末尾插入操作等价于单点修改+扩容，所以建树的时候就应该建到最大值，并且用一个变量代表数组真实长度
63             update(1, ++len, (x+pre) % mod);
64         }
65         else {
66             pre = query(1, len-x+1, len);
67             cout << pre << "\n";
68         }
69     }
70 
71 
72 }