P1198 [JSOI2008]最大数
题目描述
现在请求你维护一个数列，要求提供以下两种操作：
1、 查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：LL不超过当前数列的长度。(L > 0)(L>0)
2、 插入操作。
语法：A n
功能：将nn加上tt，其中tt是最近一次查询操作的答案（如果还未执行过查询操作，则t=0t=0)，并将所得结果对一个固定的常数DD取模，将所得答案插入到数列的末尾。
限制：nn是整数（可能为负数）并且在长整范围内。
注意：初始时数列是空的，没有一个数。
输入格式
第一行两个整数，MM和DD，其中MM表示操作的个数(M \le 200,000)(M≤200,000)，DD如上文中所述，满足(0<D<2,000,000,000)(0<D<2,000,000,000)
接下来的MM行，每行一个字符串，描述一个具体的操作。语法如上文所述。
输出格式
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
输入输出样例
输入 #1复制
5 100
A 96
Q 1
A 97
Q 1
Q 2
输出 #1复制
96
93
96
说明/提示
[JSOI2008]
本题数据已加强
题解：为线段树基础……适合刚学线段树的人写一下开拓一下思路。根据题目我们可以将线段的sum改为该线段中的最大值，这样会简单快速许多，具体见下代码；
#define _CRT_SECURE_NO_DepRECATE
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <string>
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <cctype>
#include <iterator>
#include <vector>
#include <cstring>
#include <cassert>
#include <map>
#include <queue>
#include <set>
#include <stack>
#define ll long long
#define INF 0x3f3f3f3f
#define ld long double
const ld pi = acos(-.0L), eps = 1e-;
int qx[] = { ,,,- }, qy[] = { ,-,, }, qxx[] = { ,- }, qyy[] = { ,- };
using namespace std;
struct node
{
ll l = , r = , sum = , plz = , mlz = ;
}tree[];
ll p = INF, maxx;
inline void build(int i, int l, int r, int insert,int num)//树的编号 最左端 最右端 插入的值 插入的下标
{
tree[i].l = l;
tree[i].r = r;
if (l == r)//找到该点即替换为insert
{
tree[i].sum = insert;
}
else
{
if ((l + r) / >= num)
{
build(i << , l, (l + r) / , insert, num);
}
else
{
build(i << | , (l + r) / + , r, insert, num);
}
tree[i].sum = max(tree[i << ].sum, tree[i << | ].sum);//每个线段的sum为该线段的最大值
}
}
inline ll search_max(int i, int l, int r)
{
if (tree[i].l >= l && tree[i].r <= r)//因sum即代表该线段的最大值，所以找到完全包含的线段就可以直接返回sum
{
return tree[i].sum;
}
if (tree[i].l > r || tree[i].r < l)
{
return ;
}
ll ans = -INF;
if (l <= tree[i << ].r)
{
ans = max(ans, search_max(i << , l, r));
}
if (r >= tree[i << | ].l)
{
ans = max(ans, search_max(i << | , l, r));
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
ll m, d, t = , sum = , b,input;
char x;
cin >> m >> d;
for (int i = ; i < m; i++)
{
cin >> x;
if (x == 'A')
{
cin >> input;
input = (input + t) % d;
build(, , m, input, sum);//因为最多只能插入m个，所以可以直接以m为r
sum++;
}
else
{
cin >> b;
t = search_max(, sum - b, sum - );
cout << t << endl;
}
}
return ;
}