BZOJ1012:[JSOI2008]最大数——题解
阅读原文时间:2023年07月11日阅读:1

https://www.lydsy.com/JudgeOnline/problem.php?id=1012

https://www.luogu.org/problemnew/show/P1198

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

倒着来st表即可。

(当然平衡树啊动态线段树啊分块啊都能做,选一个最简单的做。)

洛谷数据很恶心,如果你TLE了不妨与main函数对比一下。

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=4e5+;
const int B=;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar(); return w?-X:X; } ll dp[N][B+]; int lg[N]; char s[]; inline ll qry(int l,int r){ if(l>r)return ;
int h=lg[r-l+];
return max(dp[r][h],dp[l+(<<h)-][h]);
}
int main(){
int m=read(),d=read(),n=;ll t=,k;
lg[]=;
while(m--){
scanf("%s%lld",s,&k);
if(s[]=='Q'){
printf("%lld",t=qry(n-k+,n));
putchar();
}
if(s[]=='A'){
k=(k+t)%d;
dp[++n][]=k;
if(n!=){
lg[n]=lg[n-];
if((<<lg[n]+)==n)lg[n]++;
}
for(int j=;j<=lg[n];j++){
if(n-(<<j)+<)break;
dp[n][j]=max(dp[n][j-],dp[n-(<<j-)][j-]);
}
}
}
return ;
}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客:http://www.cnblogs.com/luyouqi233/ +

+++++++++++++++++++++++++++++++++++++++++++

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章