引用吴豪大牛：

这题看起来和树状数组没什么关系，不过我们通过一定

的转化，可以利用树状数组很好地解决这个问题。

我们不妨把所有线段的端点看成括号序列，即把询问的

区间[lq,rq]看成在横坐标lq处的一个‘[’和rq处的‘]’, 即把插

入的线段[li,ri]看成在横坐标li处的一个‘(’和ri处的‘)’。

稍作分析，我们不难发现，最后的答案等于‘]’左边‘(’

的个数减去‘[’左边‘)’的个数。

那么我们现在做的就是对某个点做修改，对某个前缀求

和。我们就可以很容易想到树状数组的做法：

1.建立两个树状数T1和T2，分别维护‘(’和‘)’。

2.若K=1，读入li,ri，plusT1(li,1)，plusT2(ri,1)。

3.若K=2，读入lq,rq，sumT1(rq-1)-sumT2(lq-1)

万恶的评测机!为什么用write过,writeln不过？

害我白交了4次！！！！！

用的是个极度委琐的线段树,看下面大牛的方法果然神奇

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：50ms

用WritelnAC。。

线段树处女作，以示纪念。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：运行时错误...|错误号: -1073741819

├ 测试数据 10：运行时错误...|错误号: -1073741819

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：80 有效耗时：9ms

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 25ms

├ 测试数据 10：答案正确... 88ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：113ms

为什么我用writeln也秒杀了？

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

用的是树状数组，方法是学习的etfl大牛的方法。。只是记得要用write(sum,' ');不然会显示超时。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 291ms

├ 测试数据 04：答案正确... 478ms

├ 测试数据 05：答案正确... 822ms

├ 测试数据 06：答案正确... 838ms

├ 测试数据 07：答案正确... 853ms

├ 测试数据 08：答案正确... 838ms

├ 测试数据 09：答案正确... 838ms

├ 测试数据 10：答案正确... 869ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：5827ms

Why 耗时如此之长

唉...我实在太菜了.一个垃圾线段树竟然提交了n次.

还是楼下eftl大牛厉害,交上去就秒杀.

Orz eftl大牛.

题目表述的不太清楚，在同一个点可以种多种不同的树。也就是说，这道题的实质是给定一个区间范围，让你求这个区间覆盖的已知的区间数。

fjxmlhx有个经典的括号法：

在插入一个新区间[a,b]时，向a加一个左括号(inc(l[a]))，向b加一个右括号(inc(r[b ]))。

在询问区间[a,b]时，结果就是在b之前(含b)的左括号个数减去在a之前(不含a)的后括号个数，即ans:=l[b ]-l[a-1]

具体实现可以用树状数组或者线段树。要注意用线段树时树表示的区间范围应该是[0,n]，否则会处理询问[1,b]会很麻烦

和评测机关系应该不大吧，在Vivid Puppy测线段树的结果：

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

线段树+括号法

具体题解的话，好像下面有。

当然用树状数组更快,我最近在练习线段树

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

树状数组闪电AC

第一次写线段树，竟然一次ＡＣ．就是有一点不懂，线段树里的每个区间至少是［Ｘ，Ｘ＋１］的，那么怎么在１接点上插入？我是另外用了个变量来存１上的信息的．．

树状数组就是牛！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 134ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 447ms

├ 测试数据 06：答案正确... 541ms

├ 测试数据 07：答案正确... 556ms

├ 测试数据 08：答案正确... 509ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 728ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：2915ms

我怎么这么慢？莫非是因为用流了？

树状数组果然好用……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

我无语啊。。。交了N次才AC。。。

直接用两个树状数组就可以。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

树状数组。

分别记录[1..X]中l和r的个数。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 150ms

├ 测试数据 08：答案正确... 166ms

├ 测试数据 09：答案正确... 134ms

├ 测试数据 10：答案正确... 119ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：569ms

终于碰到tiger...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 88ms

├ 测试数据 10：答案正确... 103ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：263ms

l~r之间，表示的是连续的区间，还是l..r离散的点？