JSOI2008最大数

4
2
2015

1012: [JSOI2008]最大数maxnumber

Time Limit: 3 Sec Memory Limit: 162 MB
Submit: 4808 Solved: 2174
[Submit][Status][Discuss]

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

RunID	User	Problem	Result	Memory	Time	Language	Code_Length	Submit_Time
916445	Chuck__	1012	Accepted	9788 kb	1740 ms	Pascal/Edit	2032 B	2015-04-02 18:44:39

太没用了= =这么渣渣的题花了我将近一个星期（当然中间学了些别的），最后还是和同学一起打对拍，查出的错。

感谢LYS

这题各种乱搞吧= =据说单调栈也行？

反正我开了1..m的一个线段树。。

废话不说了，上代码、

uses
    math;
type
    ll=longint;
    tnode=record
                l,r,maxn:longint;
    end;
var
   tree:array[0..200020*4] of tnode;
   i,tot,t,num,m,d:longint;
   op:char;
 
procedure build(x,l,r:ll);
var
   mid:ll;
begin
     tree[x].l:=l;
     tree[x].r:=r;
     tree[x].maxn:=0;
     if l <> r then
     begin
          mid:=l+(r-l)>>1;
          build(x*2,l,mid);
          build(x*2+1,mid+1,r);
     end;
end;
 
procedure add(x,l,r,p,v:ll);
var
   mid:ll;
begin
     if (l = r) and (tree[x].maxn = 0)
     then begin
          inc(tree[x].maxn,v);
          exit;
     end
     else begin
          mid:=(l+r)>>1;
          if p<=mid
             then add(x*2,l,mid,p,v)
             else add(x*2+1,mid+1,r,p,v);
          end;
     if tree[x*2].maxn>tree[x*2+1].maxn
        then tree[x].maxn:=tree[x*2].maxn
        else tree[x].maxn:=tree[x*2+1].maxn;
end;
 
function query(x,l,r:ll):ll;
var
   mid:ll;
begin
     if (l=tree[x].l)and(r=tree[x].r)
        then exit(tree[x].maxn);
     mid:=(tree[x].l+tree[x].r)>>1;
     if r<=mid
        then exit(query(x*2,l,r))
        else if l>mid
                then exit(query(x*2+1,l,r))
                else exit(max(query(x*2,l,mid),query(x*2+1,mid+1,r)));
end;
begin
     {assign(input,'bzoj1012.in');
     assign(output,'bzoj1012.out');
     reset(input);
     rewrite(output);}
     readln(m,d);
     build(1,1,m);
     tot:=0;
     t:=0;
     for i:=1 to m do
     begin
          readln(op,num);
          if op = 'A' then
          begin
               inc(tot);
               add(1,1,m,tot,(num+t)mod d);
          end;
          if op = 'Q' then
          begin
               t:=query(1,tot-num+1,tot);
               writeln(t);
          end;
     end;
     {close(input);
     close(output);}
end.

Category: 日题 | Tags: | Read Count: 518

二月
日	一	二	三	四	五	六
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28

温存's Blog

合肥，高一，OI。