首页 > 代码库 > AC日记——最大数 洛谷 P1198 [JSOI2008]
AC日记——最大数 洛谷 P1198 [JSOI2008]
题目描述
现在请求你维护一个数列，要求提供以下两种操作：
1、 查询操作。
语法：Q L
功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。
限制：L不超过当前数列的长度。
2、 插入操作。
语法：A n
功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。
限制：n是整数（可能为负数）并且在长整范围内。
注意：初始时数列是空的，没有一个数。
输入输出格式
输入格式：
第一行两个整数，M和D，其中M表示操作的个数(M <= 200,000)，D如上文中所述，满足(0<D<2,000,000,000)
接下来的M行，每行一个字符串，描述一个具体的操作。语法如上文所述。
输出格式：
对于每一个查询操作，你应该按照顺序依次输出结果，每个结果占一行。
输入输出样例
输入样例#1：
5 100A 96Q 1A 97Q 1Q 2
输出样例#1：
969396
说明
[JSOI2008]
思路：
离线做法，先把所有的操作都给存下来
分别记录查询和添加
然后按添加的操作数建树
然后剩下的不断进行查询操作同时也不断的更新单点
轻松ac
来，上代码：
#include <cstdio>#include <iostream>using namespace std;class node { public: int l,r,mid; long long int dis; void mid_() { mid=(l+r)>>1; }};class node tree[800001];int m,d,num_q=0,q_l[200100],q_r[200100];int num_a,a_[200010],cnt=0;long long int t;inline void tree_up(int now){ if(tree[now<<1].dis>tree[now<<1|1].dis) { tree[now].dis=tree[now<<1].dis; } else tree[now].dis=tree[now<<1|1].dis;}void tree_build(int now,int l,int r){ tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].dis=a_[++cnt]; return ; } tree[now].mid_(); tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r); tree_up(now);}void tree_change(int now,int to){ if(tree[now].l==tree[now].r&&tree[now].l==to) { tree[now].dis=(tree[now].dis+t)%d; return ; } if(to>tree[now].mid) tree_change(now<<1|1,to); else tree_change(now<<1,to); tree_up(now);}long long int tree_query(int now,int l,int r){ if(tree[now].l==l&&tree[now].r==r) { return tree[now].dis; } if(l>tree[now].mid) return tree_query(now<<1|1,l,r); else if(r<=tree[now].mid) return tree_query(now<<1,l,r); else return max(tree_query(now<<1,l,tree[now].mid),tree_query(now<<1|1,tree[now].mid+1,r));}int main(){ char ch; int now_; scanf("%d%d",&m,&d); for(int i=1;i<=m;i++) { cin>>ch>>now_; if(ch==‘Q‘) { num_q++; q_l[num_q]=num_a-now_+1; q_r[num_q]=num_a; } else { num_a++; a_[num_a]=now_; } } tree_build(1,1,num_a); cnt=0; for(int i=1;i<=num_q;i++) { while(cnt<q_r[i]) { tree_change(1,++cnt); } t=tree_query(1,q_l[i],q_r[i]); printf("%d\n",t); } return 0;}
AC日记——最大数 洛谷 P1198 [JSOI2008]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。