Ynoi 盼君勿望
1.1 前言
在太阳西斜的这个世界里，置身天上之森，等这场战争结束之后，等这场战争结束之后，人人本着正义之名，长存不灭的过去，逐渐消逝的未来，我回来了，纵使日薄西山，即使看不到未来，此时此刻的光辉，盼君勿忘，世界上最幸福的女孩
珂朵莉要永远幸福的呀~
题目链接。
1.2 题目描述
珂朵莉给了你一个序列，每次查询一个区间 \([l,r]\) 中所有子序列分别去重后的和 \(\bmod\ p\)。
输入格式
第一行两个整数 \(n,m\)。
第二行 \(n\) 个整数表示这个序列。
之后 \(m\) 行，每行三个整数 \(l,r,p\) 表示查询的区间与模数。
输出格式
\(m\) 行，每行输出一个整数表示答案。
样例 #1
样例输入 #1
5 5
1 2 2 3 4
1 2 233333
2 3 333333
1 5 5
3 5 15
2 4 8
样例输出 #1
6
6
1
6
0
提示
Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477
对于 \(100\%\) 的数据，\(1\leq n,m,a_i \leq 10^5\)，\(1\leq p\leq 10^9\)，\(1\leq l\leq r\leq n\)。
1.3 前置知识——莫队
我们一旦看到区间问题，自然而然的就想到了莫队（本蒟蒻也是刚学）不了解都可以看看 Oi-wiki，上面有详细解答，我们贴一段莫队算法的时间复杂度证明过来，不然有些同学一看到莫队就说它很暴力（恼）。
Oi-wiki莫队链接：Link
时间复杂度证明（Oi-wiki）
证：令每一块中 L 的最大值为 \(\max_1,\max_2,\max_3, \cdots , \max_{\lceil\sqrt{n}\rceil}\)。
由第一次排序可知，\(\max_1 \le \max_2 \le \cdots \le \max_{\lceil\sqrt{n}\rceil}\)。
显然，对于每一块暴力求出第一个询问的时间复杂度为 \(O(n)\)。
考虑最坏的情况，在每一块中，\(R\) 的最大值均为 \(n\)，每次修改操作均要将 \(L\) 由 \(\max_{i - 1}\) 修改至 \(\max_i\) 或由 \(\max_i\) 修改至 \(\max_{i - 1}\)。
考虑 \(R\)：因为 \(R\) 在块中已经排好序，所以在同一块修改完它的时间复杂度为 \(O(n)\)。对于所有块就是 \(O(n\sqrt{n})\)。
重点分析 \(L\)：因为每一次改变的时间复杂度都是 \(O(\max_i-\max_{i-1})\) 的，所以在同一块中时间复杂度为 \(O(\sqrt{n}\cdot(\max_i-\max_{i-1}))\)。
将每一块 L 的时间复杂度合在一起，可以得到：
对于 L 的总时间复杂度为
（裂项求和）
由题可知 \(\max_{\lceil\sqrt{n}\rceil}\) 最大为 n，所以 L 的总时间复杂度最坏情况下为 \(O(n\sqrt{n})\)。
1.4 光速幂
由于 \(Ynoi\) 系列是由清华大学教授 lxl 编写的，所以数据十分的毒瘤，会卡我们许多东西，所以，我们要保证在最短的时间内完成\(幂\)的操作，大家可以先看看百度，再来理解下面的代码讲解：
我们求 \(2^n\) 幂时，可以把它拆成很多个幂，当然要预处理，然后就能做到在 \(O(1)\) 时间内把幂求出来，代码如下：
预处理代码
inline void chuli(int mod)
{
f[0][0] = 1;
for(int i = 1;i <= bl;i ++ ) f[i][0] = 2ll * f[i - 1][0] % mod;
f[0][1] = 1;
for(int i = 1;i <= bl;i ++ ) f[i][1] = 1ll * f[i - 1][1] * f[bl][0] % mod;
}
幂代码
inline ll query(int x, int mod){
return f[x % bl][0] * f[x / bl][1] % mod;
}
2.1 题目分析
设当前区间为 \(l、r\)，值 v 在 \(l、r\) 内的出现次数为 \(cnt_v\)
顺便补充一点，莫队是以 \(l\) 为第一关键词，\(r\) 为第二关键词。
我们画图举例：
我们要排区间 \([1,3]\)，转换得 \([1,3]\)（左边为区间，右边为位置）
我们要拍区间 \([1,6]\)，转换得 \([1,6]\)；
我们要排区间 \([6]\)，转换得 \([6]\)。
所以排序顺序应该是：\(② -> ① -> ③\)。
\(cnt\) 为一个桶。
很难直接求去重后包含值 \(k\) 的子序列个数，不妨稍加转化。如果将这些子序列中的 \(k\) 删除，则这些子序列中一定不出现 \(k\)。容易看出 \(l、r\) 内不包含 \(k\) 的子序列个数共有 \(2^{r-l + 1 -cnt_k}\) 个。这意味着包含值 k 的子序列共有 \(2^{r-l + 1-2^r-l+ 1-cnt_k}\) 个。出现次数直接用普通莫队维护即可，复杂度是 \(O(n\sqrt{q})\)。
对于出现次数相同的值，我们可以将它们的贡献一起统计。这里的实现可以维护一个针对出现次数的值域双向链表，每次从当前的出现次数开始向下一个存在的出现次数跳。双向链表的插入和删除可以 \(O(1)\) 做。显然询问的复杂度和值出现次数的个数有关，又易知对于不同的值出现次数，其个数是 \(O(\sqrt{n})\) 的。所以这一部分的复杂度是 \(O(q\sqrt{n})\)。
我们要求子序列的长度 \(len\)，不妨把它看为 \(x\) 的贡献，那 \(x\) 的贡献数量就是 \(tong_x * (2 ^ {len} - 2 ^ {len - tong_x})\)
3.1 代码实现
代码十分长，写了 \(4\) 个多小时，就是一个普通莫队板子 + 光速幂。
代码运行时间 22.78ms
代码长度 2.41KB
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
template<typename T>
T read(T x)
{
T opt = 1, tong = 0;
char ch = getchar();
while(!isdigit(ch)){
opt = (tong == '-') ? -1 : 1, ch = getchar();
}
while( isdigit(ch)){
tong = (tong << 1) + (tong << 3) + (ch ^ 48), ch = getchar();
}
return opt * tong;
}
#define read read(0)
int n, m;
int bl;
const int N = 1e5 + 5;
int a[N];
ll ans[N];
int pre[N], nxt[N];
int cnt[N];
int bel[N];
ll tongg[N];
ll f[N + 10][2];
struct node
{
int l, r, m, id;
bool operator < (const node &rhs) const
{
if(bel[l] ^ bel[rhs.l]) return bel[l] < bel[rhs.l];
return (bel[l] & 1 ? r < rhs.r : r > rhs.r);
}
}q[N];
int tot;
inline void ins(int x)
{
nxt[tot] = x;
pre[x] = tot;
tot = x;
}
inline void erase(int x)
{
if(x == tot)
{
nxt[pre[x]] = 0;
tot = pre[x];
}
else
{
nxt[pre[x]] = nxt[x];
pre[nxt[x]] = pre[x];
}
pre[x] = 0;
nxt[x] = 0;
}
inline void add(int x)
{
tongg[cnt[a[x]]] -= a[x];
if(!tongg[cnt[a[x]]])
erase(cnt[a[x]]);
cnt[a[x]] ++;
if(!tongg[cnt[a[x]]])
ins(cnt[a[x]]);
tongg[cnt[a[x]]] += a[x];
}
inline void delta(int x)
{
tongg[cnt[a[x]]] -= a[x];
if(!tongg[cnt[a[x]]])
erase(cnt[a[x]]);
cnt[a[x]] -- ;
if(!tongg[cnt[a[x]]])
ins(cnt[a[x]]);
tongg[cnt[a[x]]] += a[x];
}
inline void chuli(int mod)
{
f[0][0] = 1;
for(int i = 1;i <= bl;i ++ )
f[i][0] = 2ll * f[i - 1][0] % mod;
f[0][1] = 1;
for(int i = 1;i <= bl;i ++ )
f[i][1] = 1ll * f[i - 1][1] * f[bl][0] % mod;
}
inline ll query(int x, int mod){
return f[x % bl][0] * f[x / bl][1] % mod;
}
int main()
{
n = read, m = read;
int block = n / sqrt(m);
bl = block + 1;
for(int i = 1;i <= n;i ++ ) {
a[i] = read;
bel[i] = (i - 1) / block + 1;
}
for(int i = 1;i <= m;i ++ ){
q[i].l = read, q[i].r = read, q[i].m = readl;
q[i].id = i;
}
sort(q + 1,q + 1 + m);
int l = 1, r = 0;
for(int i = 1;i <= m;i ++ ){
// cout << 'j';
while(r < q[i].r) add(++ r);
while(l > q[i].l) add(-- l);
while(l < q[i].l) delta(l ++ );
while(r > q[i].r) delta(r -- );
int len = r - l + 1;
chuli(q[i].m);
for(int j = nxt[0];j ;j = nxt[j]){
ll v = tongg[j] * (query(len, q[i].m) - query(len - j, q[i].m) + q[i].m) % q[i].m;
ans[q[i].id] = (ans[q[i].id] + v) % q[i].m;
}
}
for(int i = 1;i <= m;i ++ ){
printf("%lld\n", ans[i]);
}
return 0;
}