题目链接:
看到单点更新和查询先想到线段树, 初始化直接将所有的位置看成 0, 就只有单点修改和单点查询了.
- #include<bits/stdc++.h>
- #define lson l,mid,i<<1
- #define rson mid+1,r,i<<1|1
- #define mid (l+r)/2
- using namespace std;
- typedef long long ll;
- const int maxn = 2e5 + 10;
- ll Max[maxn <<2];
- inline ll read() {
- ll n = 0, f = 1; char ch = getchar();
- while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
- while (ch>= '0'&&ch <= '9') { n = n * 10 + ch - '0'; ch = getchar(); }
- return n * f;
- }
- void up(int i) {
- Max[i] = max(Max[i <<1], Max[i << 1 | 1]);
- }
- void update(int p, ll x, int l, int r, int i) {
- if (l == r) {
- Max[i] = x;
- return;
- }
- if (p <= mid)
- update(p, x, lson);
- else
- update(p, x, rson);
- up(i);
- }
- ll query(int L, int R, int l, int r, int i) {
- if (L <= l && r <= R)
- return Max[i];
- ll MMax = 0;
- if (L <= mid)
- MMax = max(MMax, query(L, R, lson));
- if (R> mid)
- MMax = max(MMax, query(L, R, rson));
- return MMax;
- }
- char q[3];
- int main() {
- ll n, d, x, t = 0, len = 0;
- n = read(), d = read();
- for (int i = 1; i <= n; i++) {
- scanf("%s", q);
- x = read();
- if (q[0] == 'A') {
- x = (x + t) % d;
- len++;
- update(len, x, 1, n, 1);
- }
- else {
- t = query(len - x + 1, len, 1, n, 1);
- printf("%lld\n", t);
- }
- }
- }
[Bzoj1012][JSOI2008] 最大数 maxnumber
来源: http://www.bubuko.com/infodetail-3110201.html