[BZOJ1651] [Usaco2006 Feb]Stall Reservations 专用牛棚

本文主要是介绍[BZOJ1651] [Usaco2006 Feb]Stall Reservations 专用牛棚，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=1651

题目大意

给出奶牛运动的时间段,询问同一时间最多的奶牛数

题解

线段树或差分序列

线段树

varx:array[0..3000000,1..4]of longint;i,j,k:longint;n,a,b,m:longint;
function max(a,b:longint):longint;
beginif a>b then exit(a) else exit(b);
end;procedure build(a,l,r:longint);
var mid:longint;
beginx[a,1]:=l; x[a,2]:=r;if l=r then exit;mid:=(l+r)>>1;build(a*2,l,mid);build(a*2+1,mid+1,r);
end;procedure pushdown(a:longint);
beginif x[a,1]=x[a,2] then begin x[a,4]:=0; exit; end;inc(x[a*2,3],x[a,4]); inc(x[a*2,4],x[a,4]);inc(x[a*2+1,3],x[a,4]); inc(x[a*2+1,4],x[a,4]);x[a,4]:=0;
end;procedure update(a,l,r:longint);
var mid:longint;
beginif x[a,4]<>0 then pushdown(a);if (l=x[a,1])and(r=x[a,2]) then begin inc(x[a,3]); inc(x[a,4]); exit; end;mid:=(x[a,1]+x[a,2])>>1;if r<=mid then update(a*2,l,r) elseif l>mid then update(a*2+1,l,r)else begin update(a*2,l,mid); update(a*2+1,mid+1,r); end;x[a,3]:=max(x[a*2,3],x[a*2+1,3]);
end;beginreadln(n);build(1,1,1000000);for i:=1 to n dobeginreadln(a,b);update(1,a,b);end;writeln(x[1,3]);
end.

差分序列

学习了一下~
差分是相邻两个数的差值,序列是所有的差值排成序列
我们考虑区间加上一个相同的数a,[L,R],那么对于差分序列x[l]+a,x[r+1]-a
最后用前缀和判断最大值即可

varsum,x:array[0..1000005]of longint;i,j,k:longint;n,a,b,ans:longint;
beginfillchar(x,sizeof(x),0);fillchar(sum,sizeof(sum),0);readln(n);for i:=1 to n dobeginreadln(a,b);inc(x[a]); dec(x[b+1]);end;ans:=0;for i:=1 to 1000005 dobeginsum[i]:=sum[i-1]+x[i];if ans<sum[i] then ans:=sum[i];end;writeln(ans);
end.