当前位置：首页 > article >正文

洛谷 P10288 [GESP样题八级] 区间 C++ 完整题解（STL二分法）

article 2025/2/1 18:31:37

本文并非最优解，但能通过。

一、题目链接

P10288 [GESP样题八级] 区间 - 洛谷

二、解题思路

**本题的大意就是求出a[l~r]间x出现的次数，由于数据较大、较多，所以暴力容易超时。**

首先新建一个mp，mp[x]是一个vector，里面存放从前到后x出现的下标。
map<int, vector<int> > mp;
如下，在输入时录入每个下标。
for (int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    mp[x].push_back(i);
}
接下来就是查询：

首先认识两个函数
简单用法:
upper_bound(起点, 终点, x);
返回从起点到终点第一个【大于】x的位置 返回类型是iterator。
例如upper_bound(v.begin(), v.end(), x)

lower_bound(起点, 终点, x);
返回从起点到终点第一个【不小于】x的位置 返回类型是iterator。
例如lower_bound(v.begin(), v.end(), x)

!!!如果找不到, 返回最后一个元素后面的位置
所以：
while (q--) {
    int l, r, x;
    cin >> l >> r >> x;
    cout << upper_bound(mp[x].begin(), mp[x].end(), r) - lower_bound(mp[x].begin(), mp[x].end(), l) << endl;
}

三、完整代码

温馨提示：看最后面的代码。

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


int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, q;
        map<int, vector<int> > mp;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            mp[x].push_back(i);
        }
        cin >> q;
        while (q--) {
            int l, r, x;
            cin >> l >> r >> x;
            cout << upper_bound(mp[x].begin(), mp[x].end(), r) - lower_bound(mp[x].begin(), mp[x].end(), l) << endl;
        }
    }
    return 0;
}

居然超时

在这里，加上ios::sync...也没有AC，我们需要把cin, cout改成scanf, printf或快读快写。

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

map<int, vector<int> > mp;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        mp.clear();
        int n, q;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            mp[x].push_back(i);
        }
        scanf("%d", &q);
        while (q--) {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", upper_bound(mp[x].begin(), mp[x].end(), r) - lower_bound(mp[x].begin(), mp[x].end(), l));
        }
    }
    return 0;
}