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天
发表回复