这题看起来和树状数组没什么关系，不过我们通过一定的转化，可以利用树状数组很好地解决这个问题。

我们不妨把所有线段的端点看成括号序列，即把询问的区间[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)-sumT2(lq-1)

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

括号法AC，编的很烂，没有什么优化……不过AC就好

还问一下，限时不是1s么，不应该早超时了么？……

为什么我就用了一个树状数组?

program tree;

var

c:array[1..50000]of longint;

i,j,k,l,n,m:longint;

procedure add(k,p:longint);

var

t:longint;

begin

t:=p;

while t0 do

begin

inc(getsum,c[t]);

t:=t-t and(-t);

end;

end;

procedure deal(j:longint);

var l,r,a,b,t,a1,b1,t1:longint;

begin

if j=1 then

begin

readln(l,r);

add(1,l);

add(50001,r);

end;

if j=2 then

begin

readln(l,r);

a:=getsum(l-1);b:=getsum(r);t:=getsum(n);

a1:=a mod 50001-a div 50001;b1:=(t-b) div 50001-(t-b) mod 50001;

t1:=(b-a)-a1*50001-b1;

writeln(t1 div 50002+a1+b1);

end;

end;

begin

readln(n,m);

for i:=1 to m do

begin

read(j);

deal(j);

end;

end.

又写了个线段树之后我就知道我有多么弱了

5次WA,最后发现查询的时候边界问题

同意楼下，我一开始也意味要拔了重种..

看错题目，以为后种的树会覆盖掉前面的，于是线段树，pass括号法……

发现自己沙茶了，可写了好一会的线段树也舍不得删啊，改之……

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

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

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

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

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

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

比较慢额……

program Project1;

var c,d:array[0..50000] of longint;

i,k,n,m,cc,st,en,ansa,ansb:longint;

begin

readln(n,m);

for i:=1 to m do

begin

readln(cc,st,en);

if cc=1 then

begin

k:=st;

while k0 do

begin

inc(ansb,d[k]);

dec(k,k and (-k));

end;

writeln(ansa-ansb);

end;

end;

end.

为什么wa了3个？

树状数组好牛B的样子，咱看了论文再来AC

编译通过...

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

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

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

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

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

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

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

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

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

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

program p1448;

var

n,m,a,b,k,i:longint;

x,y:array [1..50000] of longint;

function low(x:longint):longint;

begin

low:=x and (x xor (x-1));

end;

procedure work(a:longint);

begin

while a0 do

begin

t:=t+y[a];

dec(a,low(a));

end;

out2:=t;

end;

begin

readln(n,m);

for i:=1 to m do

begin

readln(k,a,b);

if k=1 then begin

work(a);

work2(b);

end;

if k=2 then

writeln(out1(b)-out2(a-1));

end;

end.

贴一个树状数组吧

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

树状数组

佩服佩服

纯模拟都能过.....

Easy无敌！！！

By fjxmlhx

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

在l处添加一个左括号，在y处添加一个右括号。

ans=1~r的左括号-1~l-1的右括号

my boss

我交了7遍还没过....我拿别人过的程序去...还是没过.....这就是Sunny的杯具了....内牛满面....

中午碰上Conan...线段树、树状数组都过了！！！感动...

失败的我做着简单的题

纪念我的第214题！！！！！！！！

（路人甲：214有什么好纪念的……）

（我：因为2.14是人类一个伟大的节日啊。）

正题：

感谢楼下的大牛们。

算法：2*树状数组+括号法。

细节：用write。

核心代码：…………………………

树状数组都快忘光了...

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

今天收获真大！刚学了线段树，又在这里学了树状数组~~

极力推荐这个演示文稿！

http://home.ustc.edu.cn/~zhuhcheng/ACM/tree.ppt

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

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

树状数组秒杀 and 看不懂题意 and 括号法很巧妙

编译通过...

编译通过...

├ 测试数据 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

上午一直在研究.....研究了位运算（诶 没办法 谁让这个算法用到位运算呢..）...研究了值怎么修改...研究了是什么原理...研究到我想吃饭去.....

呜呜%>_