luogu P4690 [Ynoi2016] 镜中的昆虫 题解
P4690 [Ynoi2016] 镜中的昆虫 题解
题意
维护一个长为 \(n\) 的序列 \(a_i\)，有 \(m\) 次操作。
-
将区间 \([l,r]\) 的值修改为 \(x\)。
-
询问区间 \([l,r]\) 出现了多少种不同的数，也就是说同一个数出现多次只算一个。
题解
感觉这道题还是比较有意思的,像是一堆套路被集合了起来,但难写是真的难写,细节是真的多。
区间数颜色
以前我写区间数颜色是只算最右边的,然后修改前驱,但是这样写并不好扩展。
我们只计算最左边的,只我们记\(i\)的前驱为\(pre_i\),前驱是前面第一个和自己相同的数字。
然后扫描线统计区间中\([l,r]\)中\(pre_i\)为\([0,l-1]\)的个数,这其实是一个矩阵查询。
这其实是一个经典的二维数点问题,将\((i,pre_i)\)看做一个点,相当于查询\((x,y)(l\leq x \leq r)(0 \leq y \leq l-1)\)的点个数。
运用二维差分的知识将一个询问拆成\(4\)个,然后跑二维偏序即可,可能画图会直观一些,但是懒。
单点带修数颜色
也就是[BalkanOI2007] Mokia 摩基亚这道题。
多引入一维时间\(t\),给每一个点设置加入时间,询问设置询问时间,一个点会被统计当且仅当\(x,y,t\)都小于时才会被统计。
修改一个点可以改为插入一个点和删除一个点,修改一个点还要修改后继的前驱等,比较麻烦。
区间带修数颜色
其实对于上面的操作并不是进阶很多,我们将由于有区间推平操作,想到珂朵莉树,一个区间看做一个一个颜色段,每次修改发现只会对颜色端的两端有影响,只有颜色段两端的\(pre_i\)会被修改。
而我们知道只有修改的珂朵莉树操作次数是 n+m 级别的,所以实际上修改的并不是很多,给每一个颜色开一个珂朵莉树,给原序列开一颗珂朵莉树进行维护就行了。
一些卡常小建议:
- 三维偏序中结构体只需要存4个,多的放外面,可以加快排序速度。
- 比较短的,可以展开的函数加上
inline。 - 在三维偏序中最后一层不需要排序。