BZOJ1012【JSOI2008】最大数 <线段树>

Problem

最大数

题目描述

现在请求你维护一个数列，要求提供以下两种操作：

1. 查询操作。
   语法：$Q\ \ L$
   功能：查询当前数列中末尾$L$个数中的最大的数，并输出这个数的值。
   限制：$L$不超过当前数列的长度。
2. 插入操作。
   语法：$A\ \ n$
   功能：将$n$加上$t$，其中$t$是最近一次查询操作的答案（如果还未执行过查询操作，则$t=0$），并将所得结果对一个固定的常数$D$取模，将所得答案插入到数列的末尾。
   限制：$n$是整数（可能为负数）并且在长整范围内。

注意：初始时数列是空的，没有一个数。

输入输出格式

输入格式
第一行两个整数，$M$和$D$，其中$M$表示操作的个数$(M\le 2\times 10^5)$，$D$如上文中所述，满足$(0<D<2\times 10^9)$
接下来的$M$行，每行一个字符串，描述一个具体的操作。语法如上文所述。
输出格式
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

输入输出样例

输入样例

5 100
A 96
Q 1
A 97
Q 1
Q 2

输出样例

96
93
96

标签：线段树

Solution

线段树裸题。
记录当前长度$len$，每个结点维护区间最大值，操作$1$为$query(len-L+1, len)$，操作$2$为$modify(++len, (n+t)\%D)$。

Code

#include <iostream>
#include <cstdio>
#define MAX_N 200000
#define INF 2000000000
#define ll long long
using namespace std;
ll tree[MAX_N*4+50];
int n, len = 0;
void updata(int v) {
    tree[v] = max(tree[v<<1], tree[v<<1|1]);
}
void build(int v, int s, int t) {
    if (s == t) {
        tree[v] = -INF;
        return;
    }
    int mid = s+t>>1;
    build(v<<1, s, mid);
    build(v<<1|1, mid+1, t);
    updata(v);
}
void modify(int v, int s, int t, int pos, ll x) {
    if (s == t) {
        tree[v] = x;
        return;
    }
    int mid = s+t>>1;
    if (pos <= mid) {
        modify(v<<1, s, mid, pos, x);
    } else {
        modify(v<<1|1, mid+1, t, pos, x);
    }
    updata(v);
}
ll query(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) {
        return tree[v];
    }
    int mid = s+t>>1;
    ll ret = -INF;
    if (l <= mid) {
        ret = max(ret, query(v<<1, s, mid, l, r));
    }
    if (r >= mid+1) {
        ret = max(ret, query(v<<1|1, mid+1, t, l, r));
    }
    return ret;
}
int main() {
    ll x, prev = 0, mod;
    char opt;
    int l;
    scanf("%d%lld", &n, &mod);
    build(1, 1, n);
    for (int i = 0; i < n; i++) {
        cin >> opt;
        if (opt == 'A') {
            scanf("%lld", &x);
            modify(1, 1, n, ++len, (x%mod+prev)%mod);
        } else {
            scanf("%d", &l);
            prev = query(1, 1, n, len-l+1, len);
            printf("%lld\n", prev);
            prev %= mod;
        }
    }
    return 0;
}