Vijos 1448校门外的树(树状数组与线段树)

Vijos 1448校门外的树

校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……

如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作： K=1，读入l,r表示在l~r之间种上的一种树 K=2，读入l,r表示询问l~r之间能见到多少种树 （l,r>0）

输入 第一行n,m表示道路总长为n，共有m个操作 接下来m行为m个操作

输出 对于每个k=2输出一个答案 样例输入 5 4 1 1 3 2 2 5 1 2 4 2 3 5 样例输出 1 2

括号序列+树状数组

什么是括号序列 下面简单介绍一下（感谢tiger教会我）

假设有一个长度是20的数轴，现在我们要在2 15之间种上一种树，那么我们可以在2处添加一个‘（’,在15的地方添加一个‘）’，这就是简单的括号序列。

如果要统计某个区间树的种类，例如 3 10，我们只需要统计10之前（包括10）有多少个‘（’，统计3之前有多少个‘）’，（不包括3）。

这样光说可能很难理解，下面给一个实例。

左括号和右括号表示的是在这些区间内种上了树。（日，感觉有点像在画大便）

假设这时候需要统计的是 5 10之间有多少种树，那么，只要在10之前种的树都是有效的（这时候先不管5的限制），也就是统计左括号的个数，一共是6个，下面加上5个限制，也就是说，在5之前，我们统计一下有多少右括号，也就是能与左括号匹配掉的括号有多少个？换句话说，就是有多少种树被限制了（自己意会下把，实在是用文字说不出来）；

把程序也拿出来晒晒把（脑残的vijos，用writeln6个点超时，用write过了，还9ms）

program vijos;

var c1,c2:array[0..50000]of longint; n,m:longint;

function lowbit(x:longint):longint; begin

lowbit:=x and (x xor (x-1)); end;

procedure addl(i:longint); begin

while i<=n do begin inc(c1[i]); inc(i,lowbit(i)); end; end;

procedure addr(i:longint); begin

while i<=n do begin inc(c2[i]); inc(i,lowbit(i)); end; end;

function findl(i:longint):longint; begin findl:=0; while i>0 do

begin

inc(findl,c1[i]); dec(i,lowbit(i)); end; end;

function findr(i:longint):longint; begin findr:=0; while i>0 do begin

inc(findr,c2[i]); dec(i,lowbit(i)); end; end;

procedure main; var i,j,d,k,r,l:longint; begin readln(n,m); for i:=1 to m do begin readln(k,l,r); if k=1 then begin addl(l); addr(r); end else begin

write(findl(r)-findr(l-1)); writeln; end;

end; end; begin main; end.

暑假还写了个线段树的 可以比较一下program vijos1448; type rec=record

lcount,rcount,be,en:longint; end;

var tree:array[1..200000]of rec; a:array[1..5000]of longint; n,m:longint;

procedure build(i,l,r:longint); begin

tree[i].be:=l; tree[i].en:=r; if l=r then exit; build(i*2,l,(l+r)div 2); build(i*2+1,((l+r)div 2)+1,r); end;

procedure fix(i,s:longint; ff:boolean); var mid:longint; begin

if ff then inc(tree[i].lcount) else inc(tree[i].rcount); if tree[i].be=tree[i].en then exit; mid:=(tree[i].be+tree[i].en)div 2; if s<=mid then fix(2*i,s,ff) else fix(2*i+1,s,ff); end;

（下面的程序我看都不想看了） procedure find(i,u,v:longint;ff:boolean; var ans:longint); var mid,k1,k2:longint; begin

if (u=tree[i].be)and(tree[i].en=v) then begin

if ff then ans:=tree[i].lcount else ans:=tree[i].rcount; exit; end;

mid:=(tree[i].be+tree[i].en) div 2; if (v<=mid) then find(i*2,u,v,ff,ans) else if u>mid then find(i*2+1,u,v,ff,ans) else begin

find(i*2,u,mid,ff,k1); find(i*2+1,mid+1,v,ff,k2); ans:=k1+k2; end; end;

procedure dushu;

var i,what,u,v,ans,k1,k2:longint; begin readln(n,m); build(1,1,n); for i:=1 to m do begin

readln(what,u,v); if what=1 then begin fix(1,u,true); fix(1,v,false);

end else begin

find(1,1,v,true,k1);

if u>1 then find(1,1,u-1,false,k2) else k2:=0; writeln(k1-k2); end; end; end; begin dushu; end.

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库Vijos 1448校门外的树(树状数组与线段树)在线全文阅读。