思路与证明

把每个细菌看成平面上的点 $(l_i,r_i)$。一个查询 $[l,r]$ 的条件是 $l_i\ge l$ 且 $r_i\le r$，等价于统计矩形 $[l,+\infty)\times(-\infty,r]$ 中的点数。这是典型的二维偏序计数。

离线做法：

1. 将所有细菌按 $r_i$ 升序排序；将所有查询按 $r$ 升序排序。

2. 依次处理查询的 $r$，把所有满足 $r_i\le r$ 的细菌“加入”数据结构。

3. 数据结构只按 $l_i$ 这一维统计：我们想要的是“当前已加入的点里，$l_i\ge l$ 的数量”。

   • 对 $l_i$ 做坐标压缩，使用树状数组按 $l_i$ 的位置加一。
   • 设当前已加入的细菌数为 $k$，查询位置 $l$ 的下标为$idx=\mathrm{lower_bound}(L, l)$（$L$ 是去重排好序的所有 $l_i$）， 则答案为 $\text{ans}=k-\text{BIT.sum}(idx-1)$ 其中$\text{BIT.sum}(x)$ 表示压缩坐标 $\le x$ 的前缀和。

4. 复杂度：排序代价 $O(n\log n + m\log m)$，每次加入与查询各为$O(\log n)$，总复杂度为$O((n+m)\log n)$，空间$O(n)$。

C++

#include <bits/stdc++.h>
using namespace std;

// 树状数组（Fenwick）
struct BIT {
    int n;
    vector<int> t;
    BIT(int n=0): n(n), t(n+1, 0) {}
    void add(int i, int v) {
        for (; i <= n; i += i & -i) t[i] += v;
    }
    int sum(int i) const {
        int s = 0;
        for (; i > 0; i -= i & -i) s += t[i];
        return s;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<int> li(n), ri(n);
    vector<int> allL; allL.reserve(n);
    for (int i = 0; i < n; ++i) {
        cin >> li[i] >> ri[i];
        allL.push_back(li[i]);
    }

    // 坐标压缩：只需要压缩所有 l_i
    sort(allL.begin(), allL.end());
    allL.erase(unique(allL.begin(), allL.end()), allL.end());
    auto getPos = [&](int x) {
        return int(lower_bound(allL.begin(), allL.end(), x) - allL.begin()) + 1; // 1-based
    };

    // 将细菌转成 (r_i, pos(l_i)) 并按 r_i 升序
    vector<pair<int,int>> items; items.reserve(n);
    for (int i = 0; i < n; ++i) {
        items.emplace_back(ri[i], getPos(li[i]));
    }
    sort(items.begin(), items.end()); // 按 r_i 升序

    // 读入查询并按 r 升序处理
    struct Query {int l, r, id;};
    vector<Query> qs(m);
    for (int i = 0; i < m; ++i) {
        cin >> qs[i].l >> qs[i].r;
        qs[i].id = i;
    }
    sort(qs.begin(), qs.end(), [](const Query& a, const Query& b){
        return a.r < b.r;
    });

    BIT bit((int)allL.size());
    vector<long long> ans(m, 0);
    int ptr = 0; // 指向 items
    for (auto &q : qs) {
        // 把所有 r_i <= q.r 的细菌加入
        while (ptr < n && items[ptr].first <= q.r) {
            bit.add(items[ptr].second, 1);
            ++ptr;
        }
        // 需要统计 l_i >= q.l 的数量
        int idx = int(lower_bound(allL.begin(), allL.end(), q.l) - allL.begin()) + 1; // 可能为 size+1
        if (idx > (int)allL.size()) {
            ans[q.id] = 0; // 所有 l_i < q.l
        } else {
            // 已加总数为 ptr
            ans[q.id] = ptr - bit.sum(idx - 1);
        }
    }

    for (int i = 0; i < m; ++i) {
        cout << ans[i] << "\n";
    }
    return 0;
}

Python

import sys
from bisect import bisect_left

data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)

n = next(it); m = next(it)

li = [0]*n
ri = [0]*n
allL = []
for i in range(n):
    l = next(it); r = next(it)
    li[i] = l; ri[i] = r
    allL.append(l)

# 坐标压缩（仅 l_i）
allL.sort()
# 去重
uniq = [allL[0]]
for x in allL[1:]:
    if x != uniq[-1]:
        uniq.append(x)

def get_pos(x):
    # 1-based
    return bisect_left(uniq, x) + 1

# items: (r_i, pos(l_i)) 按 r_i 升序
items = sorted((ri[i], get_pos(li[i])) for i in range(n))

# 读取查询并按 r 升序
qs = []
for i in range(m):
    l = next(it); r = next(it)
    qs.append((l, r, i))
qs.sort(key=lambda x: x[1])

# Fenwick
size = len(uniq)
bit = [0]*(size+1)

def add(i, v=1):
    while i <= size:
        bit[i] += v
        i += i & -i

def sum_(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

ans = [0]*m
ptr = 0
for l, r, idx in qs:
    while ptr < n and items[ptr][0] <= r:
        add(items[ptr][1], 1)
        ptr += 1
    pos = bisect_left(uniq, l) + 1
    if pos > size:
        ans[idx] = 0
    else:
        ans[idx] = ptr - sum_(pos-1)

print("\n".join(map(str, ans)))

Java

import java.io.*;
import java.util.*;

public class Main {

    // 快速读入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' ');
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') {
                x = x * 10 + (c - '0');
                c = read();
            }
            return x * sgn;
        }
    }

    // 树状数组
    static class BIT {
        int n;
        int[] t;
        BIT(int n) { this.n = n; this.t = new int[n+1]; }
        void add(int i, int v) {
            for (; i <= n; i += i & -i) t[i] += v;
        }
        int sum(int i) {
            int s = 0;
            for (; i > 0; i -= i & -i) s += t[i];
            return s;
        }
    }

    // 二分：lower_bound
    static int lowerBound(int[] a, int len, int x) {
        int l = 0, r = len; // [l,r)
        while (l < r) {
            int mid = (l + r) >>> 1;
            if (a[mid] < x) l = mid + 1;
            else r = mid;
        }
        return l;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt(), m = fs.nextInt();

        int[] li = new int[n];
        int[] ri = new int[n];
        int[] lvals = new int[n];
        for (int i = 0; i < n; i++) {
            li[i] = fs.nextInt();
            ri[i] = fs.nextInt();
            lvals[i] = li[i];
        }

        // 坐标压缩（仅 l_i）
        Arrays.sort(lvals);
        int[] uniq = new int[n];
        int u = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0 || lvals[i] != lvals[i-1]) uniq[u++] = lvals[i];
        }

        int[] pos = new int[n]; // 每个 i 的 l_i 的压缩位置（1-based）
        for (int i = 0; i < n; i++) {
            pos[i] = lowerBound(uniq, u, li[i]) + 1;
        }

        // items 按 r_i 升序的下标序列
        Integer[] ord = new Integer[n];
        for (int i = 0; i < n; i++) ord[i] = i;
        Arrays.sort(ord, Comparator.comparingInt(i -> ri[i]));

        // 查询
        int[] ql = new int[m], qr = new int[m];
        Integer[] qid = new Integer[m];
        for (int i = 0; i < m; i++) {
            ql[i] = fs.nextInt();
            qr[i] = fs.nextInt();
            qid[i] = i;
        }
        Arrays.sort(qid, Comparator.comparingInt(i -> qr[i]));

        BIT bit = new BIT(u);
        int ptr = 0;
        long[] ans = new long[m];
        for (int qi : qid) {
            int R = qr[qi];
            // 加入所有 r_i <= R 的细菌
            while (ptr < n && ri[ord[ptr]] <= R) {
                bit.add(pos[ord[ptr]], 1);
                ptr++;
            }
            int L = ql[qi];
            int idx = lowerBound(uniq, u, L) + 1; // 可能为 u+1
            if (idx > u) ans[qi] = 0;
            else ans[qi] = ptr - bit.sum(idx - 1);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) sb.append(ans[i]).append('\n');
        System.out.print(sb.toString());
    }
}

题目内容

小C 在实验室中培育了 $n$ 个细菌。

第 $i$ 个细菌的生命周期用一个闭区间 $[l_i,r_i]$ 表示。

现有 $m$ 次查询，每次查询给出一个时间区间 $[l,r]$ 。

对于每次查询，请计算生命周期完全位于该区间内即 $(l ≦l_i$ 且 $r_i ≦r)$ 的细菌数量。

输入描述

第一行输入两个整数 $n$ 和 $m(1≦n,m ≦5×10^5)$ ，分别表示细菌的数量和查询次数。

接下来 $n$ 行，每行输入两个整数 $l_i$ 和 $r_i(1≦l_i≦r_i≦ 10^9)$ ，表示第 $i$ 个细菌的生命周期区间。

随后 $m$ 行，每行输入两个整数 $l$ 和 $r(1 ≦l≦r≦ 10^9)$ ，表示一次查询的时间区间。

输出描述

输出 $m$ 行，每行输出一个整数，表示对应查询的答案。

样例1

输入

5 3
1 2
2 5
3 4
1 10
6 8
1 5
2 6
1 10

输出

3
2
5

说明

• 共有 $5$ 个细菌，其生命周期区间分别为：

  • 第 $1$ 个：$[1,2]$ ；
  • 第 $2$ 个：$[2,5]$ ；
  • 第 $3$ 个：$[3,4]$ ；
  • 第 $4$ 个：$[1,10]$ ；
  • 第 $5$ 个：$[6,8]$ 。

• 查询区间 $[1,5]$ 时，有 $3$ 个细菌(第 $1、2、3$ ) 的生命周期完全在该区间内，故输出 $3$ ；

• 查询区间 $[2,6]$ 时，有 $2$ 个细菌(第 $2、3$ )满足条件，故输出 $2$ ；

• 查询区间 $[1,10]$ 时，所有 $5$ 个细菌都满足条件，故输出 $5$ 。

样例2

输入

4 2
1 3
2 4
3 5
4 6
2 4
3 6

输出

1
2