本文从WordPress迁移而来, 查看全部WordPress迁移文章
离散处理 + 树状数组 OR 线段树
【2013多校联合训练第四场】
题意:给出一个n的序列,里面只有1到n的数字每个出现且仅出现一次。有n个询问,每个询问给出一个[l,r]区间,问你这个区间可以分成多少段连续的序列(你可以把里面的数字发乱重新排列)。例如一段区间的序列为{2,3,5,6,1,9},可以排成的连续的序列的{1,2,3}{5,6}{9},分成了3段,所以输出3
这题需要离线处理,通过一个val数组,将问题巧妙地转化为可以用线段树来解决的题目
首先我们来考虑一个前缀序列,即如果每次都问你[1,r]里面能分成多少段,要怎么做
从左到右地读入序列。没读入一个数字a[i],我们先认为它自己成为一段。然后看看它的相邻数字a[i]-1,a[i]+1,之前是否已经出现了了。如果2者都已经出现,那么a[i]的出现可以合并两者,它对整个序列的贡献是-1,即它合并了两个段,令到原来的段数减1。如果2者只是出现了一个,那么a[i]可以并入它们当中连成一段,它对整个序列的贡献是0,即它没有使序列的段数增加。如果2者在之前都没有出现,那它就自成一段,它对整个串的贡献是1,即它令序列的段数增加了1
你会发现,如果要求得[1,r]这样的询问,就只需要求sum{val[1] …… val[r]};
但是对于要求[l,r]这样任意的询问,还要处理
- 我们读入全部的询问,并且对询问排序,按左端点升序排序
- 我们再次从左到右扫描整个串,这次做的是删除操作,并同时回答询问。
每在i这个位置时,先判断有没有询问的左端点是i,是的话就可以全部回答,这些询问,答案就是sum{val[i]……val[r]}
然后删除这个数字a[i],这里有个很关键的地方,删除了a[i]只会对a[i]-1和a[i]+1这两个数字有影响。因为删除了a[i],必然使段断开,变成了2个段,如果a[i]-1这个数字在i位置之后,它就会收到影响,同样的,如果a[i]+1这个数字在i位置之后,也会收到影响,它们的val值要+1,因为新增了一个段。
1 | sample |
总结整个过程就是
- 初始化得到val
- 删除一个数字x,要找到x+1和x-1并修改他们的val值,其实就是一个单点修改
- 对于查询,就是求区间的val值的和,就是区间求和
单点修改,区间求和,是树状数组和线段树的基本功能
树状数组代码
1 |
|
线段树
1 |
|