[BZOJ 1012][JSOI2008]最大数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
A 96
Q 1
A 97
Q 1
Q 2
Sample Output
93
96
HINT
Source
裸线段树,虽然说这题很裸,不过还是得动番脑筋的,每次只能插入一个数,插入一个数就维护一次线段树,查询和线段树的建立就比较好操作了,刚开始用白书的模板套这题,不过没成功,这里的范围太大(20W),很容易爆数组,因此为了省空间,子节点不应是父节点编号的2倍和2倍+1,而应是父节点编号+1和+2,最后我用结构体保存线段树,结构体含该结点的区间左右端点和左右子树对应编号,然后就OK了
#include <stdio.h> #include <string.h> #define MAXN 4000000 #define INF 10000000 struct node { int maxv; int l,r; //结点线段的左右端点 int lc,rc; //左右子树对应编号 }tree[MAXN]; int ans,total=0; //结点编号需要一次一次加1,不能让左子树等于根节点编号的2倍,否则会爆内存 int max(int a,int b) { if(a>b) return a; return b; } void build(int L,int R) //L=区间左端点,R=区间右端点 { total++; int now=total; //now=当前结点编号 int M=(L+R)/2; //线段中点 tree[now].l=L; tree[now].r=R; if(L<R) { tree[now].lc=total+1; build(L,M); tree[now].rc=total+1; build(M+1,R); } } void query(int o,int L,int R) //在[L,R]内查询编号为o的结点最大元素值 { if(L<=tree[o].l&&tree[o].r<=R) //查询区间是结点o对应线段区间的子集,直接返回结点o对应的最大数 { ans=max(ans,tree[o].maxv); return; } if(R<=tree[tree[o].lc].r) query(tree[o].lc,L,R); //如果左子树线段完全覆盖查询区间,则向下查询左子树的最大值 else if(L>=tree[tree[o].rc].l) query(tree[o].rc,L,R); //反之,向下查询右子树的最大值 else //否则,查询区间是结点o的线段的真子集,查询[L,左子树右端点]和[右子树左端点,R]的最大值 { query(tree[o].lc,L,tree[tree[o].lc].r); query(tree[o].rc,tree[tree[o].rc].l,R); } } void insert(int o,int pos,int n) //在结点编号为o的pos位置加入n { if(tree[o].l==pos&&tree[o].r==pos) //叶节点 { tree[o].maxv=n; return; } if(pos<=tree[tree[o].lc].r) insert(tree[o].lc,pos,n); //pos位置处于o结点左子树 else if(pos>=tree[tree[o].rc].l) insert(tree[o].rc,pos,n); //pos位置处于o结点右子树 tree[o].maxv=max(tree[tree[o].lc].maxv,tree[tree[o].rc].maxv); //更新结点最大值 } int main() { int t=0,i,j,M,D,n,len=0; char CHin[4]; build(1,MAXN-20); scanf("%d%d",&M,&D); for(i=0;i<M;i++) { scanf("%s%d",CHin,&n); if(CHin[0]=='A') { len++; insert(1,len,(n+t)%D); //在线段尾部加入元素 } else { ans=-INF; query(1,len-n+1,len); //查询最后n个数的最大数 t=ans; printf("%d\n",t); } } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。