测试数据是否有误?

题目说不存在两个区间完全覆盖。说明,将所有区间的左端点进行排序之后,右端点也是单调的,这样子就应该可以使用双指针解决这个问题。我的代码是使用双指针写的,不知道问题出在哪里。

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

全部评论

相关推荐

uu们,拒offer时hr很生气怎么办我哭死
爱睡觉的冰箱哥:人家回收你的offer,或者oc后没给你发offer的时候可不会愧疚你,所以你拒了也没必要愧疚他。
点赞 评论 收藏
分享
07-01 13:37
门头沟学院 Java
steelhead:不是你的问题,这是社会的问题。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务