区间内不同的数

· · 个人记录

· 求区间内不同的数的个数

记pre[i]表示序列中i位置上的数在它之前最后一次出现的位置，即使得a_j=a_i,j<i成立的最大的j

那么[l,r]区间内不同的数的个数就是pre小于l的数的个数，如果pre大于等于l，则说明这个数在这个区间里不是第一次出现，没有贡献

实现可以用主席树

升级小应用

权值范围为[1,k]的序列，求[l,r]区间是否出现过所有数字。

等等，如果$[l,n]$不存在某种权值岂不是查不出来？单独记录下每种权值在整个序列最后一次出现的位置，并维护这个的最小值，若有最晚出现位置小于$l$的权值，那么$[l,r]$中也一定没有出现过所有数字。 #### **·** 求区间内不同的数的乘积/和 原理同上，注意也要将询问区间转换成$[1,r]$的答案消去$[1,l-1]$的答案，多在主席树上维护一些东西 然后讲一道神仙题对此的应用 JZPLCM 给定一个长度为$n$序列$a$,$Q$次询问区间内数的最小公倍数 $n,Q\le 100000,a_i \le 10^9

题解:将每个数质因数分解，并求出对于每个质因子p的指数q。那么我们要求的LCM就是对于每个质因子在这个区间内求一个q=max(q_i),l\le i\le r，拥有p^q的贡献。

然而区间内的不同质因子的个数会很多，显然不能枚举质因子做这件事情。我们这里有一个巧妙的转化，即我们只关心每个质因子在这个区间应该要有p^q的贡献，如何处理出这种贡献呢？对于一个数质因子分解后的一个质因子p^q,我们就将这个数拆成q个数,分别是p,p^2,p^3,p^4,\dots,p^q，然后每个数拥有权值p。现在我们的问题转化成，给定一个序列，每个位置上有两个数a_i,b_i，每次询问一个区间求

考虑这样做后一个区间如果LCM的某个质因子的指数是$q$，那么必定在这个区间里存在$q$个不同的数的权值是$p$，而他们的乘积恰好是$p^q$，完美解决了问题。并且原序列中每个数至多只会被分解成$log$个数，复杂度为$O(Nlog^2N+QlogN)$。 小结一下，对于不同的数的求法，维护这个权值当前最后一次出现的位置极其关键，还有很多这种思想的应用，先写这么多吧。 p.s.话说好像这一类题目都能莫队离线做(逃 相关题目:luoguP4137,P4632 https://www.luogu.org/blog/qlwpc/apio2018-xin-jia