[Ynoi2016]镜中的昆虫题解好题值得一做。题目大意：给一个序列，有若干个离线询问，每次可以区间推平或询问区间内的颜色个数，数据范围是\(10^5\)级别。解题思路：我们可以先考虑一个弱化版，每次是单点修改怎么做，类似于CF848C。我们考虑维护出每一个位置上一个与它相等的位置是\(p

洛谷P4688[Ynoi2016]掉进兔子洞莫队配合bitset例题。lxl官方题解。https://olddrivertree.blog.uoj.ac/blog/4690想到如果只有每个数只出现一次怎么做，可以莫队移动区间用bitset维护每个数的是否出现，再对\(3\)个区间进行与操作就是交集出现的数。但是这只能求出数字

[Ynoi2016]镜中的昆虫简化题意给定长为\(n\)序列\(a\),两种操作\(m\)次:1lrx:将\([l,r]\)修改为\(x\)2lr:查询\([l,r]\)出现了多少种不同的数\(n,m\le10^5\)题解\(A\)这道题还是很不容易的，起码用了几天的时间。思路也是换了又换，从分块

思路：首先可以先考虑没有换根的情况。先将树拍到dfn序上，那么一个子树\(u\)的所有点的dfn序区间为\([dfn_u,dfn_u+siz_u-1]\)。那么询问变为：每次给定两个区间\([l_1,r_1],[l_2,r_2]\)，对于在第一个区间内的点\(x\)和在第二个区间的点\(y\)，若\((x,y)\)有贡献，当且仅

难度在最近遇到的题里相对较高，在这里写一篇珂学题解。（以下是学校给的部分分）\(20\%\)：直接暴力枚举。另外\(20\%\)：假如我们取\(pre\)，对于\(pre<l\)的，\(ans++\)，明显二维偏序，树状数组或\(cdq\)即可，时间复杂度\(O(n\logn)\)。另外\(40\%\)：相当于多加一个时间维，三维偏序，\(

P4690Ynoi2016镜中的昆虫原题不会见祖宗。前置珂朵莉树、cdq分治、树状数组思路单点修改区间查询定义\(pre_i\)表示\(col_i\)的前一个一样颜色的位置，那么对于一段区间查询\([l,r]\)，我们只需要查询有区间内有多少个\(pre_i<l\)。每次修改时就相当于修改四个同颜色

P4688Ynoi2016掉进兔子洞经典莫队加bitset。思路不难发现最终答案就是：\[(r_1-l_1+1)+(r_2-l_2+1)+(r_3-l_3+1)-3\timessize\]其中\(size\)表示3个区间内出现了多少个公共元素。看到这么多区间，不妨有把区间拆下来搞莫队的想法。先不考虑询问个数的限制，我们考虑使用

视频链接：C117莫队配合bitsetP4688[Ynoi2016]掉进兔子洞_哔哩哔哩_bilibili   LuoguP4688[Ynoi2016]掉进兔子洞//莫队配合bitsetO(n*sqrt(n))#include<iostream>#include<cstring>#include<algorithm>#include<cmath>#include<bitset>usin

P4690[Ynoi2016]镜中的昆虫本质就是区间修改，区间数颜色弱化一下，先考虑不带修的情况，也就是P1972[SDOI2009]HH的项链其难点在于区间颜色的去重，需要想一个办法让区间内一个颜色只被数一次我们可以去维护一个\(Nxt\)数组，表示下一个与当前位置颜色相同的位置若当前位

题目链接：镜中的昆虫经典题了，我们首先回顾下颜色数的常见做法统计：对每个位置维护一个\(pre_i\)，表示与当前位置相同的颜色上一次出现位置。那么我们分讨一下。查询\([l,r]\)得到颜色数，对于\(pre_i<l\)的\(i\)点，显然它就是这个区间内\(a_i\)对应颜色出现的第一个位置，我们

题意给定长度为\(n\)的序列\(s\)。有\(m\)个询问，每次询问三个区间，把三个区间中同时出现的数一个一个删掉，问最后三个区间剩下的数的个数和，询问独立。Sol不难发现答案即为求：\(r1-l1+r2-l2+r3-l3+3-siz\)。其中\(siz\)表示三个区间的公共颜色的个数。仔细

64MB,1.5s题目描述您正在欣赏galgame的HS，然后游戏崩溃了，于是您只能做数据结构题了：维护一个长为 \(n\) 的序列 \(a_i\)，有 \(m\) 次操作。将区间 \([l,r]\) 的值修改为 \(x\)。询问区间 \([l,r]\) 出现了多少种不同的数，也就是说同一个数出现多次只算一个。

题目传送门soltion简单题换根显然可以拆成\(O(1)\)个区间，这里先不管。直接做法是莫队，把双子树拆成\(dfs\)序上的双前缀，可以直接莫队，但是常数比较大。另一种做法是根分，对颜色出现次数分治，大于的求出\(dfs\)序的前缀和即可，小于的因为一共只有\(O(n\sqrtn)\)个点对，所以

P4690[Ynoi2016]镜中的昆虫题解题意维护一个长为 \(n\) 的序列 \(a_i\)，有 \(m\) 次操作。将区间 \([l,r]\) 的值修改为 \(x\)。询问区间 \([l,r]\) 出现了多少种不同的数，也就是说同一个数出现多次只算一个。题解感觉这道题还是比较有意思的,像是一堆套路

RE了大约12次以后，SoN3ri告诉我是bitset开小了。那你为什么全RE了啊（？题意是给你一个长度为\(n\)的序列，一共\(m\)次询问，每次询问包含三个区间，求三个区间内相同的数去掉后剩下的数的个数。做完了小清新人渣的本愿，看啥都是bitset+莫队，这题我也是一开始打了一个莫队+bitset，但是

\(\text{Solution}\)莫队配合\(\text{bitset}\)发现答案困难的部分在于同一个数在三个区间出现次数的最小值考虑强行拆开看，用莫队处理出每个区间每个数的出现次数，这个

题目传送门已经能过hack，原因：做快速幂的时候需要微判一下边界。很好奇lxl为什么不卡显然区间加可用线段树做。然后操作二用扩展欧拉定理，每个\(p\)最多递归\(\log\)