[BZOJ2120/Luogu1903]数颜色(莫队算法)

发布于 2018-02-05  201 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2120/Luogu1903]数颜色(莫队算法)

Description

墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求,你知道你需要干什么了吗?

Http

BZOJ
Luogu

Tag

莫队算法,离线

解决思路

莫队算法把询问离线下来,排序后移动左右指针得到答案。
但这里有修改操作,怎么办呢?
可以在把询问左右区间离线下来的同时记录时间,记录是第一个修改操作后的,那么回答询问的时候再移动时间指针,把要修改的修改掉,不要修改的改回去。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2120/Luogu1903]数颜色(莫队算法)


HNCJ OIer