开花

开花

Description

　　在遥远的火星上，上面的植物非常奇怪，都是长方形的，每个植物用三个数来描述：左边界L、右边界R以及高度H，如下图所示描述一个植物：L=2,R=5和H=4。
　　
　　
　　每天都有一个新植物长出来，第一天的植物高度为1，后面每天长出的植物比前一天的高1。
　　当一个新植物长出来的时候，跟其他植物的水平线段相交处会长出一朵小花（前提是之前没有长出花朵），如果线段交于端点，是不会长花的。
　　下图为样例1的示意图：
　　

　　给出每天的植物的坐标，计算每天长出多少新花。

Input

　　第一行包含一个整数N(1<=N<=100000)，表示天数。
　　接下来N行，每行两个整数L和R(1<=L<=R<=100000)，表示植物的左右边界。

Output

　　输出每天长出新植物后增加新花的数量。

Sample Input

输入1：

4

1 4

3 7

1 6

2 6

输入2：

5

1 3

3 5

3 9

2 4

3 8

Sample Output

输出1：

0

1

1

2

输出2：

0

0

0

3

2

题目描述

这题应该没必要做再多的解释了吧？

题解

其实，这是一颗线段树，然后我们每次把读入的 l $l$，r$r$这个区间在线段树上加1，但因为植物左右的两端点是不会开花的，于是我们可以只在 l+1 $l+1$和 r−1 $r-1$的区间加1。
不过要判断 l+1>r−1 $l+1>r-1$如果不是就不用在这段区间里加了。
还有一个问题就是要用一个 sum $sum$数组记录下每个点上已有花的数量，因为有花了就不能再长出花来。
最后，只要求出 l $l$和r$r$这两个点经过的线段数量（即为经过的每个区间的和），累加起来，再减去 l $l$,r$r$上已有的花就可以了（即上述的 sum $sum$数组）。
对累加不懂的，可以看下面：（因为线段数要开100000，所以这里我只开了8的大小来做讲解）
样例1：
　
读入：1　4
计算过后……
注意　 l＋１ $l＋１$, r－１ $r－１$

ans=0 $ans=0$
然后把红线经过的所有点的和加起来，就是可以开花的数量，记得要减去 l $l$,r$r$上原来就有的花的数量。
读入：3　7
计算后……

ans=1 $ans=1$
然后，继续……
读入：1　6

ans=1 $ans=1$
读入：2　6

ans=3 $ans=3$,但因为6这个点上有在 5 6 $5~6$上有一朵花，所以 ans−1 $ans-1$。
记得不要忘了减去原有的花。

自认为这次的题解很烂，所以看不懂的话，看标吧。

vara:array[0..100000] of longint;f:array[0..900000] of longint;n,i,j,l,r,ans,s,k,p:longint;
procedure add(x,y,a,b,t:longint);
varmid:longint;
beginif (x=a) and (y=b) thenbegininc(f[t]);exit;end;mid:=(x+y) div 2;if mid>=b then add(x,mid,a,b,t*2) elseif mid<a then add(mid+1,y,a,b,t*2+1) elsebeginadd(x,mid,a,mid,t*2);add(mid+1,y,mid+1,b,t*2+1);end;
end;
procedure get(x,y,i,j,t:longint);
varmid:longint;
beginans:=ans+f[t];if (x=i) and (y=j) then exit;mid:=(x+y) div 2;if mid>=j then get(x,mid,i,j,t*2) elseif mid<i then get(mid+1,y,i,j,t*2+1) elsebeginget(x,mid,i,mid,t*2);get(mid+1,y,mid+1,j,t*2+1);end;
end;
beginreadln(n);for i:=1 to n dobeginreadln(l,r);ans:=0;k:=a[l];p:=a[r];if l+1<=r-1 then add(1,100000,l+1,r-1,1);get(1,100000,l,l,1);a[l]:=ans;get(1,100000,r,r,1);a[r]:=ans-a[l];writeln(ans-k-p);end;
end.