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 100
A 96
Q 1
A 97
Q 1
Q 2输出样例#1：
96
93
96说明
[JSOI2008]
思路的话。
首先冲着最大值
建一颗空树
然后加入就是单点修改
查询就是插后面的m位。。。。
但是这题在洛谷上AC
在COGS上爆零
-.-
还有就是不能开读入优化
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define lglg long long int
6 using namespace std;
7 const int n=200001;
8 lglg mod,m;
9 struct node
10 {
11 lglg l,r,w;
12 }tree[n*4];
13 lglg num=1;
14 lglg last=0;
15 lglg ans=-1;
16 void updata(int k)
17 {
18 tree[k].w=max(tree[k*2].w,tree[k*2+1].w);
19 }
20 void build(int ll,int rr,int k)
21 {
22 tree[k].l=ll;tree[k].r=rr;
23 if(tree[k].l==tree[k].r)
24 {
25 tree[k].w=0;
26 return ;
27 }
28 int m=(ll+rr)/2;
29 build(ll,m,k*2);
30 build(m+1,rr,k*2+1);
31 updata(k);
32 }
33 int read(lglg &x)
34 {
35 int flag=0;
36 char c=getchar();x=0;
37 if(c=='-')flag=1;
38 while(c<'0'||c>'9')c=getchar();
39 while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
40 return flag==1?x=-x:x;
41 }
42 void point_add(int where,int p,int k)
43 {
44 if(tree[k].l==tree[k].r)
45 {
46 tree[k].w=p;
47 return ;
48 }
49 int m=(tree[k].l+tree[k].r)/2;
50 if(where<=m)
51 point_add(where,p,k*2);
52 else
53 point_add(where,p,k*2+1);
54 updata(k);
55 }
56 void interval_ask(int ll,int rr,int k)
57 {
58 if(ll<=tree[k].l&&rr>=tree[k].r)
59 {
60 if(ans<tree[k].w)ans=tree[k].w;
61 return ;
62 }
63 int m=(tree[k].l+tree[k].r)/2;
64 if(ll<=m)
65 interval_ask(ll,rr,k*2);
66 if(rr>=m+1)
67 interval_ask(ll,rr,k*2+1);
68 }
69 int main()
70 {
71 //read(m);read(mod);
72 cin>>m>>mod;
73 build(1,n,1);
74 for(int i=1;i<=m;i++)
75 {
76 char c;
77 cin>>c;
78 if(c=='A')
79 {
80 lglg p;
81 //read(p);
82 cin>>p;
83 p=(p+last)%mod;
84 point_add(num++,p,1);
85 }
86 else
87 {
88 lglg p;
89 ans=-1;
90 //read(p);
91 cin>>p;
92 interval_ask(num-p,num-1,1);
93 last=ans%mod;
94 printf("%lld\n",ans);
95 }
96 }
97 return 0;
98 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-05-11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录