hdu 4288 Coder (离散化, 线段树,单点更新,区间合并)

题目链接

题意:n(1E5)个操作,分为三种,add x表示将x加到集合中(保证集合中之前没有x),del x表示从集合中删掉x(保证集合中一定右x),sum表示求集合中所有元素按从小到大排列后,所有的下标中满足i%5=3的a[i]的和。1=<x<=1E9

思路:很容易想到的是,由于插入和删除元素造成的位置改变是剧烈的,因此要分别维护i%5==k,k属于0..4的元素的和。

这道题的核心点在于,由于只有1E5个操作,我们可以将元素离散化,这样做的目的是,将每个数和位置一一对应,每个位置用1或者0,表示该位置对应的元素是否在集合中。

考虑线段树,维护6个域,1个是区间中,在集合中的元素个数,剩下5个域,分别表示以该区间的端点为位置1,位置x%i=k的元素的和(k属于0..4)。因此每个叶子节点都是位置1.

考虑PushUp, 区间元素和之间累加,难点在于其他5个域的维护。

假设当前区间为rt,那么对于sum[0..4] (sum代表的就是上面说的要维护的5个域),显然区间rt<<1的答案可以直接贡献给rt.

对于rt<<1|1的答案,考虑rt<<1|1中位置为%5==x的元素和,rt<<1中的元素个数为len个,那么rt<<1|1中sum[x]对 rt中的sum[(x+len)%5]有贡献。

反推出对rt 中 sum[i]有贡献的是rt<<1|1中的sum[(i-len+5)%5)]

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz