CSP 前学习珂学，祝自己 \(while(1)\ rp++\)。
考虑求解出每种数对答案的贡献。
设 \(t=r-l+1,k_x=\sum\limits_{i=l}^r [a_i=x]\)，由容斥得贡献为 \(x(2^t-2^{t-k_x})\)。
求解 \(k_x\)，考虑莫队，时间复杂度为 \(O(n\sqrt n)\)，这也是本题的复杂度上限。
由于 \(p\) 会变，所以不能用莫对维护 \(2^i\)。我们希望答案的计算次数级别为 \(O(\sqrt n)\)，考虑根号分治：
-
对于出现次数 \(\le \sqrt n\) 的数，我们用数组 \(num_i\) 统计，表示当前子串出现次数为 \(i\) 的数之和为多少。可以表示为： \(num_i=\sum\limits_{j=1}^{10^5}[k_j=i]\times j\)，时间复杂度 \(O(\sqrt n)\)。
-
对于出现次数 \(>\sqrt n\) 的数，我们直接维护它们的 \(k_i\)。由于这种数的个数级别为 \(O(\sqrt n)\)，所以也没问题。
现在只需要考虑快速幂的问题。普通快速幂肯定是不行了，时间复杂度会多一只 \(\log\)。考虑预处理可以给到 \(O(\sqrt n)\)，选择光速幂。
时间复杂度 \(O(\sqrt n)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,kl,a[N],l=1,r,ans[N];
struct que{int l,r,p,id;}q[N];
int cmp(que x,que y){
if(x.l/kl!=y.l/kl)
return x.l/kl<y.l/kl;
if(x.l/kl%2) return x.r>y.r;
return x.r<y.r;
}int pw1[N],pw2[N],p;
void init(int c){
p=c,pw1[0]=pw2[0]=1;
for(int i=1;i<=kl;i++)
pw1[i]=pw1[i-1]*2%p;
for(int i=1;i<=kl;i++)
pw2[i]=pw2[i-1]*pw1[kl]%p;
}int kpow(int y){
return pw1[y%kl]*pw2[y/kl]%p;
}int num[N],sum[N],vis[N],b[N],id;
void add(int x){
sum[x]++;
if(vis[x]) return;
num[sum[x]-1]-=x;
num[sum[x]]+=x;
}void del(int x){
sum[x]--;
if(vis[x]) return;
num[sum[x]+1]-=x;
num[sum[x]]+=x;
}signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m,kl=sqrt(n)+1;
for(int i=1;i<=n;i++)
cin>>a[i],num[a[i]]++;
for(int i=1;i<=1e5;i++){
if(num[i]>kl)
b[++id]=i,vis[i]=1;
num[i]=0;
}for(int i=1;i<=m;i++)
cin>>q[i].l>>q[i].r>>q[i].p,q[i].id=i;
sort(q+1,q+m+1,cmp);
for(int i=1;i<=m;i++){
init(q[i].p);int ij=q[i].id;
while(r<q[i].r) add(a[++r]);
while(r>q[i].r) del(a[r--]);
while(l>q[i].l) add(a[--l]);
while(l<q[i].l) del(a[l++]);
for(int j=1;j<=id;j++)
ans[ij]=(ans[ij]+b[j]*(kpow(r-l+1)-kpow(r-l+1-sum[b[j]])))%p;
for(int j=1;j<=kl;j++)
ans[ij]=(ans[ij]+num[j]*(kpow(r-l+1)-kpow(r-l+1-j)))%p;
ans[ij]=(ans[ij]+p)%p;
}for(int i=1;i<=m;i++)
cout<<ans[i]<<"\n";
return 0;
}