花期内花的数目

给你一个下标从 0 开始的二维整数数组 flowers
其中 flowers[i] = [starti, endi] 表示第 i 朵花的花期从 starti 到 endi
同时给你一个下标从 0 开始大小为 n 的整数数组 people ，people[i] 是第 i 个人来看花的时间
请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的数目

1. 合并排序 + 离线查询

插入点和查询点合并

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
        //离线查询，分别标识天数，开花、人、死掉，以及人对应的位置结果标识
        vector<vector<int>> search;
        int curflower = 0;//记录当前花的数目
        for(auto &flower:flowers){
            search.push_back(vector<int>{flower[0],1,-1});
            search.push_back(vector<int>{flower[1],3,-1});
        }
        for(int i=0;i<people.size();i++)
            search.push_back(vector<int>{people[i],2,i});
        sort(search.begin(),search.end(),[&](const vector<int>&a,const vector<int>&b ){
            if(a[0]==b[0])  return a[1]<b[1];
            return a[0]<b[0];
        });
        vector<int> res(people.size());
        for(auto &s:search){
            if(s[1]==1) curflower++;
            if(s[1]==2) res[s[2]] = curflower;
            if(s[1]==3) curflower--;
        }
        return res;
    }
};

2. 不合并排序 + 离线查询

插入点和查询点不合并

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
        //离线查询，分别标识天数，开花、人、死掉，以及人对应的位置结果标识
        vector<vector<int>> search;
        int curflower = 0;//记录当前花的数目
        for(auto &flower:flowers){
            search.push_back(vector<int>{flower[0],1});
            search.push_back(vector<int>{flower[1]+1,-1});
        }
        sort(search.begin(),search.end());
        vector<int> index(people.size());
        iota(index.begin(),index.end(),0);
        sort(index.begin(),index.end(),[&](int a,int b){
            return people[a]<people[b];
        });
        int sidx = 0;
        vector<int> res(people.size());
        for(auto idx:index){
            while(sidx<search.size()&&search[sidx][0]<=people[idx])
                curflower+=search[sidx++][1];
            res[idx] = curflower;
        }
        return res;
    }
};

3. 差分 + 离线查询

本质上是利用红黑树的有序，进行查询

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        map<int, int> cnt;
        for (auto &flower : flowers) {
            cnt[flower[0]]++;
            cnt[flower[1] + 1]--;
        }
        int n = persons.size();
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int a, int b) {
            return persons[a] < persons[b];
        });

        vector<int> ans(n);
        int curr = 0;
        auto it = cnt.begin();
        for (int x : indices) {
            while (it != cnt.end() && it->first <= persons[x]) {
                curr += it->second;
                it++;
            }
            ans[x] = curr;
        }
        return ans;
    }
};

4. 排序 + 二分

直接二分求开花和落花的个数

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>> &flowers, vector<int> &persons) {
        int n = flowers.size();
        vector<int> starts(n), ends(n);
        for (int i = 0; i < n; ++i) {
            starts[i] = flowers[i][0];
            ends[i] = flowers[i][1];
        }
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());
        int m = persons.size();
        vector<int> ans(m);
        for (int i = 0; i < m; ++i) {
            int x = upper_bound(starts.begin(), starts.end(), persons[i]) - starts.begin();
            int y = lower_bound(ends.begin(), ends.end(), persons[i]) - ends.begin();
            ans[i] = x - y;
        }
        return ans;
    }
};

5. 离散化 + 树状数组

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>> &flowers, vector<int> &persons) {
        map<int,int> m;
        //进行离散化
        for(auto &flower:flowers){
            m[flower[0]]++;
            m[flower[1]+1]++;
        }
        for(auto person:persons)
            m[person]++;
        int idx = 1;
        for(auto &[key,val]:m)
            val = idx++;
        //初始化树
        n = m.size();
        tree.resize(n+1,0);
        //对插入点进行插入更新
        
       for(auto &flower:flowers){
            update(m[flower[0]],1);
            update(m[flower[1]+1],-1);
        }
        //进行查询
        for(auto &person:persons)
            person = getsum(m[person]);
        return persons;
    }

    vector<int> tree;
    int n;
    int lowbit(int x){//求二进制化最后一位的值
        return x&(-x);
    }
    void update(int i,int k){ //在i位置加上k，O(logn)复杂度单点修改
        while(i<=n){//更新子树上所有值
            tree[i]+=k;
            i+=lowbit(i);//移动到父亲节点
        }
    }

    long long getsum(int i){  //求数组前i项的和
        long long res=0;
        while(i>0){//O(logn)求前缀和
            res+=tree[i];
            i-=lowbit(i);//移动到前一棵子树（子区间）
        }
        return res;
    }
};