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;}P1198 [JSOI2008]最大数
原文地址：https://www.cnblogs.com/chloristendika/p/10101733.html