[JSOI2008]最大数

 1 #include <bits/stdc++.h> 2 ?3 using namespace std; 4 ?5 #define re register 6 #define rep(i, a, b) for (re int i = a; i <= b; ++i) 7 #define repd(i, a, b) for (re int i = a; i >= b; --i) 8 #define maxx(a, b) a = max(a, b); 9 #define minn(a, b) a = min(a, b);10 #define LL long long11 #define inf (1 << 30)12 13 const int maxn = 2e5 + 5, N = 2e5;14 15 struct Seg_T {16 #define lson (o << 1)17 #define rson (o << 1 | 1)18 ????int v[maxn << 4];19 ????void pushup(int o) { v[o] = max(v[lson], v[rson]); }20 ????void add(int o, int l, int r, int x, int t) {21 ????????if (l == r) { v[o] = t; return; }22 ????????int mid = (l + r) >> 1;23 ????????if (x <= mid) add(lson, l, mid, x, t);24 ????????else add(rson, mid+1, r, x, t);25 ????????pushup(o);26 ????}27 ????int query(int o, int l, int r, int ql, int qr) {28 ????????if (ql <= l && r <= qr) return v[o];29 ????????int mid = (l + r) >> 1, ans = 0;30 ????????if (ql <= mid) ans = max(ans, query(lson, l, mid, ql, qr));31 ????????if (mid < qr) ans = max(ans, query(rson, mid+1, r, ql, qr));32 ????????return ans;33 ????}34 } S;35 36 int n, L = 0;37 LL D, t;38 39 int main() {40 ????scanf("%d %lld", &n, &D);41 42 ????rep(i, 1, n) {43 ????????char c[2]; LL x;44 ????????scanf("%s %lld", c, &x);45 ????????if (c[0] == ‘Q‘) printf("%lld\n", t = S.query(1, 1, N, L-x+1, L));46 ????????else {47 ????????????L++;48 ????????????S.add(1, 1, N, L, (t+x) % D);49 ????????}50 ????}51 52 ????return 0;53 }