（未完待续）

题目链接：Vijos P1448/LibreOJ 10115/TYVJ 1473(Joyoi)/信息学奥赛一本通 T1537。

题目

题目描述

校门外有很多树，学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两种操作：

• $K=1$，读入 $l,r$ 表示在 $l$ 到 $r$ 之间种上一种树，每次操作种的树的种类都不同；
• $K=2$，读入 $l,r$ 表示询问 $l$ 到 $r$ 之间有多少种树。

注意：每个位置都可以重复种树。

题解

思路

两个树状数组就可以解决这道题。

代码

#include<cstdio>
typedef long long ll;
//以上为头文件
const int MAXN=100000+5;//N的最大范围
const int MAXM=100000+5;//M的最大范围
struct TreeArray{//树状数组模板
    #define lowbit(x) ( (x)&( - (x) ) )
    ll n;
    ll unit[MAXN];
    void Update(ll ID,ll val){
        while(ID<=n){
            unit[ID]+=val;
            ID+=lowbit(ID);
        }
        return;
    }
    ll Query(ll x){
        register ll ans=0;
        while(x){
            ans+=unit[x];
            x-=lowbit(x);
        }
        return ans;
    }
    ll Query(ll x,ll y){
        return Query(y)-Query(x-1);
    }
};
ll n,m;
TreeArray T1,T2;//两个树状数组
int main(void){
    register ll i;
    scanf("%lld%lld",&n,&m);
    T1.n=T2.n=n;
    for(i=1;i<=m;++i){
        static ll k,a,b;
        scanf("%lld%lld%lld",&k,&a,&b);
        if(k==1){
            T1.Update(a,1);
            T2.Update(b,1);
        }
        if(k==2)
            printf("%lld\n",T1.Query(b)-T2.Query(a-1));
    }
    return 0;
}