本文从WordPress迁移而来, 查看全部WordPress迁移文章
http://codeforces.com/problemset/problem/85/D
线段树
离线处理,好题
题目的输入数据中保证了严格的合法性:插入的元素一定是集合中没有的,删除的元素一定是集合中存在的,所以要好好利用这点
先读入全部操作,那么就可以知道一共有哪些数字出现过(只需要统计add后面的数字)
排序(去重可以省掉因为数据保证了不会重复),离散化
这里离散化是因为数字太大了10^9(如果数字小不需离散化)
那么插入一个数字就能在所有出现的数字找到它的准确位置(所有不同的数字个数是tot,线段树总区间就是tot)
每个节点记录6个信息,分别是这个区间插入了多少个数字cnt
这个区间内%5分别为0,1,2,3,4的数字和重要的PushUp合并区间的时候
当前区间的sum[0,1,2,3,4]直接继承左孩子的sum
对于右孩子,它的sum不能直接给当前区间,要“移位”
左孩子插入数字总数为Lcnt,那么右区间的sum[i]传递给当前区间的时候
实际变为了sum[(i+Lcnt)%5]
另外插入和删除操作实际上都是单点更新,来到叶子后,对于叶子这个区间而言
这个数字一定是“第1个数字”,所以t[leaf].sum[1] = val
1 |
|