最大数
链接：https://www.acwing.com/problem/content/1277/
代码：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int N = 200010; 6 7 struct Node 8 { 9 int l, r, mx; 10 }tr[N * 4]; 11 12 int m, p; 13 14 void build(int u, int l, int r) 15 { 16 tr[u] = {l, r}; 17 if (l == r) return; 18 int mid = (l + r) >> 1; 19 build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); 20 } 21 22 void change(int u, int x, int v) 23 { 24 if (tr[u].l == x && tr[u].r == x) 25 { 26 tr[u] = {x, x, v}; 27 return; 28 } 29 30 int mid = (tr[u].l + tr[u].r) >> 1; 31 if (x <= mid) change(u << 1, x, v); 32 if (x > mid) change(u << 1 | 1, x, v); 33 tr[u].mx = max(tr[u << 1].mx, tr[u << 1 | 1].mx); 34 } 35 36 int query(int u, int l, int r) 37 { 38 if (l <= tr[u].l && tr[u].r <= r) 39 { 40 return tr[u].mx; 41 } 42 43 int mid = (tr[u].l + tr[u].r) >> 1; 44 int v = 0; 45 if (l <= mid) v = query(u << 1, l, r); 46 if (r > mid) v = max(v, query(u << 1 | 1, l, r)); 47 return v; 48 } 49 int main() 50 { 51 cin >> m >> p; 52 53 build(1, 1, m); 54 55 int last = 0, n = 0; 56 while (m -- ) 57 { 58 char op[2]; 59 int x; 60 cin >> op >> x; 61 if (*op == 'Q') 62 { 63 last = query(1, n - x + 1, n); 64 cout << last << " "; 65 } 66 else 67 { 68 change(1, n + 1, (x + last) % p); 69 n ++; 70 } 71 } 72 73 return 0; 74 }