Kangaroos

信息

此题目来自 洛谷， 原始题目与提交代码请前往 P6349 [PA 2011] Kangaroos - 洛谷。

题目描述

给出长为 $n$ 的序列 $a$，第 $i$ 个元素是一个区间 $[l_i,r_i]$。

$m$ 次询问，给出 $A,B$，求出 $a$ 中最长的区间（即这个序列中的一段），使得这个区间内每个区间都与 $[A,B]$ 有交集。输出这个最长区间的长度。

第一行两个整数 $n,m$。

接下来 $n$ 行，第 $i$ 行两个整数 $l_i,r_i$。

接下来 $m$ 行，每行两个整数 $A,B$，为一次询问。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，第 $i$ 行两个整数 $l_i,r_i$。

接下来 $m$ 行，每行两个整数 $A,B$，为一次询问。

输出格式

输出 $m$ 行，每行一个整数，为询问的答案。

输入输出样例

输入 #1

3 3
2 5
1 3
6 6
3 5
1 10
7 9

输出 #1

2
3
0

说明/提示

${1}\le{n}\le{{5}\times{10^{4}}}$， ${1}\le{m}\le{{2}\times{{10}^{5}}}$， ${1}\le{{l}_{i}}\le{{r}_{i}}\le{{10}^{9}}$， ${1}\le{A}\le{B}\le{{10}^{9}}$

题目解答

枚举法

直接一个个进行比对即可。

C++

/**
 * 洛谷 P6349 解答程序。
 * @author CoolCLK
 */
#include <iostream>
#include <vector>
#define repeat(n) for (size_t _ = 0; _ < n; _++)
typedef unsigned int u_int;
using namespace std;

u_int n, m;
vector<pair<u_int, u_int>> intervals(0);
vector<u_int> answers(0);

int main() {
    cin >> n >> m;
    repeat(n) {
        u_int l, r;
        cin >> l >> r;
        intervals.push_back(pair<u_int, u_int>(l, r));
    }
    repeat(m) {
        u_int A, B;
        cin >> A >> B;
        u_int ans = 0;
        u_int len = 0;
        
        for (auto& interval : intervals) {
            if (interval.first <= B && interval.second >= A) {
                len++;
                if (len > ans) ans = len;
            } else {
                len = 0;
            }
        }
        answers.push_back(ans);
    }
    for (auto& ans : answers) {
        cout << ans << endl;
    }
    return 0;
}

动态规划+二分法

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 50005;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> inters(n);
    for (int i = 0; i < n; i++) {
        cin >> inters[i].first >> inters[i].second;
    }
    
    // 预处理连续段的最大最小值
    vector<int> maxL(n), minR(n);
    vector<int> dp(n);  // dp[i] = 以i结尾的最长连续段长度
    
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            maxL[i] = inters[i].first;
            minR[i] = inters[i].second;
            dp[i] = 1;
        } else {
            maxL[i] = max(maxL[i - 1], inters[i].first);
            minR[i] = min(minR[i - 1], inters[i].second);
            if (inters[i].first <= minR[i - 1] && inters[i].second >= maxL[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 1;
            }
        }
    }
    
    // 处理查询
    while (m--) {
        int A, B;
        cin >> A >> B;
        
        // 二分找满足条件的左边界
        auto check = [&](int len) {
            for (int i = len - 1; i < n; i++) {
                if (dp[i] >= len) {
                    // 检查子区间是否满足[maxL, minR]在[A, B]中的条件
                    int l = maxL[i];
                    int r = minR[i];
                    if (l <= B && r >= A) return true;
                }
            }
            return false;
        };
        
        int l = 0, r = n, ans = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(mid)) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cout << ans << '\n';
    }
    
    return 0;
}

分块算法

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = 50005;
const int BLK = 225; // sqrt(50000) ≈ 223

struct Block {
    int l_len, r_len, max_len;
    bool full;
};

vector<Block> blocks;
vector<bool> valid;
int block_size, block_cnt;

void build_blocks(int n) {
    block_size = sqrt(n);
    block_cnt = (n + block_size - 1) / block_size;
    blocks.resize(block_cnt);
    valid.resize(n, false);
}

void update_block(int bid, int n) {
    int start = bid * block_size;
    int end = min(start + block_size, n) - 1;
    
    int cur = 0;
    blocks[bid].l_len = blocks[bid].r_len = blocks[bid].max_len = 0;
    blocks[bid].full = true;
    
    // 计算左连续长度
    for (int i = start; i <= end; i++) {
        if (valid[i]) {
            blocks[bid].l_len++;
        } else {
            blocks[bid].full = false;
            break;
        }
    }
    
    // 计算右连续长度
    for (int i = end; i >= start; i--) {
        if (valid[i]) {
            blocks[bid].r_len++;
        } else {
            break;
        }
    }
    
    // 计算块内最大连续长度
    int max_cur = 0;
    for (int i = start; i <= end; i++) {
        if (valid[i]) {
            cur++;
            max_cur = max(max_cur, cur);
        } else {
            cur = 0;
        }
    }
    blocks[bid].max_len = max_cur;
}

int query_global() {
    int max_len = 0;
    int cur = 0;
    for (int i = 0; i < block_cnt; i++) {
        if (blocks[i].full) {
            cur += block_size;
            max_len = max(max_len, cur);
        } else {
            max_len = max(max_len, blocks[i].max_len);
            if (cur > 0) {
                max_len = max(max_len, cur + blocks[i].l_len);
                cur = blocks[i].r_len;
            }
        }
    }
    return max_len;
}

int main() {
    // 输入和预处理代码详见线段树的实现
    
    build_blocks(n);
    vector<int> ans(m, 0);
    
    int p = 0, q = 0;
    for (int i = 0; i < m; i++) {
        while (p < n && inters[p].l <= qrys[i].b) {
            int idx = inters[p].idx;
            valid[idx] = true;
            update_block(idx / block_size, n);
            p++;
        }
        
        while (q < n && r_values[q] >= qrys[i].a) {
            int r_val = r_values[q];
            for (int j = q; j < n; j++) {
                if (inters[j].r < r_val) break;
                int idx = inters[j].idx;
                valid[idx] = true;
                update_block(idx / block_size, n);
            }
            q++;
        }
        
        ans[qrys[i].idx] = query_global();
    }
    
    for (int i = 0; i < m; i++) {
        cout << ans[i] << '\n';
    }
    
    return 0;
}

线段树

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 50005;
const int MAXM = 200005;

struct SegTree {
    struct Node {
        int l_len, r_len, max_len;
        Node() : l_len(0), r_len(0), max_len(0) {}
    };
    
    vector<Node> tree;
    int n;
    
    SegTree(int size) : n(size) {
        tree.resize(4 * n);
    }
    
    Node merge(const Node& left, const Node& right, int l_cnt, int r_cnt) {
        Node res;
        res.l_len = (left.l_len == l_cnt) ? l_cnt + right.l_len : left.l_len;
        res.r_len = (right.r_len == r_cnt) ? r_cnt + left.r_len : right.r_len;
        res.max_len = max({left.max_len, right.max_len, left.r_len + right.l_len});
        return res;
    }
    
    void update(int idx, int l, int r, int pos, int val) {
        if (l == r) {
            tree[idx].l_len = tree[idx].r_len = tree[idx].max_len = val;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) {
            update(idx * 2, l, mid, pos, val);
        } else {
            update(idx * 2 + 1, mid + 1, r, pos, val);
        }
        tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1], 
                         mid - l + 1, r - mid);
    }
    
    int query() {
        return tree[1].max_len;
    }
};

struct Interval {
    int l, r, idx;
};

struct Query {
    int a, b, idx;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<Interval> inters(n);
    for (int i = 0; i < n; i++) {
        cin >> inters[i].l >> inters[i].r;
        inters[i].idx = i;
    }
    
    vector<Query> qrys(m);
    for (int i = 0; i < m; i++) {
        cin >> qrys[i].a >> qrys[i].b;
        qrys[i].idx = i;
    }
    
    // 按左端点排序
    sort(inters.begin(), inters.end(), [](const Interval& x, const Interval& y) {
        return x.l < y.l;
    });
    
    // 按右端点降序排序
    sort(qrys.begin(), qrys.end(), [](const Query& p, const Query& q) {
        return p.b != q.b ? p.b < q.b : p.a > q.a;
    });
    
    vector<bool> inB(n, false), inA(n, false);
    SegTree segTree(n);
    vector<int> ans(m, 0);
    
    // 按R值降序处理
    vector<int> r_values;
    for (int i = 0; i < n; i++) r_values.push_back(inters[i].r);
    sort(r_values.begin(), r_values.end(), greater<int>());
    
    int p = 0;  // L指针
    int q = 0;  // R指针
    for (int i = 0; i < m; i++) {
        // 添加满足 L <= B 的区间
        while (p < n && inters[p].l <= qrys[i].b) {
            int idx = inters[p].idx;
            inB[idx] = true;
            if (inA[idx]) {
                segTree.update(1, 0, n - 1, idx, 1);
            }
            p++;
        }
        
        // 添加满足 R >= A 的区间
        while (q < n && r_values[q] >= qrys[i].a) {
            int r_val = r_values[q];
            for (int j = q; j < n; j++) {
                if (inters[j].r < r_val) break;
                int idx = inters[j].idx;
                inA[idx] = true;
                if (inB[idx]) {
                    segTree.update(1, 0, n - 1, idx, 1);
                }
            }
            q++;
        }
        
        ans[qrys[i].idx] = segTree.query();
    }
    
    for (int i = 0; i < m; i++) {
        cout << ans[i] << '\n';
    }
    
    return 0;
}