st 表 和 分块 都可做 还跑得很快
然而我只会线段树
题目要求是线段树的插入操作
直接考虑建一棵足够大的线段树,插入操作就变成了 单点修改操作
剩下的查询直接查询$ (x ?- ?L ?+ ?1, ?x )$
code:
#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 200001;const ll INF = 99999999999999;int n;ll D, t = 0, a[N], cnt = 0;struct Stree { int l, r; ll maxi; }tree[N * 3]; void pushup(int rt) { tree[rt].maxi = max(tree[rt << 1].maxi, tree[rt << 1 | 1].maxi);}void build(int l, int r, int rt) { if(l == r) { tree[rt].maxi = -INF; return; } int mid = (l + r) >> 1; build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1); pushup(rt);}void upd(int idx, int C, int l, int r, int rt) { if(l == r) { tree[rt].maxi = C; return; } int mid = (l + r) >> 1; if(idx <= mid) upd(idx, C, l, mid, rt << 1); else upd(idx, C, mid + 1, r, rt << 1 | 1); pushup(rt);}ll Quary(int L, int R, int l, int r, int rt) { if(L <= l && r <= R) return tree[rt].maxi; int mid = (l + r) >> 1; ll a = -INF, b = -INF; if(L <= mid) a = Quary(L, R, l, mid, rt << 1); if(R > mid) b = Quary(L, R, mid + 1, r, rt << 1 | 1); return max(a, b);}int main() { scanf("%d %lld", n, D); build(1, N, 1); for(int i = 1; i <= n; i++) { char opt; ll x; cin >> opt; scanf("%lld", &x); if(opt == 'A') { x += t; x %= D; cnt++; upd(cnt, x, 1, N, 1); } else { t = Quary(cnt - x + 1, cnt, 1, N, 1); printf("%lld\n", t); } } return 0;}