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

2025/2/6 18:48:04 来源：https://blog.csdn.net/applelin2012/article/details/145403864 浏览: 次关键词：洛谷 P10288 [GESP样题八级] 区间 C++ 完整题解（STL二分法）

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

一、题目链接

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;
}