P4396 [AHOI2013]作业 莫队 + 树状数组
发布日期:2021-09-25 23:58:08
浏览次数:3
分类:技术文章
本文共 1966 字,大约阅读时间需要 6 分钟。
题意:给定一个序列,m个询问,每次询问给定一个区间 [ l , r ] 和两个数 a b ,求这个区间中有多少数在 [ a , b ] 区间之间和有多少数出现在 [ a , b ] 之间。
文字可能表述不好,下面给一组样例: 序列 1 2 2 询问 1 3 1 3 ( l , r , a , b ) 答案 3 2最近学莫队肯定是用莫队来搞了,显然 [ a , b ] 可以转换成前缀来搞,用两个树状数组来维护就行了,一个直接维护前缀个数,一个维护当前数是否出现即可。
时间复杂度: O ( N N l o g N ) O(N\sqrt{N}logN) O(NNlogN)正解应该是套上值域分块(奈何我目前不会啊。
#pragma GCC optimize(2)#include#include #include #include #include
转载地址:https://blog.csdn.net/DaNIelLAk/article/details/108386141 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月02日 09时30分53秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
实战六:手把手教你用TensorFlow进行手写数字识别
2019-04-26
实战七:手把手教你用TensorFlow进行验证码识别(上)
2019-04-26
机器学习算法之梯度下降法
2019-04-26
机器学习算法之多项式回归
2019-04-26
TensorFlow(keras)入门课程--01 机器学习的Hello World
2019-04-26
TensorFlow(keras)入门课程--03 卷积介绍
2019-04-26
TensorFlow(keras)入门课程--04 卷积神经网络
2019-04-26
TensorFlow(keras)入门课程--05 复杂图像处理
2019-04-26
TensorFlow(keras)入门课程--06 CNN用于猫狗数据集
2019-04-26
【比赛篇】TinyMind人民币面值 - 热身赛
2019-04-26
卷积神经网络交通标志识别
2019-04-26
【实战】深度学习构建人脸面部表情识别系统
2019-04-26
Python机器学习&数据分析-关联规则
2019-04-26
【实战】kaggle猫狗大战-卷积神经网络实现猫狗识别
2019-04-26
01 计算机视觉-opencv图像基本操作
2019-04-26
02 计算机视觉-opencv阈值与滤波处理
2019-04-26
03 计算机视觉-opencv图像形态学处理
2019-04-26
04计算机视觉-opencv图像梯度处理
2019-04-26
05计算机视觉-opencv边缘检测
2019-04-26
07 计算机视觉-opencv模板匹配
2019-04-26