1012: [JSOI2008]最大数maxnumber
Time Limit: 3 Sec Memory Limit: 162 MBSubmit: 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
A 96
Q 1
A 97
Q 1
Q 2
Sample Output
96
93
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.
评论 (0)
