Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #209 - [UPIT] Splay tree
Ngày: 27-04-2011
Cập nhật: 27-04-2011
Người gửi: technolt
Ngôn ngữ: Pascal
Xem: 904

Điểm: 3.6/5 (13 Phiếu)


{$MODE OBJFPC}
{$M 10000000}
{$R-,Q-}
uses math;
const
  fin='';
  fou='';
  maxn=100111;
 
type
  tnode=^node;
  node=record
    size:longint;
    value,sum:int64;
    setid,setvalue:longint;
    incid:longint;
    incstart,incrate:int64;
    left,right,parent:tnode;
  end;
 
var
  root,nilT:tnode;
  n,nq:longint;
  a:array[1..maxn] of longint;
 
procedure updateset(p:tnode);inline;
begin
  if p=nilT then exit;
  with p^ do
    begin
	  if setid=0 then exit;
      value:=setvalue;
      sum:=size*value;
      if left^.setid<setid then
        begin
          left^.setid:=setid;
          left^.setvalue:=setvalue;
        end;
      if right^.setid<setid then
        begin
          right^.setid:=setid;
          right^.setvalue:=setvalue;
        end;
      setid:=0;
      setvalue:=0;
    end;
end;
 
 
 
procedure updateinc(p:tnode);inline;
  procedure process(q:tnode;var incid_:longint;const incstart_:int64;var incrate_:int64);inline;
  begin
    if q=nilT then exit;
	with q^ do
		if setid<incid then
		  begin
			incid:=max(incid,incid_);
			incstart:=incstart+incstart_;
			incrate:=incrate+incrate_;
		  end
		else
		  begin
			incid:=incid_;
			incstart:=incstart_;
			incrate:=incrate_;
		  end;
  end;
begin
  if p=nilT then exit;
  if p^.incid=0 then exit;
  with p^ do
    begin
      value:=value+incstart+incrate*(left^.size+1);
      sum:=sum+incstart*size+incrate*((int64(size)*(size+1)) shr 1);
      process(left,incid,incstart,incrate);
      process(right,incid,incstart+incrate*(left^.size+1),incrate);
      incid:=0;
      incstart:=0;
      incrate:=0;
    end;
end;
 
procedure updatequery(p:tnode);inline;
begin
  if p=nilT then exit;
  with p^ do
    begin
      if setid=incid then exit
      else if setid<incid then
        begin
          updateset(p);
          updateinc(p);
        end
      else
        begin
          updateinc(p);
          updateset(p);
        end;
    end;
end;
 
procedure update(p:tnode);inline;
begin
  if p=nilT then exit;
  with p^ do
    begin
      size:=left^.size+1+right^.size;  
      updatequery(left);updatequery(right);
      sum:=left^.sum+value+right^.sum;
	end;
  updatequery(p);
end;
 
procedure setlink(x,y:tnode;inleft:boolean);inline;
begin
  if inleft then
    x^.left:=y
  else
    x^.right:=y;
  y^.parent:=x;
end;
 
procedure uptree(x:tnode);inline;
var
  y,z,beta:tnode;
begin
  y:=x^.parent;
  z:=y^.parent;
 
  if y^.left=x then
    begin
      beta:=x^.right;
      setlink(x,y,false);
      setlink(y,beta,true);
    end
  else
    begin
      beta:=x^.left;
      setlink(x,y,true);
      setlink(y,beta,false);
    end;
  setlink(z,x,z^.left=y);
  update(y);
  update(x);
end;
 
procedure splay(x:tnode);inline;
var
  y,z:tnode;
begin
  repeat
    y:=x^.parent;
    if y=nilT then exit;
    z:=y^.parent;
    if z<>nilT then
        if (z^.left=y)=(y^.left=x) then
          uptree(y)
        else
          uptree(x);
        uptree(x);
  until false;
  x^.parent:=nilT;
end;
 
function access(p:tnode;i:longint):tnode;inline;
begin
  while true do
    begin
      updatequery(p);
      if p^.left^.size>=i then p:=p^.left
      else
        begin
          i:=i-p^.left^.size;
          if i=1 then break;
          dec(i);
          p:=p^.right;
        end;
    end;
  splay(p);
  exit(p);
end;
 
function getright(p:tnode):tnode;inline;
  begin
    while p^.right<>nilT do p:=p^.right;
	exit(p);
  end;
 
function join(t1,t2:tnode):tnode;inline;
 
begin
  if t1=nilT then exit(t2);
  if t2=nilT then exit(t1);
  t1:=getright(t1);
  splay(t1);
  setlink(t1,t2,false);
  update(t1);
  exit(t1);
end;
 
procedure split(p:tnode;var t1,t2:tnode;i:longint);inline;
begin
  if i=0 then
    begin
      t1:=nilT;
      t2:=p;
      exit;
    end;
  if i=p^.size then
    begin
      t1:=p;
      t2:=nilT;
      exit;
    end;
  t1:=access(p,i);
  t2:=t1^.right;
  t1^.right:=nilT;
  t2^.parent:=nilT;
  update(t1);
end;
 
function visit_init_tree(l,h:longint):tnode;inline;
  var
    m:longint;
  begin
    if l>h then exit(nilT);
    m:=(l+h) div 2;
    new(result);
    with result^ do
      begin
        left:=visit_init_tree(l,m-1);
        right:=visit_init_tree(m+1,h);
        left^.parent:=result;
        right^.parent:=result;
        value:=a[m];
        sum:=left^.sum+value+right^.sum;
        size:=h-l+1;
        setid:=0;
        setvalue:=0;
        incid:=0;
        incstart:=0;
        incrate:=0;
      end;
  end;
 
procedure init_tree;inline;
 
begin
  new(nilT);
  with nilT^ do
    begin
      left:=nilT;
      right:=nilT;
      parent:=nilT;
      size:=0;
      value:=0;
      sum:=0;
      setid:=0;
      setvalue:=0;
      incid:=0;
      incstart:=0;
      incrate:=0;
    end;
  root:=visit_init_tree(1,n);
  root^.parent:=nilT;
end;
 
procedure print(p:tnode);
  procedure visit(p:tnode);
  begin
    if p=nilT then exit;
    updatequery(p);
    visit(p^.left);
    write(p^.value,' ');
    visit(p^.right);
  end;
begin
  visit(p);
  writeln;
end;
 
procedure printdebug(p:tnode);
  procedure visit(p:tnode);
  begin
    if p=nilT then exit;
    updatequery(p);
    visit(p^.left);
    write(stderr,p^.value,' ');
    visit(p^.right);
  end;
begin
  visit(p);
  writeln(stderr);
end;
 
var
  i,q,x,y,v:longint;
  t1,t2:tnode;
  time:longint;
  buf:array[1..65535] of byte;
 
begin
  assign(input,fin);reset(input);
  assign(output,fou);rewrite(output);
  settextbuf(input,buf);
  readln(n,nq);
  for i:=1 to n do
    read(a[i]);
  init_tree;
  for i:=1 to nq do
    begin
      read(q);
      case q of
        1:
          begin
            read(x,y,v);
            split(root,root,t2,y);
            split(root,root,t1,x-1);
            update(t1);
            t1^.setid:=i;
            t1^.setvalue:=v;
            update(t1);
            root:=join(root,t1);
            root:=join(root,t2);
          end;
        2:
          begin
            read(x,y,v);
            split(root,root,t2,y);
            split(root,root,t1,x-1);
            update(t1);
            t1^.incid:=i;
            t1^.incstart:=0;
            t1^.incrate:=v;
            update(t1);
            root:=join(root,t1);
            root:=join(root,t2);
          end;
        3:
          begin
            read(x,v);
            split(root,root,t2,x-1);
            new(t1);
            with t1^ do
              begin
                left:=nilT;
                right:=nilT;
                parent:=nilT;
                size:=1;
                value:=v;
                sum:=v;
                setid:=0;
                incid:=0;
                incstart:=0;
                incrate:=0;
              end;
            root:=join(root,t1);
            root:=join(root,t2);
          end;
        4:
          begin
            read(x,y);
            split(root,root,t2,y);
            split(root,root,t1,x-1);
            update(t1);
            writeln(t1^.sum);
            root:=join(root,t1);
            root:=join(root,t2);
          end;
      end;
    end;
  close(input);close(output);
end.