首页 > 代码库 > 1012: [JSOI2008]最大数maxnumber

1012: [JSOI2008]最大数maxnumber

2024-08-09 02:01:32   211人阅读

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           begin13                x:=x mod p;14                a[0,m+1]:=x;15                for i:=1 to ly do16                    begin17                         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          begin27               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 begin32      readln(n,p);33      m:=0;34      for i:=1 to n do35          begin36               readln(c1,l);37               case upcase(c1) of38                    ‘A‘:add(l+t);39                    ‘Q‘:begin40                             t:=last(l);41                             writeln(t);42                    end;43               end;44          end;45 end.46

 

1012: [JSOI2008]最大数maxnumber


联系
我们