注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj1798】【Ahoi2009】【维护序列】  

2014-04-30 18:23:47|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:维护一段序列,支持下面三种操作:
   1)数列的一段整体乘以一个数
   2)数列的一段整体加上一个数
   3)询问数列的一段的和 mod P的值。

   0.0线段树直接加标记做就可以了,复习一下线段树的基本操作吧。
   一般遇到多标记的题目都要事先强行规定一个标记下放的顺序,比如先下放乘法再下放加法。0.0这里纠结了一下...然后发现自己果然傻叉了...= =考虑下面有一个节点有 两个标记 a和b分别表示乘法和加法了,那么咱们下放一个乘法标记c,实际上只需要把儿子们的两个标记变成 c*a和c*b即可。然后加法标记c只需要让儿子们的加法标记c即可。
    傻×的没搞清加法标记的下放,连wa三发才发现= =
========================

program bzoj1798;
const maxn=100010;
type node=record
     l,r:longint;
     aa,bb,sum,a,b:int64;
     end;

var t:array[0..maxn shl 3]of node;
    a:array[0..maxn]of int64;
    n,m,tot:longint;
    modd:int64;

function mo(x:int64):int64;
begin
  if x>=modd then x:=x mod modd;
  exit(x);
end;

procedure push(x:longint);
begin
  if t[x].aa<>1 then
   begin
     if t[x].l<>0 then begin
       t[t[x].l].aa:=mo(t[t[x].l].aa*t[x].aa);
       t[t[x].l].bb:=mo(t[t[x].l].bb*t[x].aa);
       t[t[x].l].sum:=mo(t[t[x].l].sum*t[x].aa);
     end;
     if t[x].r<>0 then begin
       t[t[x].r].aa:=mo(t[t[x].r].aa*t[x].aa);
       t[t[x].r].bb:=mo(t[t[x].r].bb*t[x].aa);
       t[t[x].r].sum:=mo(t[t[x].r].sum*t[x].aa);
     end;
     t[x].aa:=1;
   end;
  if t[x].bb<>0 then
   begin
     if t[x].l<>0 then begin
       t[t[x].l].bb:=mo(t[t[x].l].bb+t[x].bb);
       t[t[x].l].sum:=mo(t[t[x].l].sum+(t[t[x].l].b-t[t[x].l].a)*t[x].bb);
     end;
     if t[x].r<>0 then begin
       t[t[x].r].bb:=mo(t[t[x].r].bb+t[x].bb);
       t[t[x].r].sum:=mo(t[t[x].r].sum+(t[t[x].r].b-t[t[x].r].a)*t[x].bb);
     end;
     t[x].bb:=0;
   end;
end;

procedure maintain(x:longint);
begin
  t[x].sum:=mo(t[t[x].l].sum+t[t[x].r].sum);
end;

procedure insert(l,r,x,c:longint;w:int64);
var mid:longint;
begin
  if (t[x].a>=l)and(t[x].b<=r)then
   begin
     if c=0 then
      begin
        t[x].aa:=mo(t[x].aa*w);
        t[x].bb:=mo(t[x].bb*w);
        t[x].sum:=mo(t[x].sum*w);
        push(x);
      end
     else
      begin
        t[x].bb:=mo(t[x].bb+w);
        t[x].sum:=mo(t[x].sum+w*(t[x].b-t[x].a));
        push(x);
      end;
     exit;
   end;
  push(x);
  mid:=(t[x].a+t[x].b)shr 1;
  if mid>l then insert(l,r,t[x].l,c,w);
  if mid<r then insert(l,r,t[x].r,c,w);
  maintain(x);
end;

function query(l,r,x:longint):int64;
var ans:int64;mid:longint;
begin
  if (t[x].a>=l)and(t[x].b<=r)then exit(t[x].sum);
  push(x);
  ans:=0;mid:=(t[x].a+t[x].b)shr 1;
  if mid>l then ans:=mo(ans+query(l,r,t[x].l));
  if mid<r then ans:=mo(ans+query(l,r,t[x].r));
  maintain(x);
  exit(ans);
end;

procedure build(l,r:longint);
var now,mid:longint;
begin
  inc(tot);now:=tot;
  t[now].a:=l;t[now].b:=r;
  t[now].aa:=1;t[now].bb:=0;
  if l+1<r then
   begin
     mid:=(l+r)shr 1;
     t[now].l:=tot+1;build(l,mid);
     t[now].r:=tot+1;build(mid,r);
     maintain(now);
   end
  else t[now].sum:=a[r];
end;

procedure init;
var i,j,u,v:longint;w:int64;
begin
  read(n,modd);
  for i:=1 to n do read(a[i]);
  tot:=0;
  build(0,n);
  read(m);
  for i:=1 to m do
   begin
     read(j);
     if j=1 then
      begin
        read(u,v,w);
        insert(u-1,v,1,0,w);
      end;
     if j=2 then
      begin
        read(u,v,w);
        insert(u-1,v,1,1,w);
      end;
     if j=3 then
      begin
        read(u,v);
        writeln(query(u-1,v,1));
      end;
   end;
end;

begin
  init;
end.

  评论这张
 
阅读(37)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017