测试数据是否有误?
题目说不存在两个区间完全覆盖。说明,将所有区间的左端点进行排序之后,右端点也是单调的,这样子就应该可以使用双指针解决这个问题。我的代码是使用双指针写的,不知道问题出在哪里。
#include<iostream> #include<algorithm> #include<unordered_map> using namespace std; const int N = 3e5 + 10; int a[N]; int n, q; struct Data{ int l, r, k, id; bool operator< (const Data &d) const{ return l < d.l; } }g[N]; int res[N];//记录结果 int main() { while (cin >> n) { int x = 1, y = 0; unordered_map<int, int> num;//记录当前区间喜好值的个数 for (int i = 1; i <= n; i++) cin >> a[i]; cin >> q; for (int i = 0; i < q; i++) { int l, r, k; cin >> l >> r >> k; g[i] = {l, r, k, i}; } sort(g, g + q); for (int i = 0; i < q; i++) { int l = g[i].l, r = g[i].r, k = g[i].k, id = g[i].id; while (y < r) num[a[++y]] ++; while (x < l) num[a[x++]] --; res[id] = num[k]; } for (int i = 0; i < q; i++) cout << res[i] << endl; } return 0; }