hdu 3874 树状数组+离线处理

2024-05-28 04:48

本文主要是介绍hdu 3874 树状数组+离线处理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://acm.hdu.edu.cn/showproblem.php?pid=3874


跟上一题一样http://blog.csdn.net/u011026968/article/details/38542227,我相当于默写一遍上一题的代码。。。。

上次出现的问题在这里总结下:
1、lower_bound()返回的是指针,为了变为下标,需要减去数组首地址----当然这个下标是从0开始的,树状数组里下标从1开始,所以再多加个1

2、离散化的方法:
以前我的做法是:http://blog.csdn.net/u011026968/article/details/38527151

就是lisan[i]=i  对lisan[]数组按照num[i]数组进行间接排序,然后lisan[i]=k,表示第i小的数在num的下标为k,再做一次处理,d[lisan[i]]=i,相当于把num中下标为k的数变成了i,而且i范围是1~n  (n是数的个数),就达到了压缩区间的目的。但是今天发现,如果原来的数组里面有重复元素,那么这样处理之后,新的数组没有重复元素了o(╯□╰)o

对于hdu3874和hdu3333这种排除重复元素的题,当然这种离散化的方法就不对了

这道题不需要离散化,,,

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;#define ls(rt) rt*2
#define rs(rt) rt*2+1
#define ll long long
#define ull unsigned long long
#define rep(i,s,e) for(int i=s;i<e;i++)
#define repe(i,s,e) for(int i=s;i<=e;i++)
#define CL(a,b) memset(a,b,sizeof(a))
#define IN(s) freopen(s,"r",stdin)
#define OUT(s) freopen(s,"w",stdout)const int MAXN =  50000+100;
struct Query
{int l,r;int id;bool operator < (const Query &c)const{return r<c.r;}
}q[200000 + 100];ll c[MAXN],ans[200000 + 100];
ll num[MAXN],bi[MAXN];
int last[MAXN];
int N;inline int lowbit(int i){return i&(-i);}void add(int x, int v)
{while(x<=N){c[x]+=v;x+=lowbit(x);}
}
ll sum(int i)
{ll ret=0;while(i>0){ret+=c[i];i-=lowbit(i);}return ret;
}int main()
{//IN("hdu3874.txt");int ncase;int Q,l,r;scanf("%d",&ncase);while(ncase--){scanf("%d",&N);CL(c,0);CL(last,0);for(int i=1;i<=N;i++){scanf("%I64d",&num[i]);bi[i]=num[i];}sort(bi+1,bi+1+N);scanf("%d",&Q);for(int i=1;i<=Q;i++){scanf("%d%d",&q[i].l,&q[i].r);q[i].id=i;}sort(q+1,q+1+Q);int qu=1;for(int i=1;i<=N;i++){int pos=lower_bound(bi+1,bi+1+N,num[i])-bi;if(last[pos]){add(last[pos],-num[i]);last[pos]=i;}add(i,num[i]);last[pos]=i;while(q[qu].r == i && qu<=Q){ans[q[qu].id]=sum(i)-sum(q[qu].l-1);qu++;}}for(int i=1;i<=Q;i++)printf("%I64d\n",ans[i]);}return 0;
}



这篇关于hdu 3874 树状数组+离线处理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1009577

相关文章

Java堆转储文件之1.6G大文件处理完整指南

《Java堆转储文件之1.6G大文件处理完整指南》堆转储文件是优化、分析内存消耗的重要工具,:本文主要介绍Java堆转储文件之1.6G大文件处理的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言文件为什么这么大?如何处理这个文件?分析文件内容(推荐)删除文件(如果不需要)查看错误来源如何避

使用Python构建一个高效的日志处理系统

《使用Python构建一个高效的日志处理系统》这篇文章主要为大家详细讲解了如何使用Python开发一个专业的日志分析工具,能够自动化处理、分析和可视化各类日志文件,大幅提升运维效率,需要的可以了解下... 目录环境准备工具功能概述完整代码实现代码深度解析1. 类设计与初始化2. 日志解析核心逻辑3. 文件处

Java docx4j高效处理Word文档的实战指南

《Javadocx4j高效处理Word文档的实战指南》对于需要在Java应用程序中生成、修改或处理Word文档的开发者来说,docx4j是一个强大而专业的选择,下面我们就来看看docx4j的具体使用... 目录引言一、环境准备与基础配置1.1 Maven依赖配置1.2 初始化测试类二、增强版文档操作示例2.

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

Python使用vllm处理多模态数据的预处理技巧

《Python使用vllm处理多模态数据的预处理技巧》本文深入探讨了在Python环境下使用vLLM处理多模态数据的预处理技巧,我们将从基础概念出发,详细讲解文本、图像、音频等多模态数据的预处理方法,... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

Spring Boot @RestControllerAdvice全局异常处理最佳实践

《SpringBoot@RestControllerAdvice全局异常处理最佳实践》本文详解SpringBoot中通过@RestControllerAdvice实现全局异常处理,强调代码复用、统... 目录前言一、为什么要使用全局异常处理?二、核心注解解析1. @RestControllerAdvice2

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方