面试算法题:O(nlogn)查询l~r区间内k的个数

2023-10-26

查询用户文章喜好

我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为k。因为一些特殊的原因,不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在L1<=L2<=R2<=R1)。

输入描述:

输入: 第1行为n代表用户的个数 第2行为n个整数,第i个代表用户标号为i的用户对某类文章的喜好度 第3行为一个正整数q代表查询的组数 第4行到第(3+q)行,每行包含3个整数l,r,k代表一组查询,即标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数。 数据范围n <= 300000,q<=300000 k是整型

输出描述:

输出:一共q行,每行一个整数代表喜好值为k的用户的个数

输入例子1:

5
1 2 3 3 5
3
1 2 1
2 4 5
3 5 3

输出例子1:

1
0
2

例子说明1:

样例解释:
有5个用户,喜好值为分别为1、2、3、3、5,
第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1
第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0
第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2

解法思路

分块搜索

  • 若查询1次区间,可以将区间排序,统计即可
  • 1 0 6 10^6 106次查询,不能每次都排序
  • 将数据大约分为 s q r t ( n ) sqrt(n) sqrt(n)块,存储两个数组分别是原数组和每块排好序的数组
  • 分为2种情况
1. 查询的左右端点在同一块
2. 查询的左右端点在不同一块
  • 第一种情况遍历即可,复杂度不超过 O ( s q r t ( n ) ) O(sqrt(n)) O(sqrt(n))
  • 第二种情况在头尾两块遍历,中间的块(若有)则二分查找(预处理时每块排序)

参考代码

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
#define N 300000

int a[N + 5], b[N + 5];

int getLtoR(int l, int r, int k) {
    int cnt = 0;
    for (int i = l; i <= r; i++) {
        if (a[i] == k) cnt++;
    }
    return cnt;
}

int halfSearch(int l0, int r0, int x) {
    int l = l0, r = r0, mid;
    while (l < r) {
        mid = (l + r) / 2;
        x <= b[mid] ? r = mid : l = mid + 1;
    }
    return r;
}

int main() {
    int n, q, m;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    m = sqrt(n);
    for (int i = 1; i <= m + 1; i++) {
        if ((i - 1) * m + 1 > n) break;
        sort(b + (i - 1) * m + 1, b + min(i * m, n) + 1);
        /*
        for (int j = (i - 1) * m + 1; j <= min(i * m, n); j++)
            printf("%d ", b[j]);
        printf("\n");
        */
    }
    scanf("%d", &q);
    while (q--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        int lx = (l - 1) / m + 1, rx = (r - 1) / m + 1, ans = 0;
        if (lx == rx) {
            ans = getLtoR(l, r, k);
        } else {
            ans = getLtoR(l, lx * m, k) + getLtoR((rx - 1) * m + 1, r, k);
            for (int i = lx + 1; i <= rx - 1; i++) {
                int left = halfSearch((i - 1) * m + 1, i * m, k);
                // printf("%d\n", left);
                if (b[left] == k) {
                    int right = left;
                    while (b[right + 1] == k && right + 1 <= i * m) right++;
                    ans += right - left + 1;
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

面试算法题:O(nlogn)查询l~r区间内k的个数 的相关文章

  • Numpy 实现全连接神经网络

    神经网络与深度学习实验报告 一 实验名称 Numpy 实现全连接神经网络 二 实验要求 用 python 的 numpy 模块实现全连接神经网络 网络结构为一个输入层 一个隐藏层 一个输出层 隐藏层的激活函数为 Relu 函数 输出层的激活
  • Qt系列文章之 QTabWidget

    上一篇文章介绍如何对QMessgeBox进行使用 本文紧接上文内容继续对Qt的窗体文件开发介绍 一般主界面会有很多控件和交互区域 如果把所有的控件都放在一个界面全部显示 整个界面就会显得非常臃肿繁琐 那么使用分页式的表格窗体布局就能将不同类
  • STM32 从APP跳入BootLoader问题

    在这次项目中 程序从APP跳入BootLoader主要遇到两个问题 做个记录 1 现象 跳入BootLoader后还没开始升级便重启 原因 APP程序中开启了独立看门狗 当跳入BootLoader时看门狗也继续计时 但并没有重新喂狗 因此导

随机推荐

  • uniapp开发日志

    bug 将Base64的编码解码看错 uniapp封装uni request方法 import utils from js utils js let debug false if process env NODE ENV developme
  • Advanced Computer Network Review(3)——BBR

    这是复习系列的第三篇 主要梳理BBR拥塞控制有关的一些要点 老师给出的复习要点如下 1 基于loss的拥塞控制存在什么问题 为什么 2 理解下面这张图 这篇文章的梳理部分参考了中科大郑烇老师 高级计算机网络 的相关部分 特此声明 一 基于l
  • windows命令行更改文件夹权限

    echo off rem windows命令行更改文件夹权限 Cacls命令使用格式如下 Cacls filename T E C G user perm R user P user perm D user Filename 显示访问控制列
  • Linux下如何查看分区文件系统类型

    1 fdisk l fdisk l 只能列出硬盘的分区表 容量大小以及分区类型 但看不到文件系统类型 2 df h df 命令是用来查看文件系统磁盘空间使用量的 但df 命令只会列出已挂载的文件系统信息 对于没有挂载的文件系统是查看不到的
  • LeetCode -数组数据的插入位置(二分法)

    搜索数组数据插入位置 给定一个排序数组和一个目标值 在数组中找到目标值 并返回其索引 如果目标值不存在于数组中 返回它将会被按顺序插入的位置 数组可能有重复数据 有重复数据时返回 插入到重复数据的第一个位置 示例 1 输入 1 3 6 7
  • Vuforia 官方Demo讲解

    官方原文地址 https library vuforia com articles Solution Native Sample Application Template 今天看到的36氪新闻 高通发布面向VR AR一体机的骁龙XR1芯片
  • MySQL的自定义排序函数 FIELD(str,str1,str2,str3,...)

    FIELD是mysql的自定义排序函数 ORDER BY FIELD str str1 str2 str3 说明 str是字段 str1 str2 是自定义排序的值 举例说明 以上两幅图就看懂FIELD 的用法了吧
  • Vue——get调用后端接口并将数据回显到table中

    get调用 呈现效果 动态获取后台数据 1 HTML lt template gt
  • vue —— 项目启动时无法识别es6的扩展语法

    启动项目报错 解决 ES6的拓展运算符报错 1 切换淘宝镜像 npm install g cnpm registry http registry npm taobao org cnpm install legacy peer deps sa
  • “三项能力超过ChatGPT”,科大讯飞星火大模型现场接受观众挑战,写稿制表PPT通通拿下...

    杨净 发自 合肥量子位 公众号 QbitAI 三项能力超过ChatGPT 1024将整体超过GPT水平 在科大讯飞星火认知大模型发布会现场 董事长刘庆峰拍着胸脯保证 引起现场掌声雷动 而真机演示效果和多场景产品展示直接把观众们看呆 信息量太
  • anaconda pytorch配置

    wvscode配置python编译器时 发现即使在右下角改变编译器版本 任然无法使用anaconda的python 通过在setting中搜索code runner 修改Execution Map中python u中python为anaco
  • JS anonymous:无名函数的使用

    这个无名函数名字是我起的 起这个名字的原因有两条 原因一是在改前端代码的时候发现这个东西 在调试台console用debug调试 会显示一个anonymous 但你发现他是一个函数 原因二是 这个在w3school上也有 在下面连接页面搜索
  • 解决:500 Internal Privoxy Error

    500 Internal Privoxy Error Privoxy encountered an error while processing your request Could not load template file no se
  • 内网穿透 VScodeSHH

    准备 腾讯云服务器 linux xshell xftp frp https github com fatedier frp 服务端为腾讯云服务器 linux 客户端为自己工作站 linux 服务端操作 用xshell登录腾讯云服务器 下载
  • audio标签与video标签的常用属性及方法

    一 常用的css属性 1 src 用于指明video标签需要播放的音频的地址
  • C语言学习之认识exit()函数

    C语言学习之认识exit 函数 在C语言的main函数中我们通常使用return 0 exit 0 表示程序正常退出 exit exit 1 表示程序异常退出 exit 结束当前进程 当前程序 在整个程序中 只要调用 exit 就结束 但在
  • unity下HybridCLR热更新简易框架

    简易打AB包工具 using System Collections using System Collections Generic using UnityEngine using UnityEditor using HybridCLR E
  • servlet的生命周期

    Servlet的生命周期可以分为5个阶段 加载阶段 创建阶段 初始化阶段 处理客户请求 服务 阶段 销毁阶段 1 加载阶段 服务器接收到客户端请求之后首先会通过类加载器使用servlet类对应的文件加载servlet 2 创建阶段 然后we
  • 河海大学计算机esi排名,河海大学材料科学学科进入ESI国际排名前1%

    根据汤森路透基本科学指标数据库 Essential Science Indicators 简称ESI 2018年3月最新公布的数据 河海大学材料科学学科继工程学 环境 生态学 计算机科学之后首次进入ESI国际学科排名全球前1 实现了学校学科
  • 面试算法题:O(nlogn)查询l~r区间内k的个数

    查询用户文章喜好 我们对用户按照它们的注册时间先后来标号 对于一类文章 每个用户都有不同的喜好值 我们会想知道某一段时间内注册的用户 标号相连的一批用户 中 有多少用户对这类文章喜好值为k 因为一些特殊的原因 不会出现一个查询的用户区间完全