Vijos1448校门外的树(树状数组与线段树).doc

Vijos 1448校门外的树 校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的…… 如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作： K=1，读入l,r表示在l~r之间种上的一种树 K=2，读入l,r表示询问l~r之间能见到多少种树 （l,r0） 输入 第一行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 i0 do ????? begin ??????? inc(findl,c1[i]); ??????? dec(i,lowbit(i)); ????? end; ? end; function findr(i:longint):longint; ? begin ??? findr:=0; ??? while i0 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 lo