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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1858】【Scoi2010】【序列操作】  

2014-04-09 23:28:07|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   T T卡在hnoi的取石子游戏的证明了...咱先写一道线段树的题目练练手。
   题目大意:给出一个01序列,支持以下操作:
   0 a b :将区间【a,b】的数全变成0
   1 a b :将区间【a,b】的数全变成1
   2 a b :将区间【a,b】的数全部取反
   3 a b :询问【a,b】区间和
   4 a b :询问【a,b】区间最大连续1 
   由于区间没有操作,所以咱们可以考虑线段树。
   0和1操作懒标记。2操作懒标记,3操作开一个sum域。最后一个需要分解区间外加从左到右扫描。
   咱们现在来讨论些细节...
   首先咱们对于每一个区间需要记录一个 lmax,rmax。lmax表示该区间从左边起的1的最长长度,rmax类似。然后咱们分解区间的时候,首先用之前区间合并区间的最大右起和 maxsum+lmax 更新答案,然后设该区间为【l,r】咱们判断lmax=r-l+1,如果是的话说明这一段全是1,咱们贪心的用 maxsum+lmax 更新maxsum,否则咱们用 rmax 更新maxsum。然后递归区间即可...
    然后关于懒标记的处理,0或者1的咱们下放的时候 更新 lmax=rmax=sum=0(懒标记为0),否则lmax=rmax=sum=r-l+1,然后关于取反的标记,貌似为了搞这个...咱们还得记录左起最大0和右起最大0....然后sum变成r-l+1-sum。然后这道题就做完了.....其实还得注意下放的先后顺序,咱是默认的先下放全体赋值再下放取反,如果某一次全体赋值了则把取反改成false。
    突然发现上面傻叉地忘记一种情况...就是在区间内部的...这个需要再开一个maxx...维护类似的。因为这个忽略WA3次..
=====================

program bzoj1858;
const maxn=100010;
type node=record
     lmax,rmax,maxx:array[0..1]of longint;
     sum,a,b,l,r:longint;
     opt:longint;
     opp:boolean;
     end;

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

procedure swap(var a,b:longint);
var t:longint;
begin
  t:=a;a:=b;b:=t;
end;

function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;

procedure maintain(x:longint);
begin
  with t[x] do
   begin
     sum:=t[l].sum+t[r].sum;
     if t[l].sum=0 then lmax[0]:=t[l].b-t[l].a+t[r].lmax[0]
                   else lmax[0]:=t[l].lmax[0];
     if t[l].sum=t[l].b-t[l].a then lmax[1]:=t[l].b-t[l].a+t[r].lmax[1]
                               else lmax[1]:=t[l].lmax[1];
     if t[r].sum=0 then rmax[0]:=t[r].b-t[r].a+t[l].rmax[0]
                   else rmax[0]:=t[r].rmax[0];
     if t[r].sum=t[r].b-t[r].a then rmax[1]:=t[r].b-t[r].a+t[l].rmax[1]
                               else rmax[1]:=t[r].rmax[1];
     maxx[0]:=max(t[l].maxx[0],t[r].maxx[0]);
     maxx[0]:=max(maxx[0],t[l].rmax[0]+t[r].lmax[0]);
     maxx[1]:=max(t[l].maxx[1],t[r].maxx[1]);
     maxx[1]:=max(maxx[1],t[l].rmax[1]+t[r].lmax[1]);
   end;
end;

procedure release(x:longint);
begin
  with t[x] do
   begin
     if opt<>-1 then
      begin
        t[l].opt:=opt;t[r].opt:=opt;
        t[l].opp:=false;t[r].opp:=false;
        t[l].sum:=opt*(t[l].b-t[l].a);
        t[l].lmax[opt]:=t[l].b-t[l].a;
        t[l].rmax[opt]:=t[l].lmax[opt];
        t[l].lmax[opt xor 1]:=0;
        t[l].rmax[opt xor 1]:=0;
        t[r].sum:=opt*(t[r].b-t[r].a);
        t[r].lmax[opt]:=t[r].b-t[r].a;
        t[r].rmax[opt]:=t[r].lmax[opt];
        t[r].lmax[opt xor 1]:=0;
        t[r].rmax[opt xor 1]:=0;
        t[l].maxx[opt]:=t[l].b-t[l].a;
        t[l].maxx[opt xor 1]:=0;
        t[r].maxx[opt]:=t[r].b-t[r].a;
        t[r].maxx[opt xor 1]:=0;
        opt:=-1;
      end;
     if opp then
      begin
        t[l].opp:=not t[l].opp;
        t[r].opp:=not t[r].opp;
        t[l].sum:=t[l].b-t[l].a-t[l].sum;
        t[r].sum:=t[r].b-t[r].a-t[r].sum;
        swap(t[l].lmax[0],t[l].lmax[1]);
        swap(t[l].rmax[0],t[l].rmax[1]);
        swap(t[r].lmax[0],t[r].lmax[1]);
        swap(t[r].rmax[0],t[r].rmax[1]);
        swap(t[l].maxx[0],t[l].maxx[1]);
        swap(t[r].maxx[0],t[r].maxx[1]);
        opp:=false;
      end;
   end;
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].opt:=-1;t[now].opp:=false;
  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
   begin
     t[now].sum:=a[r];
     t[now].lmax[a[r]]:=1;
     t[now].rmax[a[r]]:=1;
     t[now].lmax[a[r] xor 1]:=0;
     t[now].rmax[a[r] xor 1]:=0;
     t[now].maxx[a[r]]:=1;
     t[now].maxx[a[r] xor 1]:=0;
     t[now].l:=0;
     t[now].r:=0;
   end;
end;

procedure get(l,r,c,x:longint);
var mid:longint;
begin
  if (t[x].a>=l)and(t[x].b<=r) then
   begin
    if c<=1 then
     begin
      t[x].opt:=c;
      t[x].opp:=false;
      t[x].sum:=c*(t[x].b-t[x].a);
      t[x].lmax[c]:=t[x].b-t[x].a;
      t[x].rmax[c]:=t[x].lmax[c];
      t[x].lmax[c xor 1]:=0;
      t[x].rmax[c xor 1]:=0;
      t[x].maxx[c]:=t[x].b-t[x].a;
      t[x].maxx[c xor 1]:=0;
      exit;
     end;
    if c=2 then
     begin
       t[x].opp:=not t[x].opp;
       t[x].sum:=t[x].b-t[x].a-t[x].sum;
       swap(t[x].lmax[0],t[x].lmax[1]);
       swap(t[x].rmax[0],t[x].rmax[1]);
       swap(t[x].maxx[0],t[x].maxx[1]);
       exit;
     end;
    if c=3 then
     begin
       ans:=ans+t[x].sum;
       exit;
     end;
    if c=4 then
     begin
       ans:=max(ans,maxlen+t[x].lmax[1]);
       ans:=max(ans,t[x].maxx[1]);
       if t[x].b-t[x].a=t[x].sum then
         maxlen:=maxlen+t[x].sum
       else
         maxlen:=t[x].rmax[1];
       ans:=max(ans,maxlen);
       exit;
     end;
   end;
  release(x);
  mid:=(t[x].a+t[x].b)shr 1;
  if mid>l then get(l,r,c,t[x].l);
  if mid<r then get(l,r,c,t[x].r);
  maintain(x);
end;

procedure init;
var i,ll,rr,op:longint;
begin
  read(n,m);
  for i:=1 to n do
    read(a[i]);
  tot:=0;
  build(0,n);
  for i:=1 to m do
   begin
     read(op,ll,rr);
     inc(ll);inc(rr);
     ans:=0;maxlen:=0;
     get(ll-1,rr,op,1);
     if op>2 then writeln(ans);
   end;
end;

begin
  init;
end.


  评论这张
 
阅读(72)| 评论(2)
推荐 转载

历史上的今天

评论

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

页脚

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