测试数据是否有误?

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

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

全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 15:19
点赞 评论 收藏
分享
08-19 17:40
Java
吴offer选手:666 打老板了吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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