题解
我又十分不友好的复制题面了(懒)~~
题目描述
现在请求你维护一个数列,要求提供以下两种操作:
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
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define int long long
const int maxnn = 200200 ;
#define inf -0x3ffffff
using namespace std ;
struct dy{
int lc , rc , maxn ;
}tree[maxnn<<2];
int m , mod , tmp , t = 1 , ans = inf , k , q , tail ;
int a[maxnn] ;
char opt ;
void pushup(int u){
tree[u].maxn = max(tree[tree[u].lc].maxn,tree[tree[u].rc].maxn) % mod ;
}
void build(int u , int l , int r){//建树
tree[u].maxn = -inf ;
if(l == r){
return ;
}
int mid = (l+r) >> 1 ;
tree[u].lc = ++t ;
build(tree[u].lc,l,mid) ;
tree[u].rc = ++t ;
build(tree[u].rc,mid+1,r) ;
pushup(u) ;
}
void updata(int u , int l ,int r , int x , int w){//区间修改
if(r == x && l == x){
tree[u].maxn = w ;
return ;
}
int mid = (l+r) >> 1 ;
if(x <= mid) updata(tree[u].lc ,l,mid,x,w) ;
else
if(x > mid) updata(tree[u].rc,mid+1,r,x,w) ;
pushup(u) ;
}
void query(int u,int l,int r,int ll,int rr){//查找区间最大值
if(l == ll && r == rr){
ans=max(ans,tree[u].maxn) ;
return ;
}
int mid = (l+r) >> 1 ;
if(rr <= mid) query(tree[u].lc,l,mid,ll,rr) ;
else if(ll > mid) query(tree[u].rc,mid+1,r,ll,rr) ;
else{
query(tree[u].lc,l,mid,ll,mid) ;
query(tree[u].rc,mid+1,r,mid+1,rr) ;
}
}
signed main(){
cin >> m >> mod ;
build(1,1,m) ;
for(int i = 1 ; i <= m ; i ++){
cin >> opt ;
if(opt == 'A'){
cin >> k ;
k = (k+tmp) % mod ;
tail ++ ;
updata(1,1,m,tail,k) ;
}
if(opt == 'Q'){
ans = inf;
scanf("%lld",&q);
if(!q) tmp = 0;
else{
int l,r ;
r = tail ;
l = tail-q+1 ;
query(1,1,m,l,r);
tmp = ans;
}
printf("%lld\n",tmp);
}
}
return 0 ;
}
return 0 ;