[DS记录]P5072 [Ynoi2015] 盼君勿忘
command_block
2021-06-30 16:17:26
**题意** ： 给出序列 $A$ ，每次查询区间 $[l,r]$ 的所有子序列分别去重后的和 $\bmod\ p$。
这里的 $p$ 每次询问单独给定，不保证是质数。
允许离线，$n,m\leq 10^5$ ，时限$\texttt{3s}$。
------------
分别考虑每个数的贡献。若在一个长度为 $L$ 的区间中数 $x$ 出现了 $k$ 次，则贡献为 $x(2^L-2^{L-k})$。
由于每次的 $p$ 都不同，势必要单独计算每个 $2^L-2^{L-k}$。
对于每个询问，首先用光速幂预处理，即可 $O(\sqrt{n})-O(1)$ 求解 $2^k$。
考虑根号分治。
记 $s_k$ 为出现 $k$ 次的数的总和，对于出现次数 $\leq \sqrt{n}$ 的数，计算 $\sum_{k=1}^{\sqrt{n}}s_k(2^L-2^{L-k})$。
对于出现次数 $>\sqrt{n}$ 的数，只有 $O(\sqrt{n})$ 个，暴力维护其出现次数。
使用莫队即可维护上述信息，复杂度 $O(n\sqrt{n})$。（$n,m$ 同阶）
代码很好写。
```cpp
#include<algorithm>
#include<cstdio>
#include<cmath>
#define ll long long
#define MaxN 100500
using namespace std;
const int lim=100000;
ll s[505];
int o[MaxN],a[MaxN],cnt[MaxN],BS;
inline void add(int x){
if (cnt[x]>BS){++o[x];return ;}
s[o[x]]-=x;s[++o[x]]+=x;
}
inline void del(int x){
if (cnt[x]>BS){--o[x];return ;}
s[o[x]]-=x;s[--o[x]]+=x;
}
struct Data{int l,r,mod,p;}b[MaxN];
bool cmp(const Data &A,const Data &B)
{return A.l/BS==B.l/BS ? (A.l/BS)&1 ? A.r<B.r : A.r>B.r : A.l<B.l;}
int n,m,ans[MaxN],mod
,st[505],tn,pw1[505],pw2[505];
int pow2(int n)
{return 1ll*pw2[n/BS]*pw1[n%BS]%mod;}
int main()
{
scanf("%d%d",&n,&m);
BS=sqrt(n)+1;
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
cnt[a[i]]++;
}
for (int i=1;i<=lim;i++)
if (cnt[i]>BS)st[++tn]=i;
for (int i=1;i<=m;i++){
scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].mod);
b[i].p=i;
}
sort(b+1,b+n+1,cmp);
int l=1,r=0;
for (int i=1;i<=m;i++){
while(b[i].l<l)add(a[--l]);
while(r<b[i].r)add(a[++r]);
while(l<b[i].l)del(a[l++]);
while(b[i].r<r)del(a[r--]);
mod=b[i].mod;
pw1[0]=pw2[0]=1;
for (int i=1;i<=BS;i++)pw1[i]=(pw1[i-1]<<1)%mod;
for (int i=1;i<=BS;i++)pw2[i]=1ll*pw2[i-1]*pw1[BS]%mod;
int len=r-l+1,ret=0;ll ret2=0;
for (int i=1;i<=tn;i++){
int x=st[i];
ret=(ret+1ll*x*pow2(len-o[x]))%mod;
ret2+=x;
}
for (int c=1;c<=BS;c++){
ret=(ret+1ll*s[c]*pow2(len-c))%mod;
ret2+=s[c];
}
ans[b[i].p]=(ret2%mod*pow2(len)-ret+mod)%mod;
}
for (int i=1;i<=m;i++)
printf("%d\n",ans[i]);
return 0;
}
```