题解 P1198 【[JSOI2008]最大数】

线段树基础题。 ```cpp #include <cstdio> #define Lovelive long long #define lr (u << 1) #define rr (u << 1 | 1) #define lt l, m, lr #define rt m + 1, r, rr #define tt int l, int r, int u #define lld "%lld" #define maxn 200010 #define INF 0x3F3F3F3F3F3F3F3FLL Lovelive maxv[maxn << 2]; template <typename T> inline T max(T a, T b) { return a > b ? a : b; } void maintain(tt) { if(l < r) maxv[u] = max(maxv[lr], maxv[rr]); } void modify(int pos, Lovelive c, tt) { int m = (l + r) >> 1; if(l == r) { maxv[u] = c; return ; } if(pos <= m) modify(pos, c, lt); else modify(pos, c, rt); maintain(l, r, u); } Lovelive query(int L, int R, tt) { if(L <= l && r <= R) return maxv[u]; int m = (l + r) >> 1; Lovelive ret = -INF; if(L <= m) ret = max(ret, query(L, R, lt)); if(R >= m + 1) ret = max(ret, query(L, R, rt)); return ret; } Lovelive m, d, last, len, x; char tmp[2333]; int main() { for(int i = 0; i < maxn << 2; i++) maxv[i] = -INF; scanf(lld lld, &m, &d); for(int i = 0; i < m; i++) { scanf("%s"lld, tmp, &x); if(tmp[0] == 'A') { len ++; modify(len, (x + last) % d, 1, 200000, 1); } else { if(!x) last = 0; else last = query(len - x + 1, len, 1, 200000, 1); printf(lld"\n", last); } } return 0; } ```