1012: [JSOI2008]最大数maxnumber

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec  Memory Limit: 162 MB

Submit: 4435  Solved: 2000

[Submit][Status]

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

5 100 A 96 Q 1 A 97 Q 1 Q 2

Sample Output

96 93 96

HINT

Source

 题解:额。。这个。。。网上说了好多高端的算法(HansBug:说是线段树嘛,可是怎么加点进去;单调队列嘛,麻烦;树状数组区间最值嘛,不会写 phile:我也是醉了)然后我就想到了《算法导论》上面那个用于静态快速求区间最值的RMQ(可以做到O(nlogn)初始化,O(1)查询),而且这道题要求的是会不停的在序列末尾追加数字,这样子会发现原来的RMQ算法可以加上一个追加数字操作(这算是我自创的么呵呵呵)——当加上新数字后,对于每一级的一维数组都只需要再在后面追加一格就是了,每一级的追加可以类比原有的查询操作。。。然后可以做到修改时O(logn),求值时O(1),总复杂度为O(nlogn+n),n<=200000,看样子有点危险,可是一测还是Accept了。。。

 1 const lx=200000;ly=trunc(ln(lx)/ln(2))+1;
 2 var
 3    i,j,k,l,m,n,p,t:longint;
 4    a:array[0..ly,0..lx] of longint;
 5    c1:char;
 6 function max(x,y:longint):longint;
 7          begin
 8               if x>y then max:=x else max:=y;
 9          end;
10 procedure add(x:longint);
11           var i,j,k:longint;
12           begin
13                x:=x mod p;
14                a[0,m+1]:=x;
15                for i:=1 to ly do
16                    begin
17                         j:=m-trunc(exp(i*ln(2)))+2;
18                         if j<1 then break;
19                         k:=j+trunc(exp((i-1)*ln(2)));
20                         a[i,j]:=max(a[i-1,j],a[i-1,k]);
21                    end;
22                inc(m);
23           end;
24 function last(x:longint):longint;
25          var i:longint;
26          begin
27               if x>m then exit(last(m));
28               i:=trunc(ln(x)/ln(2));
29               last:=max(a[i,m-x+1],a[i,m-trunc(exp(i*ln(2)))+1]);
30          end;
31 begin
32      readln(n,p);
33      m:=0;
34      for i:=1 to n do
35          begin
36               readln(c1,l);
37               case upcase(c1) of
38                    'A':add(l+t);
39                    'Q':begin
40                             t:=last(l);
41                             writeln(t);
42                    end;
43               end;
44          end;
45 end.
46     

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WindCoder

JSON中关于对双向关联的支持

本文原文:Bidirectional Relationship Support in JSON

1732
来自专栏偏前端工程师的驿站

编译期类型检查 in ClojureScript

前言  话说"动态类型一时爽,代码重构火葬场",虽然有很多不同的意见(请参考),但我们看到势头强劲的TypeScript和Flow.js,也能感知到静态类型在某...

1917
来自专栏编码小白

ofbiz实体引擎(七) 检查数据源

/** * Check the datasource to make sure the entity definitions are correct,...

2914
来自专栏Jackson0714

PHP内核之旅-3.变量

2996
来自专栏java学习

面试题51(关于抽象类与接口的掌握)

(单选题)5、A是抽象父类或接口, B , C 派生自 A ,或实现 A ,现在 Java 源代码中有如下声明: 1. A a0=new A(); 2. A...

2814
来自专栏C/C++基础

动态联编实现原理分析

所谓动态联编,是指被调函数入口地址是在运行时、而不是在编译时决定的。C++语言利用动态联编来完成虚函数调用。C++标准并没有规定如何实现动态联编,但大多数的C+...

811
来自专栏步履前行

Java Validation Api

在我们应用程序的业务逻辑中,经常会碰到参数教研的情况,比如在Controller中,我们的参数是一个Entity的时候,经常要判断这个Entity的字段是否是...

3235
来自专栏程序猿DD

JDK 1.5 - 1.8 各版本的新特性总结

此文章意在借鉴前人经验,留作日后查看。如有侵犯,实属无意。我以后会注意,谢谢博友的提醒。也愿各大博友们能够共同学习和努力。

7046
来自专栏搜云库

BTA 常问的 Java基础40道常见面试题及详细答案

最近看到网上流传着,各种面试经验及面试题,往往都是一大堆技术题目贴上去,而没有答案。

5916
来自专栏ImportSource

Java8真不用再搞循环了?

Java8以后真的不用循环了?真的不用了? 好吧,本文分享的内容是java8之前和java8之后一些代码的不同写法,我们会先介绍java8之前和java8之后不...

2.4K11

扫码关注云+社区

领取腾讯云代金券