作者:SADFGHJKSADFV_565 | 来源:互联网 | 2023-10-16 18:52
题目链接:http:acm.hdu.edu.cnshowproblem.php?pid3333题意:数轴上的区间和问题,有一些变化就是要求的是不同元素的和,线段树or数状数组可以解决.刚
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3333
题意:数轴上的区间和问题,有一些变化就是要求的是不同元素的和,线段树or数状数组可以解决.
刚开始时竟然给线段树的每人结点维护了一个set 来标记是否有重复,那个复杂度弄的比暴力都高了吧,汗一个~
后来看了下别人的思路,采用离线操作,对Q所要求的区间以右端点递增排序,从左至右插入新的元素,如果该元素已经插入了线段树中,就删掉旧位置的,在新位置插入该元素,并对以该元素位置为右端点的区间进行查询求和,即为结果.
记录元素是否已插入线段树可用离散化+二分来实现,也可用hash来记录.这里用的是hash表.
首先用线段树写了,可是一直RE的很悲状,后来才发现ans[]数组竟然开小了,这鬼~
数状数组实现很简单,甚至效率也高了线段树很多.
线段树:
数状数组: