PEL比赛的4 T2-----LJJ受罚 题解

回复帖子

@kczno1 2016-10-05 19:15 回复

由于难掩激动之情,又没有题解区,就在这里发了

虽然eden的方法也挺好的,但我的算法根本不用常数优化,而且最慢的也只有100ms

(题目范围错了,应为:序列长度为10000,询问次数10000)

思路就是用两个指针l,r,

用贪心的思想,在满足条件情况下,l一定时r尽量右;r一定时l尽量左;不断右移,O(n)解决。

然而这题不是要求区间和之类的,是or的和,这就麻烦了。

一开始想用一个数组记录每一二进制位的出现的个数,然而这样时间就要*log(数的范围),只拿了25分(特判小长度优化后45)

后来想到用线段树,用贪心的思想去尽量移动,可见程序。

var
 a,max:array[0..30010] of longint;
 del:array[0..10010] of longint;
 n,q,i,j,k,x,x0,ord,l,r,s,m:longint;
 now,ans:longint;

procedure chmin(var x:longint;y:longint);
begin
    if x>y then x:=y;
end;
procedure chmax(var x:longint;y:longint);
begin
 if x<y then x:=y;
end;
function da(x,y:longint):longint;
begin
 if x>y then exit(x);
 exit(y);
end;

procedure change(x,w:longint);
begin
 inc(del[x],w);

 a[x+m]:=sqr(del[x]);
 x:=x+m;
 while x>1 do
 begin
  x:=x>>1;a[x]:=a[x<<1] or a[x<<1+1];
 end;

 max[x+m]:=a[x+m];
 x:=x+m;
 while x>1 do
 begin
  x:=x>>1;max[x]:=da(max[x<<1],max[x<<1+1]);
 end;
end;

procedure fr;
begin
 now:=a[l];r:=l;
 if now>s then exit;
 repeat
  while r and 1=1 do r:=r>>1;
  if r=0 then exit;
  if a[r xor 1] or now>s then
  begin
   r:=r xor 1;break;
  end;
  now:=a[r xor 1] or now;r:=r>>1;
 until false;

 while r<=m do
 begin
  if a[r<<1] or now>s then r:=r<<1
  else
  begin
   now:=a[r<<1] or now;
   r:=r<<1+1;
  end;
 end;
 now:=now or a[r];
end;

procedure fl;
begin
 l:=r;now:=a[r];
 if now>s then exit;
 repeat
  while l and 1=0 do l:=l>>1;
  if l=1 then exit;
  if a[l xor 1] or now>s then
  begin
   l:=l xor 1;break;
  end;
  now:=a[l xor 1] or now;l:=l>>1;
 until false;

 while l<=m do
 begin
  if a[l<<1+1] or now>s then l:=l<<1+1
  else
  begin
   now:=a[l<<1+1] or now;
   l:=l<<1;
  end;
 end;
 now:=now or a[l];
end;

begin 
 readln(n,q);
  m:=1;
 while 1<<m<=n do inc(m);
 m:=1<<m-1;

 read(x0);
 for i:=2 to n do
 begin
  read(x);
  change(i,x-x0);
  x0:=x;
 end;

 for i:=1 to q do
 begin
  read(ord);
  if ord=1 then
  begin
   readln(l,r,s);
   change(r+1,-s);
   change(l,s);
  end
  else
  begin
   read(s);
   if a[1]<=s then writeln(-1)
   else
   if max[1]>s then writeln(2)
   else 
   begin
    l:=2+m;fr;ans:=1<<30;

    repeat
     fl;
     chmin(ans,r-l+2);
     inc(l);
     fr;
    until now<=s;

    writeln(ans);
   end;
  end;
 end;
end.
@kczno1 2016-10-05 19:17 回复 举报

也就是所谓zkw线段树(其实我没学过,只是凭自己的理解)

@kczno1 2016-10-05 19:24 回复 举报

del是存差,(delta)

a,m是线段树

max存的区间是最大的差的平方,用来特判答案长度为2的,不然两个指针一次移动一个就慢了

a存的是差的平方的or和

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。