[BZOJ 2743] [HEOI 2012] 采花

树状数组 + 差分

看上去就像莫队算法。

然后发现数据有点大......算了。

可以发现每种花只有当前区间中的第二枝对后面有贡献。则计算答案可以利用差分方法:若在 pos 位置的一束花能对后方产生贡献,则在树状数组中将 [pos, n] 区间 +1。最终此时某个区间答案即为区间和。

记录下位置 i 后第一次出现该位置颜色花的位置 nxt[i]。考虑从一个区间 [L, R] 到另一个区间 [L+1, R] 答案的变化:既然位置 L 处的花退出了区间,那么花 i 对答案的影响也要被去除,即在树状数组中把 [L, n] 答案 -1。原本 nxt[i] 位置的花是区间内第二朵花,现在也变成了第一朵,因此更新答案,[nxt[i], n] 区间 +1。

既然知道了相邻区间的转移,那么整体的做法也可以明确了:先将读入的所有区间按左端点排序,然后按刚才的方法在左端点间一位一位转移,答案就是区间和了。

代码如下:

继续阅读[BZOJ 2743] [HEOI 2012] 采花