P1230: [Usaco2008 Nov]lites 开关灯

时间:2021-12-12 16:42:31

嗯嗯,这是一道线段树的题,询问区间内亮着的灯的个数,我们可以把区间修改的线段树改一下,原本的求和改成若有奇数次更改则取反(总长度-亮着的灯个数),而判断是否奇数次只要数组加一个delta的值,update的时候delta xor 1 就够了,代码如下。

 type
tpoint=record
l,r,sum,delta,mid:longint;
end;
var n,m,s,e,i,j,c,sum:longint;
tree:array[..] of tpoint;
procedure build(x,l,r:longint);
begin
tree[x].l:=l; tree[x].r:=r; tree[x].sum:=; tree[x].delta:=; tree[x].mid:=(l+r) shr ;
if l>=r then exit;
build(x*,l,(l+r) shr );
build(x*+,((l+r) shr )+,r);
end;
procedure maitain(x:longint);
begin
tree[x].sum:=;
if tree[x].l<tree[x].r then
tree[x].sum:=tree[x*].sum+tree[x*+].sum;
tree[x].sum:=abs(tree[x].delta*(tree[x].r-tree[x].l+)-tree[x].sum);
end;
procedure insert(x:longint);
begin
if (s<=tree[x].l) and (tree[x].r<=e) then tree[x].delta:=tree[x].delta xor
else begin
if s<=tree[x].mid then insert(x*);
if e>tree[x].mid then insert(x*+);
end;
maitain(x);
end;
procedure query(x,add:longint);
begin
if (s<=tree[x].l) and (tree[x].r<=e) then
sum:=sum+abs(add*(tree[x].r-tree[x].l+)-tree[x].sum)
else begin
if s<=tree[x].mid then query(x*,add xor tree[x].delta);
if e>tree[x].mid then query(x*+,add xor tree[x].delta);
end;
end;
begin
readln(n,m);
build(,,n);
for i:= to m do
begin
readln(c,s,e);
sum:=;
if c= then insert()
else begin
query(,);
writeln(sum);
end;
end;
end.

(转载请注明出处:http://www.cnblogs.com/Kalenda/)