首页 > 小Z的袜子
开通博客写题解
头像 louhc
发表于 2019-08-20 18:27:01
思路 莫队基础题.对于每个区间,设颜色的出现次数为,答案就是,分子的意义是任意选两只袜子,颜色相同的对数(可重复选,与顺序有关)减去重复选同一只的情况.莫队维护.加入一个数,减去加入前该数出现次数的平方,加上加入后该数出现次数的平方,删去一个数则恰恰相反.因为是以前写的代码,计算时分子分母先除了个2 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 codesonic
发表于 2019-09-02 21:29:16
简要题意 给定一个长度为n的序列，每次询问一个区间[l,r]中，随机抽取两个数字，这两个数字相同的概率 既然是静态的，不妨考虑莫队。我们发现这题的性质满足莫队所需的性质，我们只需要考虑状态的转移，即插入一个点和删除一个点即可 考虑一个颜色对答案的贡献，设s[i]表示区间内第i种颜色的数量，很容易推出 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”