[BZOJ1012][JSOI2008]最大数maxnumber

浏览数：34 / 时间：2015年06月09日

Description

　　现在请求你维护一个数列，要求提供以下两种操作： 1、查询操作。语法：Q L 功能：查询当前数列中末尾L个数中的最大的数，并输出这个数的值。限制：L不超过当前数列的长度。 2、插入操作。语法：A n 功能：将n加上t，其中t是最近一次查询操作的答案（如果还未执行过查询操作，则t=0)，并将所得结果对一个固定的常数D取模，将所得答案插入到数列的末尾。限制：n是非负整数并且在长整范围内。注意：初始时数列是空的，没有一个数。

　　好久没做到这么水的题了ww

　　看到题面马上想到其实可以把数列中末尾L个数看成一段区间，根据上面的操作可以得出区间的右端点

　　再根据L推出左端点，A操作相当于一个一个在数列中放数

　　非常裸的线段树一下子就敲起来了。

program bzoj1012;
const maxn=200010;maxm=1000010;
var m,n,i:longint;
    ch:char;
    a:array[-1..maxn]of record x,y:int64;ch:char;end;
    tr:array[-1..maxm]of record l,r:longint;cover:int64;end;
    t,tt:int64;

function max(a,b:int64):int64;
begin
    if a>b then exit(a) else exit(b);
end;

procedure build(p,l,r:longint);
var mid:longint;
begin
    tr[p].l:=l;tr[p].r:=r;tr[p].cover:=0;
    mid:=(l+r) >> 1;
    if l<r then
    begin
        build(p*2,l,mid);
        build(p*2+1,mid+1,r);
    end;
end;

procedure insert(p,loc:longint;x:int64);
var mid:longint;
begin
    if (tr[p].l=loc)and(tr[p].r=loc) then
    begin
        tr[p].cover:=x;
        exit;
    end;
    mid:=(tr[p].l+tr[p].r) >> 1;
    if loc<=mid then insert(p*2,loc,x) else insert(p*2+1,loc,x);
    tr[p].cover:=max(tr[p*2].cover,tr[p*2+1].cover);
end;

function query(p,l,r:longint):longint;
var mid:longint;
begin
    if (tr[p].l=l)and(tr[p].r=r) then exit(tr[p].cover);
    mid:=(tr[p].l+tr[p].r) >> 1;
    if r<=mid then exit(query(p*2,l,r)) else
        if l>mid then exit(query(p*2+1,l,r)) else
            exit(max(query(p*2,l,mid),query(p*2+1,mid+1,r)));
end;

begin
    readln(m,tt);n:=0;
    for i:=1 to m do
    begin
        readln(a[i].ch,ch,a[i].x);
        if a[i].ch=‘A‘ then inc(n) else
        begin
            a[i].x:=n-a[i].x+1;
            a[i].y:=n;
        end;
    end;
    build(1,1,n);
    n:=0;t:=0;
    for i:=1 to m do
    if a[i].ch=‘A‘ then
        begin
                inc(n);
                insert(1,n,(a[i].x+t) mod tt);
        end else
    begin
        t:=query(1,a[i].x,a[i].y);
        writeln(t);
    end;
end.