首页 > 代码库 > bzoj1789 AHOI 维护数列（线段树）

bzoj1789 AHOI 维护数列（线段树）

2024-07-07 09:02:39   230人阅读

首先想到线段树，然后刚开始写忽然想到树状数组求和岂不是更快，而且编程复杂度又小，于是把之前写的删掉，写树状数组，写完模版之后忽然发现这题竟然是区间修改！

于是又删掉重写，忽然发现不会处理又加又乘的，果断看题解……

经过几乎两个小时的调试，终于1A。

需要注意的是，一定要让线段树的每一个区间保存的值时刻为正确的，这样才能在调用时直接返回。比如说这道题的change和query操作的最后一句话：

sum:=f(g[k<<1]+g[k<<1+1])

而不是

sum:=f(t[k<<1].sum+t[k<<1+1].sum)

时刻记住这点就ok了。一开始我还以为我的模版记错了呢……

代码：

  1 type node=record
  2      l,r,ti,ad,sum:int64;
  3      end;
  4 var i,n,m,tagtime,tagadd,ch,x,y,c,p:longint;
  5     t:array[0..650000] of node;
  6 function f(x:int64):int64;
  7  begin
  8  f:=x mod p;
  9  end;
 10 function g(k:longint):longint;
 11  begin
 12  with t[k] do
 13   begin
 14   g:=f(f(sum*ti)+f(ad*(r-l+1)));
 15   end;
 16  end;
 17 procedure build(x,y,k:longint);
 18  var mid:longint;
 19  begin
 20  with t[k] do
 21   begin
 22   l:=x;r:=y;ad:=0;ti:=1;
 23   if l=r then begin read(sum);sum:=f(sum);exit;end;
 24   mid:=(l+r)>>1;
 25   build(l,mid,k<<1);
 26   build(mid+1,r,k<<1+1);
 27   sum:=f(t[k<<1].sum+t[k<<1+1].sum);
 28   end;
 29  end;
 30 procedure pushdown(k:longint);
 31  begin
 32  with t[k] do
 33   begin
 34   if ti<>1 then
 35    begin
 36    sum:=f(sum*ti);
 37    t[k<<1].ti:=f(t[k<<1].ti*ti);
 38    t[k<<1].ad:=f(t[k<<1].ad*ti);
 39    t[k<<1+1].ti:=f(t[k<<1+1].ti*ti);
 40    t[k<<1+1].ad:=f(t[k<<1+1].ad*ti);
 41    ti:=1;
 42    end;
 43   if ad<>0 then
 44    begin
 45    sum:=f(sum+ad*(r-l+1));
 46    t[k<<1].ad:=f(t[k<<1].ad+ad);
 47    t[k<<1+1].ad:=f(t[k<<1+1].ad+ad);
 48    ad:=0;
 49    end;
 50   end;
 51  end;
 52 procedure change(x,y,k:longint);
 53  var mid:longint;
 54  begin
 55  with t[k] do
 56   begin
 57   if (l=x) and (r=y) then
 58    begin
 59     ti:=(ti*tagtime) mod p;
 60     ad:=(ad*tagtime+tagadd) mod p;
 61     exit;
 62    end;
 63   pushdown(k);
 64   mid:=(l+r)>>1;
 65   if y<=mid then change(x,y,k<<1)
 66   else if x>mid then change(x,y,k<<1+1)
 67   else
 68    begin
 69    change(x,mid,k<<1);
 70    change(mid+1,y,k<<1+1);
 71    end;
 72   sum:=f(g(k<<1)+g(k<<1+1));
 73   end;
 74  end;
 75 function query(x,y,k:longint):longint;
 76  var mid:longint;
 77  begin
 78  with t[k] do
 79   begin
 80   pushdown(k);
 81   if (l=x) and (r=y) then exit(f(sum));
 82   mid:=(l+r)>>1;
 83   if y<=mid then query:=f(query(x,y,k<<1))
 84   else if x>mid then query:=f(query(x,y,k<<1+1))
 85   else query:=f(f(query(x,mid,k<<1))+f(query(mid+1,y,k<<1+1)));
 86   sum:=f(g(k<<1)+g(k<<1+1));
 87   end;
 88  end;
 89 procedure init;
 90  begin
 91  readln(n,p);
 92  build(1,n,1);
 93  end;
 94 procedure main;
 95  begin
 96  readln(m);
 97  for i:=1 to m do
 98   begin
 99    read(ch);
100    if ch=1 then
101     begin
102     readln(x,y,tagtime);
103     tagadd:=0;
104     change(x,y,1);
105     end
106    else if ch=2 then
107     begin
108     readln(x,y,tagadd);
109     tagtime:=1;
110     change(x,y,1);
111     end
112    else
113     begin
114     readln(x,y);
115     writeln(query(x,y,1));
116     end;
117   end;
118  end;
119 begin
120  init;
121  main;
122 end.
View Code

虽然现在已经12：30了，但我感觉，很开心。做了这道题，值！

 


联系
我们