忘了这是第几道“校门外的树”的，翻了下tyvj发现叫这名字的有三道题- -。括号法真是好东西。
一开始搜题目归类想练线段树的，结果看解题发现这题树状数组更好做，其实也是树状数组更容易理解。今天早上物理课就在比划这道题。
写BIT算法的时候犯的错就是忘记给function里的ans清零的- -一开始我看output都差1我还以为是算法错了。
program vijos_p1448;var i,j,m,n,k,a,b,tot,t1,t2,ans:longint; f:array[1..200000,1..2] of integer;function lowbit(x:longint):longint;begin lowbit:=x and (-x);end;procedure add(x,node:longint);begin while x<=n do begin inc(f[x,node]); x:=x+lowbit(x); end;end;function getsum(x,node:longint):longint;var ans:longint;begin ans:=0; while x>0 do begin ans:=ans+f[x,node]; x:=x-lowbit(x); end; exit(ans);end;begin readln(n,m); for i:=1 to m do begin readln(k,a,b); if k=1 then begin inc(tot); add(a,1); add(b,2); end; if k=2 then begin t1:=getsum(a-1,2); t2:=tot-getsum(b,1); ans:=tot-t1-t2; writeln(ans); end; end;end.
测试数据 #0: Accepted, time = 0 ms, mem = 1516 KiB, score = 1
测试数据 #1: Accepted, time = 0 ms, mem = 1516 KiB, score = 1
测试数据 #2: Accepted, time = 29 ms, mem = 1516 KiB, score = 1
测试数据 #3: Accepted, time = 31 ms, mem = 1512 KiB, score = 1
测试数据 #4: Accepted, time = 41 ms, mem = 1516 KiB, score = 1
测试数据 #5: Accepted, time = 100 ms, mem = 1516 KiB, score = 1
测试数据 #6: Accepted, time = 40 ms, mem = 1512 KiB, score = 1
测试数据 #7: Accepted, time = 46 ms, mem = 1516 KiB, score = 1
测试数据 #8: Accepted, time = 62 ms, mem = 1516 KiB, score = 1
测试数据 #9: Accepted, time = 117 ms, mem = 1516 KiB, score = 1
Accepted, time = 466 ms, mem = 1516 KiB, score = 10
后来开始码线段树了，难于理解的是这题要改的是点，而不是段，我的做法是自动吧点x扩充成x~x+1的线段。这写得麻烦的竟然有6个参数肯定有更简单的代码嗯哼=。=而且我也不确定这算不算线段树了总感觉怪怪的，时间效率上貌似稍微差一点，不过差别这么细微忽略好了。
这里犯了个错误就是既然扩充点成线段，那么边界就该是n+1。k=2时getsum中a和b的边界也要改。
咳咳一不小心数组开大了，因为一开始边界问题以为是数组没开大问题…
program vijos_p1448_3;var f:array[1..200000,1..2] of longint; k,a,b,i,n,m,tot,t1,t2,ans:longint;procedure add(p,left,right,x,y,node:longint);var mid:longint;begin if (x=left) and (y=right) then begin inc(f[p,node]); exit; end; mid:=(left+right) div 2; if y<=mid then begin add(2*p,left,mid,x,y,node); f[p,node]:=f[p,node]+1; end else if x>=mid then begin add(2*p+1,mid,right,x,y,node); f[p,node]:=f[p,node]+1; end else begin add(2*p,left,mid,x,mid,node); add(2*p+1,mid,right,mid,y,node); f[p,node]:=f[p,node]+1; end;end;function getsum(p,left,right,x,y,node:longint):longint;var ans,mid:longint;begin if (x=left) and (y=right) then exit(f[p,node]); mid:=(left+right) div 2; if y<=mid then exit(getsum(2*p,left,mid,x,y,node)) else if x>=mid then exit(getsum(2*p+1,mid,right,x,y,node)) else exit(getsum(2*p,left,mid,x,mid,node)+getsum(2*p+1,mid,right,mid,y,node));end;begin readln(n,m); for i:=1 to m do begin readln(k,a,b); if k=1 then begin inc(tot); add(1,1,n+1,a,a+1,1); add(1,1,n+1,b,b+1,2); end; if k=2 then begin t1:=getsum(1,1,n+1,1,a,2); t2:=tot-getsum(1,1,n+1,1,b+1,1); ans:=tot-t1-t2; writeln(ans); end; end;end.
测试数据 #0: Accepted, time = 0 ms, mem = 32048 KiB, score = 1
测试数据 #1: Accepted, time = 0 ms, mem = 32052 KiB, score = 1
测试数据 #2: Accepted, time = 31 ms, mem = 32048 KiB, score = 1
测试数据 #3: Accepted, time = 46 ms, mem = 32048 KiB, score = 1
测试数据 #4: Accepted, time = 62 ms, mem = 32048 KiB, score = 1
测试数据 #5: Accepted, time = 54 ms, mem = 32048 KiB, score = 1
测试数据 #6: Accepted, time = 54 ms, mem = 32048 KiB, score = 1
测试数据 #7: Accepted, time = 78 ms, mem = 32048 KiB, score = 1
测试数据 #8: Accepted, time = 83 ms, mem = 32048 KiB, score = 1
测试数据 #9: Accepted, time = 124 ms, mem = 32048 KiB, score = 1
Accepted, time = 532 ms, mem = 32052 KiB, score = 10