【BZOJ3110】K大数查询（权值线段树套线段树+标记永久化，整体二分）

题意：有N个位置，M个操作。操作有两种，每次操作

如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c

如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。

N,M<=50000,N,M<=50000

a<=b<=N

1操作中abs(c)<=N

2操作中c<=Maxlongint

思路：这道题如果外层是位置的话就需要在外层区间更新并不会写

所以需要外层权值，内层位置

然而常数太渣，BZOJ上过不去

并不想（会）写标记永久化

 var t:array[..]of record

                             l,r:longint;

                             a,s:int64;

                            end;

     op,x,y,z,d:array[..]of longint;

     root:array[..]of longint;

     n,m,up,i,tmp,n1,cnt:longint;

 procedure swap(var x,y:longint);

 var t:longint;

 begin

  t:=x; x:=y; y:=t;

 end;

 function query(l,r,x,y,p:longint):int64;

 var mid,k:longint;

     tmp:int64;

 begin

  if p= then exit();

  mid:=(l+r)>>;

  if (t[p].a>)and(l<r) then

  begin

   tmp:=t[p].a;

   if t[p].l= then begin inc(cnt); t[p].l:=cnt; end;

   k:=t[p].l;

   t[k].a:=t[k].a+tmp;

   t[k].s:=t[k].s+tmp*(mid-l+);

   if t[p].r= then begin inc(cnt); t[p].r:=cnt; end;

   k:=t[p].r;

   t[k].a:=t[k].a+tmp;

   t[k].s:=t[k].s+tmp*(r-mid);

   t[p].a:=;

  end;

  if (l>=x)and(r<=y) then exit(t[p].s);

  query:=;

  if x<=mid then query:=query+query(l,mid,x,y,t[p].l);

  if y>mid then query:=query+query(mid+,r,x,y,t[p].r);

 end;

 procedure update(l,r,x,y:longint;var p:longint);

 var mid,k:longint;

     tmp:int64;

 begin

  if p= then begin inc(cnt); p:=cnt; end;

  mid:=(l+r)>>;

  if (t[p].a>)and(l<r) then

  begin

   tmp:=t[p].a;

   if t[p].l= then begin inc(cnt); t[p].l:=cnt; end;

   k:=t[p].l;

   t[k].a:=t[k].a+tmp;

   t[k].s:=t[k].s+tmp*(mid-l+);

   if t[p].r= then begin inc(cnt); t[p].r:=cnt; end;

   k:=t[p].r;

   t[k].a:=t[k].a+tmp;

   t[k].s:=t[k].s+tmp*(r-mid);

   t[p].a:=;

  end;

  if (l>=x)and(r<=y) then

  begin

   t[p].a:=t[p].a+;

   t[p].s:=t[p].s+r-l+;

   exit;

  end;

  if x<=mid then update(l,mid,x,y,t[p].l);

  if y>mid then update(mid+,r,x,y,t[p].r);

  t[p].s:=t[t[p].l].s+t[t[p].r].s;

 end;

 procedure add(a,b,c:longint);

 var l,r,k,mid:longint;

 begin

  l:=; r:=n+n+; k:=;

  while l<r do

  begin

   mid:=(l+r)>>;

   update(,n,a,b,root[k]);

   if c<=mid then

   begin

    r:=mid; k:=k<<;

   end

    else

    begin

     l:=mid+; k:=(k<<)+;

    end;

  end;

  update(,n,a,b,root[k]);

 end;

 function ask(a,b:longint;c:int64):longint;

 var l,r,mid,k:longint;

     tmp:int64;

 begin

  l:=; r:=n+n+; k:=;

  while l<r do

  begin

   mid:=(l+r)>>;

   tmp:=query(,n,a,b,root[k<<]);

   if tmp>=c then

   begin

    r:=mid; k:=k<<;

   end

    else

    begin

     l:=mid+; k:=(k<<)+;

     c:=c-tmp;

    end;

  end;

  exit(l);

 end;

 begin

  readln(n,m);

  for i:= to m do read(op[i],x[i],y[i],z[i]);

  for i:= to m do

   if op[i]= then add(x[i],y[i],n+-z[i])

    else writeln(n+-ask(x[i],y[i],z[i]));

 end.

2017.3.19

想了想还是学一波奇技淫巧

需要注意的是标记永久化只能用(l=x)and(r=y)的写法写

 var t:array[..]of record

                             l,r:longint;

                             a,s:int64;

                            end;

     op,x,y,z,d:array[..]of longint;

     root:array[..]of longint;

     n,m,up,i,tmp,n1,cnt:longint;

 procedure swap(var x,y:longint);

 var t:longint;

 begin

  t:=x; x:=y; y:=t;

 end;

 procedure pushup(l,r,p:longint);

 begin

  t[p].s:=t[t[p].l].s+t[t[p].r].s+t[p].a*(r-l+);

 end;

 function query(l,r,x,y,p:longint):int64;

 var mid:longint;

     ans:int64;

 begin

  if p= then exit();

  if (l=x)and(r=y) then exit(t[p].s);

  mid:=(l+r)>>;

  query:=;

  ans:=t[p].a*(y-x+);

        if y<=mid then exit(query(l,mid,x,y,t[p].l)+ans)

   else if x>mid then exit(query(mid+,r,x,y,t[p].r)+ans)

   else exit(query(l,mid,x,mid,t[p].l)+query(mid+,r,mid+,y,t[p].r)+ans);

 end;

 procedure update(l,r,x,y:longint;var p:longint);

 var mid,k:longint;

     tmp:int64;

 begin

  if p= then begin inc(cnt); p:=cnt; end;

  mid:=(l+r)>>;

  if (l=x)and(r=y) then

  begin

   t[p].a:=t[p].a+;

   t[p].s:=t[p].s+r-l+;

   exit;

  end;

       if y<=mid then update(l,mid,x,y,t[p].l)

  else if x>mid then update(mid+,r,x,y,t[p].r)

  else

  begin

   update(l,mid,x,mid,t[p].l);

   update(mid+,r,mid+,y,t[p].r);

  end;

  pushup(l,r,p);

 end;

 procedure add(a,b,c:longint);

 var l,r,k,mid:longint;

 begin

  l:=; r:=n+n+; k:=;

  while l<r do

  begin

   mid:=(l+r)>>;

   update(,n,a,b,root[k]);

   if c<=mid then

   begin

    r:=mid; k:=k<<;

   end

    else

    begin

     l:=mid+; k:=(k<<)+;

    end;

  end;

  update(,n,a,b,root[k]);

 end;

 function ask(a,b:longint;c:int64):longint;

 var l,r,mid,k:longint;

     tmp:int64;

 begin

  l:=; r:=n+n+; k:=;

  while l<r do

  begin

   mid:=(l+r)>>;

   tmp:=query(,n,a,b,root[k<<]);

   if tmp>=c then

   begin

    r:=mid; k:=k<<;

   end

    else

    begin

     l:=mid+; k:=(k<<)+;

     c:=c-tmp;

    end;

  end;

  exit(l);

 end;

 begin

  readln(n,m);

  for i:= to m do read(op[i],x[i],y[i],z[i]);

  for i:= to m do

   if op[i]= then add(x[i],y[i],n+-z[i])

    else writeln(n+-ask(x[i],y[i],z[i]));

 end.

整体二分是二分答案，CDQ分治是二分操作序列

比树套树快2倍

 var a,b:array[..]of record

                           l,r,id,op:longint;

                           w:int64;

                          end;

     s1,s2:array[..]of int64;

     flag,ans:array[..]of longint;

     n,m,i,cnt:longint;

 function lowbit(x:longint):longint;

 begin

  exit(x and (-x));

 end;

 procedure add(x,y:longint);

 var i:longint;

 begin

  i:=x;

  while i<=n do

  begin

   s1[i]:=s1[i]+y;

   s2[i]:=s2[i]+y*x;

   i:=i+lowbit(i);

  end;

 end;

 procedure update(a,b,c:longint);

 begin

  add(a,c); add(b+,-c);

 end;

 function query(x:longint):int64;

 var i:longint;

 begin

  i:=x; query:=;

  while i> do

  begin

   query:=query+s1[i]*(x+)-s2[i];

   i:=i-lowbit(i);

  end;

 end;

 function ask(a,b:longint):int64;

 begin

  exit(query(b)-query(a-));

 end;

 procedure solve(x,y,l,r:longint);

 var i,mid,pre,now:longint;

     tmp:int64;

 begin

  if l=r then

  begin

   for i:=x to y do

    if a[i].op= then ans[a[i].id]:=l;

   exit;

  end;

  mid:=(l+r)>>;

  pre:=x; now:=x;

  for i:=x to y do

   if a[i].op= then

   begin

    if a[i].w<=mid then

    begin

     update(a[i].l,a[i].r,);

     flag[i]:=;

     inc(now);

    end

     else flag[i]:=;

   end

    else

    begin

     tmp:=ask(a[i].l,a[i].r);

     if tmp>=a[i].w then

     begin

      inc(now); flag[i]:=;

     end

      else

      begin

       flag[i]:=;

       a[i].w:=a[i].w-tmp;

      end;

    end;

  for i:=x to y do

   if (a[i].op=)and(a[i].w<=mid) then update(a[i].l,a[i].r,-);

  for i:=x to y do

   if flag[i]= then

   begin

    b[now]:=a[i]; inc(now);

   end

    else

    begin

     b[pre]:=a[i]; inc(pre);

    end;

  for i:=x to y do a[i]:=b[i];

  solve(x,pre-,l,mid);

  solve(pre,y,mid+,r);

 end;

 begin

  assign(input,'bzoj3110.in'); reset(input);

  assign(output,'bzoj3110.out'); rewrite(output);

  read(n,m);

  for i:= to m do

  begin

   read(a[i].op,a[i].l,a[i].r,a[i].w);

   if a[i].op= then a[i].w:=n-a[i].w+

    else

    begin

     inc(cnt); a[i].id:=cnt;

    end;

  end;

  solve(,m,,*n+);

  for i:= to cnt do writeln(n-ans[i]+);

  close(input);

  close(output);

 end.

巴特西

【BZOJ3110】K大数查询（权值线段树套线段树+标记永久化，整体二分）

最新文章

热门文章