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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我的博客

echo、print、print_r、var_dump使用和区别

1、echo — Output one or more strings(输出一个或者多个字符串) 2、print — Output a string(输出一个字...

31570
来自专栏用户2442861的专栏

剑指offer 33 把数组排成最小的数

转载请注明出处:http://blog.csdn.net/ns_code/article/details/28128551

13420
来自专栏CaiRui

Python之‘’控制流‘’

一、if语句 格式: i1 = 3 if i1 > 4: print('yes you are right') elif 0 < i1 < 4: ...

23790
来自专栏Python小屋

奇怪,Python有的函数调用需要两对括号?(2)

在Python中,允许嵌套定义函数,也就是在一个函数A中可以定义另一个函数B。另外,在Python中,可调用对象可以分为三类:1)函数,2)类,3)含有特殊方法...

34890
来自专栏Python攻城狮

动态语言-Python1.动态语言的定义

动态编程语言是高级程序设计语言的一个类别,在计算机科学领域已被广泛应用。它是一类在运行时可以改变其结构的语言:例如新的函数、对象、甚至代码可以被引进,已有的函数...

8020
来自专栏不想当开发的产品不是好测试

java匿名内部类

show the code : package com.test.jwen.httpApiAuto; public class AInter { publ...

23870
来自专栏和蔼的张星的图像处理专栏

548. 两数组的交 II 排序+双指针

样例 nums1 = [1, 2, 2, 1], nums2 = [2, 2], 返回 [2, 2].

10820
来自专栏老司机的技术博客

golang学习笔记2:基本结构与数据类型

除了以上介绍的这些关键字,Go 语言还有 36 个预定义标识符,其中包含了基本类型的名称和一些基本的内置函数。

11340
来自专栏ml

hdu 3518 (后缀数组)

  题目描述:   找出一个字符串中至少重复出现两次的字串的个数(重复出现时不能重叠)。   code:      后缀数组处理,对于得到height 进行查找...

36540
来自专栏破晓之歌

Typescript入门 原

10250

扫码关注云+社区

领取腾讯云代金券