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

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

（题目范围错了，应为：序列长度为10000，询问次数10000）

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
m:=1;
while 1<<m<=n do inc(m);
m:=1<<m-1;

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

for i:=1 to q do
begin
if ord=1 then
begin
change(r+1,-s);
change(l,s);
end
else
begin
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 回复 举报

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

del是存差，（delta）

a,m是线段树

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

a存的是差的平方的or和