树状数组40行

├ 测试数据 01：答案正确... (0ms, 972KB)

├ 测试数据 02：答案正确... (0ms, 972KB)

├ 测试数据 03：答案正确... (0ms, 972KB)

├ 测试数据 04：答案正确... (0ms, 972KB)

├ 测试数据 05：答案正确... (0ms, 972KB)

├ 测试数据 06：答案正确... (0ms, 972KB)

├ 测试数据 07：答案正确... (465ms, 972KB)

├ 测试数据 08：答案正确... (1184ms, 972KB)

├ 测试数据 09：答案正确... (3325ms, 972KB)

├ 测试数据 10：答案正确... (3325ms, 972KB)

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

Accepted / 100 / 8300ms / 972KB

虽然费时，但是我会告诉你我用的模拟吗？模拟啊！模拟啊！writeln！我本来都以为AC率就这么没了呢！！

线段树解。题目可以理解为求给定区间和多少已知区间相交。那么只需要求出与当前区间不相交的，再减去就好了。具体思路为记录每一个区间的开始点与终端。如果当前区间的终端小于某区间的开始点或当前区间的开始点大于某区间的终端，则该区间与当前区间不相交。

var a:array[0..200000,1..2]{1表示开始点，2表示终端} of longint;

n,m,i,x,y,all,mr,ml,le,ri,k:longint;

Procedure change(l,r,x,pos,num:longint);{记录每一个区间的开始点与终端}

begin

if (pos>r)or(pos=ml then exit(0);

if ml>r then exit(a[x,2]);

le:=searchle(l,(l+r)div 2,2*x);

ri:=searchle((l+r)div 2+1,r,2*x+1);

exit(le+ri);

end;

Function searchri(l,r,x:longint):longint;{寻找右侧不相交区间数}

var le,ri:longint;

begin

if r

OTL 括号法

树状数组无压力的说-_-

编译通过...

├ 测试数据 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 括号法很巧妙