【BZOJ1012】【树状数组求区间最值】最大数maxnumber

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Description

现在请求你维护一个数列，要求提供以下两种操作： 1、查询操作。语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。 2、插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个数。

Input

第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0

Output

对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。

Sample Input

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

Sample Output

96
93
96

HINT

【分析】

Orz。。。无所不能的树状数组，自己看代码看得懂吧。。。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <map> const int MAXN = + ;
const int MAX = + ;
using namespace std;
typedef long long ll;
ll m, MOD, l;
ll C[MAXN], num[MAXN]; void init(){
memset(C, , sizeof(C));
l = ;//l代表的是整个序列的长度
scanf("%lld%lld", &m, &MOD); }
ll lowbit(ll x) {return x & -x;}
ll Max(ll l, ll r){
ll cnt = num[r];
while (l <= r){
cnt = max(cnt, num[r]);
for (--r; r - l >= lowbit(r); r -= lowbit(r)) cnt = max(cnt, C[r]);
//cnt = max(cnt, C[r]);
}
return cnt;
}
void work(){
ll last = ;//表示上一次查询的答案
for (int i = ; i <= m; i++){
char str[];
scanf("%s", str);
if (str[] == 'Q'){
int a;
scanf("%lld", &a);
last = Max(l - a + , l);
printf("%lld\n", last);//[a,l]区间内的最大值
}else{
ll x;
scanf("%lld", &x);
num[++l] = (x + last) % MOD;
C[l] = max(Max(l - lowbit(l) + , l - ), (x + last) % MOD); }
}
} int main(){
int T;
#ifdef LOCAL
freopen("data.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
init();
work();
return ;
}