首先声明我不是牛。。
这个代码复杂度貌似是nlogn,但是用这题的弱数据测,时间比朴素还多,= =
自己写的代码,水平有限。。看看吧
type
node=record
r,p,m:longint;
move:boolean;{区间内的树是否被移动过的标记}
left,right:longint;
end;
var
tree:array[1..30000] of node;
tol,l,i,m,x,y:longint;
procedure buildtree(u:longint);{RT,建树}
begin
if tree[u].r=tree[u].p-1 then
exit;
tree[u].m:=(tree[u].r+tree[u].p) div 2;
tol:=tol+1;
tree[u].left:=tol;
tree[tree[u].left].r:=tree[u].r;
tree[tree[u].left].p:=tree[u].m;
tree[tree[u].left].move:=true;
buildtree(tree[u].left);
tol:=tol+1;
tree[u].right:=tol;
tree[tree[u].right].r:=tree[u].m;
tree[tree[u].right].p:=tree[u].p;
tree[tree[u].right].move:=true;
buildtree(tree[u].right);
end;
procedure modify(u,head,tail:longint);{修改区间move标记}
begin
if not tree[u].move then exit;
if (tree[u].r=head)and(tree[u].p=tail) then
begin
tree[u].move:=false;
exit;
end;
if tree[u].m>=tail then modify(tree[u].left,head,tail)
else
if tree[u].m<=head then modify(tree[u].right,head,tail)
else
begin
modify(tree[u].left,head,tree[u].m);
modify(tree[u].right,tree[u].m,tail);
end;
end;
function ans(u:longint):longint;{最后自底向上进行求值}
begin
if not tree[u].move then exit(0);
if (tree[u].left=0)and(tree[u].right=0) then ans:=1
else
ans:=ans(tree[u].left)+ans(tree[u].right);
end;
begin
assign(input,'schooltree.in');reset(input);
readln(l,m);
tol:=1;
tree[1].r:=0;
tree[1].p:=l+1;
tree[1].move:=true;
buildtree(1);
for i:=1 to m do
begin
readln(x,y);
y:=y+1;
modify(1,x,y);
end;
writeln(ans(1));
end.