bzoj1798: [Ahoi2009]Seq 维护序列seq【线段树】

  • 内容
  • 评论
  • 相关

题目点击这里


嗯,找了道线段树的题目做,发现果然对tag的操作还不是很熟练,还是要弄好这方面的东西,毕竟属于基础内容。

这题就三个操作,都是区间修改区间查询,所以tag是免不了的。观察操作要求发现,一个是区间乘上一个数,一个是区间加上一个数,那么显然就要用两个tag,一个表示要加上的数,一个表示要乘上的数。

那么问题来了,tag的具体维护方法就是个问题了。

t1表示乘的tag,t2表示加的tag,假设原来t1、t2分别为c、d的节点x要进行pushdown,父节点的t1、t2分别为a、b,那么就会变成:

a(cx+d)+b=acx+(ad+b)

嗯,看到这个我想所有人都知道该怎么搞了吧。。。


代码:(关于64位的处理这里没有写好,其实只要把t、tag1、tag2的类型改成int64就不会这么麻烦了)

var
  t,tag1,tag2:array[1..262144] of longint;
  n,m,i,j,k,p,ll,rr:longint;
  q,qq:int64;
procedure build(l,r,x:longint);
var
  m:longint;
begin
  tag1[x]:=1;
  if l=r then
  begin
    read(t[x]);
    exit;
  end;
  m:=(l+r) shr 1;
  build(l,m,x shl 1);
  build(m+1,r,x shl 1 or 1);
  t[x]:=(t[x shl 1]+t[x shl 1 or 1]) mod p;
end;
procedure downdate(l,r,x,t1,t2:longint);
begin
  q:=t[x];
  qq:=t2;
  q:=(q*t1+qq*(r-l+1)) mod p;
  t[x]:=q;
  q:=tag1[x];
  q:=q*t1 mod p;
  tag1[x]:=q;
  q:=t1;
  q:=(q*tag2[x]+t2) mod p;
  tag2[x]:=q;
end;
procedure down(l,r,x:longint);
var
  m:longint;
begin
  if (tag1[x]=1) and (tag2[x]=0) then exit;
  m:=(l+r) shr 1;
  downdate(l,m,x shl 1,tag1[x],tag2[x]);
  downdate(m+1,r,x shl 1 or 1,tag1[x],tag2[x]);
  tag1[x]:=1;
  tag2[x]:=0;
end;
procedure change1(l,r,x:longint);
var
  m:longint;
begin
  if (l>=ll) and (r<=rr) then
  begin
    q:=t[x];
    q:=q*i mod p;
    t[x]:=q;
    q:=tag2[x];
    q:=q*i mod p;
    tag2[x]:=q;
    q:=tag1[x];
    q:=q*i mod p;
    tag1[x]:=q;
    exit;
  end;
  down(l,r,x);
  m:=(l+r) shr 1;
  if m>=ll then change1(l,m,x shl 1);
  if m<rr then change1(m+1,r,x shl 1 or 1);
  t[x]:=(t[x shl 1]+t[x shl 1 or 1]) mod p;
end;
procedure change2(l,r,x:longint);
var
  m:longint;
begin
  if (l>=ll) and (r<=rr) then
  begin
    q:=i;
    q:=(q*(r-l+1)+t[x]) mod p;
    t[x]:=q;
    tag2[x]:=(tag2[x]+i) mod p;
    exit;
  end;
  down(l,r,x);
  m:=(l+r) shr 1;
  if m>=ll then change2(l,m,x shl 1);
  if m<rr then change2(m+1,r,x shl 1 or 1);
  t[x]:=(t[x shl 1]+t[x shl 1 or 1]) mod p;
end;
function query(l,r,x:longint):longint;
var
  m,ans:longint;
begin
  if (l>=ll) and (r<=rr) then
  exit(t[x]);
  down(l,r,x);
  m:=(l+r) shr 1;
  ans:=0;
  if m>=ll then ans:=(ans+query(l,m,x shl 1)) mod p;
  if m<rr then ans:=(ans+query(m+1,r,x shl 1 or 1)) mod p;
  exit(ans);
end;
procedure update(l,r,x:longint);
var
  m:longint;
begin
  if l=r then exit;
  down(l,r,x);
  m:=(l+r) shr 1;
  update(l,m,x shl 1);
  update(m+1,r,x shl 1 or 1);
  t[x]:=(t[x shl 1]+t[x shl 1 or 1]) mod p;
end;
begin
  read(n,p);
  build(1,n,1);
  read(m);
  repeat
    read(k);
    dec(m);
    if k=1 then
    begin
      read(ll,rr,i);
      change1(1,n,1);
    end;
    if k=2 then
    begin
      read(ll,rr,i);
      change2(1,n,1);
    end;
    if k=3 then
    begin
      read(ll,rr);
      writeln(query(1,n,1));
    end;
  until m=0;
end.

退役倒计时:25天

评论

0条评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.