首页 > 代码库 > [JSOI2008]最大数
[JSOI2008]最大数
题目：洛谷P1198、BZOJ1012
题目大意：要你维护一个数列，支持两个操作:①查询当前数列中末尾L个数里的最大数;②读入s，在数列尾部插入$(s+t)%D$（t是上次询问的值，初始为0）。
解题思路：线段树。m最大为200000，开一个线段树，初始化为一个很小的值，然后直接插入、查询即可。
C++ Code：
#include<cstdio>#include<algorithm>#include<cstring>#define N 200000using namespace std;int t=0,m,D,l,r,d[2*N+6],endd=0;char c[12];void insert(int L,int R,int o){ if(L==R){ d[o]=r; return; } int m=(L+R)>>1; if(endd<=m)insert(L,m,o<<1);else insert(m+1,R,o<<1|1); d[o]=max(d[o<<1],d[o<<1|1]);}int query(int L,int R,int o){ if(l<=L&&R<=r)return d[o]; int m=(L+R)>>1; int x=0x80808080,y=0x80808080; if(l<=m)x=query(L,m,o<<1); if(m<r)y=query(m+1,R,o<<1|1); return max(x,y);}int main(){ memset(d,0x80,sizeof(d)); scanf("%d%d",&m,&D); while(m--){ scanf("%s %d",c,&r); if(c[0]==‘A‘){ endd++; r=(r+t)%D; insert(1,N,1); }else{ l=endd-r+1; r=endd; t=query(1,N,1); printf("%d\n",t); } } return 0;}
[JSOI2008]最大数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。