【哈希】ABC248 D - Range Count Query

太过爱你忘了你带给我的痛 2024-03-23 17:07 36阅读 0赞

**独立做出来的一道题！**

**考虑题目特殊性就可以**

[D - Range Count Query (atcoder.jp)][D - Range Count Query _atcoder.jp]

题意：

![54112c9766aa47509cfbe9cc94ef9786.png][]

思路：

本来一点思路都没，只会暴力

但是有个特殊条件：ai的值域在1~N之间

因此可以考虑哈希

考虑值域的那根数轴，值域中的每个数都插入位置

那么每次询问之间二分出第一个>=L的和最后一个<=R的位置，就可以计算贡献了！

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    
    vector<int> v[mxn];
    
    int N,Q,L,R,X;
    int a[mxn];
    
    signed main(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i],v[a[i]].push_back(i);
    	cin>>Q;
    	while(Q--){
    		cin>>L>>R>>X;
    		int pos1=lower_bound(v[X].begin(),v[X].end(),L)-v[X].begin();
    		int pos2=upper_bound(v[X].begin(),v[X].end(),R)-v[X].begin()-1;
    		cout<<max(0ll,pos2-pos1+1)<<'\n';
    	}
    }

[D - Range Count Query _atcoder.jp]: https://atcoder.jp/contests/abc248/tasks/abc248_d
[54112c9766aa47509cfbe9cc94ef9786.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/eec80bb9453643039daeab02623f62bc.png

发表评论取消回复

表情：

评论列表（有 0 条评论，36人围观）

还没有评论，来说两句吧...

相关阅读

相关【哈希】ABC248 D - Range Count Query

独立做出来的一道题！考虑题目特殊性就可以 [D - Range Count Query (atcoder.jp)][D - Range Count Query _atco

太过爱你忘了你带给我的痛/ 2024年03月23日 17:07/ 0 赞/ 37 阅读

相关【Floyd】ABC208 D - Shortest Path Queries 2

[D - Shortest Path Queries 2 (atcoder.jp)][D - Shortest Path Queries 2 _atcoder.jp] 题意：

偏执的太偏执、/ 2024年03月22日 18:04/ 0 赞/ 33 阅读

相关【交互题】ABC299 D - Find by Query

[D - Find by Query (atcoder.jp)][D - Find by Query _atcoder.jp] 题意：有一个01串，左边都是0，右边都是1

野性酷女/ 2024年03月22日 10:38/ 0 赞/ 42 阅读

相关关于哈希关于哈希关于哈希

今天老师讲了哈希，草草地整理一下：哈希表，也称散列表，是一种高效的数据结构。它的最大优点就是把数据存储和查找所消耗的时间大大降低，几乎可以看成是 O（1）的，而代价是消耗比

旧城等待，/ 2023年10月04日 18:49/ 0 赞/ 39 阅读

相关哈希值哈希表_哈希杰森

哈希值哈希表我最近写了一个[简单的库，可预测地对json进行哈希处理][json] 。该实用程序基于出色的[Jackson Json解析库][Jackson Json

阳光穿透心脏的1/2处/ 2023年02月25日 04:56/ 0 赞/ 33 阅读

相关 leetcode 304. Range Sum Query 2D - Immutable

You are given an integer array nums and you have to return a new counts array. The count

冷不防/ 2022年08月20日 13:07/ 0 赞/ 18 阅读

相关重温数据结构：哈希哈希函数哈希表

[点击查看 Java 集合框架深入理解系列][Java _]， - ( ゜- ゜)つロ乾杯~ > 在学习 HashMap 前，我们先来温习下 Hash(哈希) 的概念

￡神魔★判官ぃ/ 2022年07月15日 00:30/ 0 赞/ 331 阅读

相关 RMQ(Range Minimum Query)

RMQ RMQ（Range Minimum Query）是指区间最值查询，即对于长度为 n 的数列 A，回答若干询问 RMQ(A,i,j),(i,j<=n)，返回数列

短命女/ 2022年06月08日 06:07/ 0 赞/ 93 阅读

相关 Range Sum Query - Immutable

303. Range Sum Query - Immutable 题目描述 Given an integer array nums, find the sum of

缺乏、安全感/ 2022年05月14日 12:35/ 0 赞/ 171 阅读

相关 304. Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by i

Bertha 。/ 2022年03月06日 06:42/ 0 赞/ 178 阅读