P1494 [国家集训队] 小Z的袜子 解题笔记

题目来源 P1494 [国家集训队] 小 Z 的袜子 题意简述 有一个长度为 nnn 的序列 {ci}\{c_i\}{ci​}。现在给出 mmm 个询问，每次给出两个数 l,rl,rl,r，从编号在 lll 到 rrr 之间的数中随机选出两个不同位置的数，求两个数相等的概率。 n,m≤5×104,ci≤nn,m\le5\times10^4,c_i\le nn,m≤5×104,ci​≤n 解题思路 本题保证 ci≤nc_i\le nci​≤n 。事实上，如果不满足这个条件，我们也可以对序列做离散化操作，因为数字的绝对大小与解题无关。 cic_ici​ 的值域相当有限，于是便可以考虑用桶来维护区间中不同数字的数量。 每次移动区间端点后，只需要考虑新加进来的这个数和前面的数相等的概率是多少，经过某些 O(1..