校门外的树

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1125 字

树状数组区间覆盖计数

一本通
例

正文

/*
原题：T1537（4.1 树状数组）校门外种树
题意：道路长 n，m 个操作：K=1 在 [l,r] 种下一种新树（每次种类都不同）；
K=2 询问 [l,r] 之间有多少种树。每个位置可以重复种树。n,m≤5×10^4。
思路：每种树对应一个区间 [L,R]，它与询问 [l,r] 有交集当且仅当 L≤r 且 R≥l。
于是用两个树状数组分别记录各种树的左端点 L 与右端点 R：
答案 = (L≤r 的种类数) − (R<l 的种类数)，即 sumL(r) − sumR(l−1)。
复杂度：时间 O((n+m) log n)，空间 O(n)
易错点：1) 必须同时满足 L≤r 与 R≥l 两个条件，只统计 R≥l 会把左端点太靠右的种类多算进来；
2) 第二项求的是 R<l，对应树状数组前缀查询 sumR(l−1)，是严格小于而非 ≤；
3) 坐标从 1 开始，l−1 可能为 0，前缀和函数要能返回 0。
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN=50005;
struct BIT{
    int t[MAXN];
    void add(int i,int v){
        for(;i<MAXN;i+=i&-i){
            t[i]+=v;
        }
    }
    int sum(int i){
        int s=0;
        for(;i>0;i-=i&-i){
            s+=t[i];
        }
        return s;
    }
};
BIT bitL,bitR;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int k,l,r;
        cin>>k>>l>>r;
        if(k==1){
            // 种下一种新树，记录它的左右端点
            bitL.add(l,1);
            bitR.add(r,1);
        }else{
            int ans=bitL.sum(r)-bitR.sum(l-1);
            cout<<ans<<"\n";
        }
    }
    return 0;
}

校门外的树

正文

一本通·提高篇的其它内容