JZOJ 4.8 2435——校门外的树【树状数组】

Description

校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……
如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：
K=1，读入l,r表示在l~r之间种上的一种树
K=2，读入l,r表示询问l~r之间能见到多少种树
（l,r>0）

Input

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

Output

对于每个k=2输出一个答案

Sample Input

5 4
1 1 3
2 2 5
1 2 4
2 3 5
Sample Output

1
2
Hint

范围：20%的数据保证，n,m<=100
60%的数据保证，n <=1000,m<=50000
100%的数据保证，n,m<=50000

---

其实可以理解为括号序列，L为“(“,R为”)”
其实就是在这个区间找到多少个左括号，和右括号
假设这时候需要统计的是 5 10之间有多少种树，那么，只要在10之前种的树都是有效的（这时候先不管5的限制），也就是统计左括号的个数，一共是6个，下面加上5个限制，也就是说，在5之前，我们统计一下有多少右括号，也就是能与左括号匹配掉的括号有多少个？换句话说，就是有多少种树被限制了。
所以就是将findl(r)-findr(l-1)求出来

---

代码如下：

var s1,s2: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(s1[i]);
                        inc(i,lowbit(i));
                end;
end;

procedure addr(i:longint);
begin
        while i<=n do
                begin
                        inc(s2[i]);
                        inc(i,lowbit(i));
                end;
end;

function findl(i:longint):longint;
begin
        findl:=0;
        while i>0 do
                begin
                        inc(findl,s1[i]);
                        dec(i,lowbit(i));
                end;
end;

function findr(i:longint):longint;
begin
        findr:=0;
        while i>0 do
                begin
                        inc(findr,s2[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.