原题
题目描述 Description
简单的说,一共N个水果排成一排,切M次,每次切[L,R]区间的所有水果(可能有的水果被重复切),每切完一次输出剩下水果数量.
数据已重新装配,不会出现OLE错误.
时限和数据范围适当修改,避免数据包过大而浪费空间资源.
输入描述 Input Description
第1行共包括2个正整数，分别为N,M.
接下来m行每行两个正整数L,R.
输出描述 Output Description
一共输出M行,每行输出切完之后剩下水果数量.
样例输入 Sample Input
10 3
3 5
2 8
1 5
样例输出 Sample Output
7
3
2
数据范围及提示 Data Size & Hint
30%的数据满足N,M<=5,000
60%的数据满足N,M<=100,000
100% 的数据满足1<=L<=R<=N<=500,000,1<=M<=500,000
题解
很明显的线段树,但我80分tle了很多次,没想到啊25行的线段树还会tle,后来加了个判断机制就AC了.
这道题其实有一个奇技淫巧,就是让整个线段树的初值全部设为0,然后再一个个区间读入,将区间统一赋值成1,最后ans=N-sum[1].
最最关键的,是将set过的区间标记起来,如果标记过,那么就直接跳过,不然就tle了2333.
下面是代码:
var sum,st:array[1..2000000] of int64;
var en:array[1..2000000] of boolean;
var n,m,x,y:int64;
var i:longint;
procedure sett(h,l,r,x,y,num:longint);
var m,p:longint;
begin
p:=0;
if (l>=x)and(r<=y) then begin st[h]:=num;en[h]:=true;exit; end;//标记区间
m:=(l+r)>>1;
if (x<=m)and(not en[h<<1]) then sett(h<<1,l,m,x,y,num);//处理左边区间
if (y>m)and(not en[h<<1+1]) then sett(h<<1+1,m+1,r,x,y,num);//处理右边区间
if en[h<<1] then p:=(m-l+1)*st[h<<1] else p:=sum[h<<1];
if en[h<<1+1] then inc(p,(r-m)*st[h<<1+1]) else inc(p,sum[h<<1+1]);
sum[h]:=p;//每次更新父亲节点的sum值
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
sett(1,1,n,x,y,1);
writeln(n-sum[1]);//奇技淫巧
end;
end.
欢迎转载,若转载请注明出处.