bzoj3489: A simple rmq problem （主席树）

//==========================

蒟蒻Macaulish：http://www.cnblogs.com/Macaulish/ 转载要声明！

//==========================

说好的“因为是OJ上的题，就简单点好了。”呢？

一开始看不懂，不会写。

然后跪了一个晚上决定看云的题解&……似乎是主席树套主席树！吓傻，还开了40000000的数组。然后一交tle……

然后p是不可能玩常数的。

找不到其他做法。

然后找到了神牛dwjshift，好心地提供了题解（http://tieba.baidu.com/p/2947256742#47989538012l ）之后还好心地提供了代码！简直业界良心！（dwj必拿AU）

一开始写的是主席树套配对堆（因为要个优先队列嘛）然后发现套个配对堆各种问题（就不说了，其实主要还是我太弱，这个里面很恶心。。。。。）

然后就跪了dwj的代码，用treap实现。

关于题解，正题开始：

主席树套主席树的做法详见帖子中吧主的话

然后发现没有那么必要。

主席树套优先队列详见帖子下面。

“给定一个序列，支持两个操作： 1.给区间[l,r]中塞进或去掉一个数 2.查询某个点的值”

然后类似标记永久化。就可以变成单点修改的线段树套优先队列了

（原来主席树也是可以区间修改区间查询？……只要套个标记永久化）

写的时候有个地方傻叉了，就是主席树修改的时候，如果区间被要修改的区间覆盖时就不用改他儿子，这时候注意不要忘记儿子们=旧的点的儿子们，要是一开始新的点的儿子都是旧的点的不就行了，这是个人风格问题！）

{$inline on}

const

  maxn=;

  maxm=;

var

  left,right,size,fix,max2,value:array[..maxm]of longint;

  root,lson,rson,max:array[..maxm]of longint;

  time,last,next,num:array[..maxn]of longint;

  n,m,tot1,tot2,ll,rr:longint;

  flag:boolean;

procedure swap(var x,y:longint);inline;

var

  i:longint;

begin

  i:=x;

  x:=y;

  y:=i;

end;

function mmax(x,y:longint):longint;inline;

begin

  if x<y then exit(y);

  exit(x);

end;

procedure update(x:longint);inline;

begin

  max2[x]:=mmax(max2[left[x]],max2[right[x]]);

  if size[x]> then max2[x]:=mmax(max2[x],value[x]);

end;

procedure leftr(var x:longint);inline;

var

  k:longint;

begin

  k:=right[x];

  right[x]:=left[k];

  left[k]:=x;

  max2[k]:=max2[x];

  update(x);

  x:=k;

end;

procedure rightr(var x:longint);inline;

var

  k:longint;

begin

  k:=left[x];

  left[x]:=right[k];

  right[k]:=x;

  max2[k]:=max2[x];

  update(x);

  x:=k;

end;

procedure insert(var x:longint;y:longint);inline;

begin

  if x= then begin

    inc(tot2);

    x:=tot2;

    size[x]:=;

    value[x]:=y;

    fix[x]:=random(maxn);

    max2[x]:=y;

    left[x]:=;

    right[x]:=;

    exit;

  end;

  if value[x]=y then begin

    if flag then inc(size[x])

      else dec(size[x]);

    update(x);

  end

  else

    if value[x]<y then begin

      insert(right[x],y);

      update(x);

      if fix[right[x]]>fix[x] then leftr(x);

    end

    else begin

      insert(left[x],y);

      update(x);

      if fix[left[x]]>fix[x] then rightr(x);

    end;

end;

procedure change(x,old,l,r,y:longint;var new:longint);inline;

var

  mid:longint;

begin

  inc(tot1);

  new:=tot1;

  if (ll<=l) and (r<=rr) then begin

    insert(root[x],y);

    max[new]:=max2[root[x]];

    lson[new]:=lson[old];

    rson[new]:=rson[old];

    exit;

  end;

  max[new]:=max2[root[x]];

  mid:=(l+r)>>;

  if ll>mid then begin

    change(x<<+,rson[old],mid+,r,y,rson[new]);

    lson[new]:=lson[old];

  end

  else

  if rr<=mid then begin

    change(x<<,lson[old],l,mid,y,lson[new]);

    rson[new]:=rson[old];

  end

  else begin

    change(x<<,lson[old],l,mid,y,lson[new]);

    change(x<<+,rson[old],mid+,r,y,rson[new]);

  end;

end;

function query(x,l,r,y:longint):longint;inline;

var

  mid:longint;

begin

  //writeln(x);

  if l=r then exit(max[x]);

  mid:=(l+r)>>;

  if y>mid then exit(mmax(max[x],query(rson[x],mid+,r,y)))

    else exit(mmax(max[x],query(lson[x],l,mid,y)))

end;

procedure into;inline;

var

  i,j:longint;

begin

  readln(n,m);

  for i:= to n do read(num[i]);

  for i:= to n do last[i]:=n+;

  for i:=n downto  do begin

    next[i]:=last[num[i]];

    last[num[i]]:=i;

  end;

  for i:= to n do

    if last[i]<>n+ then begin

      ll:=last[i];

      rr:=next[ll]-;

      flag:=true;

      change(,time[],,n,i,time[]);

    end;

  for i:= to n do begin

    ll:=i-;

    rr:=next[i-]-;

    flag:=false;

    change(,time[i-],,n,num[i-],time[i]);

    if next[i-]<>n+ then begin

      ll:=next[i-];

      rr:=next[ll]-;

      flag:=true;

      change(,time[i],,n,num[i-],time[i]);

    end;

  end;

end;

procedure work;inline;

var

  lastans,l,r:longint;

begin

  lastans:=;

  while m> do begin

   // writeln(m,'===========');

    dec(m);

    readln(l,r);

    l:=(l+lastans) mod n+;

    r:=(r+lastans) mod n+;

    if l>r then swap(l,r);

    lastans:=query(time[l],,n,r);

    writeln(lastans);

  end;

end;

begin

  randomize;

  into;

  work;

end.

巴特西

bzoj3489: A simple rmq problem （主席树）

最新文章

热门文章