题目链接
题意分析
插点题外话
我感觉我已经不可能再获得幸福了
因为
我已经被幸福包围了
珂朵莉，欢迎回家
每一次做这种题面都会泪目的
由于这种题只存在询问 所以我们不自觉的想到了莫队
首先 如果区间[l,r]中的一个数x出现了k次的话 那么ta在所有子序列里面出的次数就是(2^{r-l+1}-2^{r-l+1-k})
然后的话 我们使用莫队 维护每一个数x出现了的次数k 出现k次的数的和 区间里面所有的k
每一个数x出现了的次数k：由于(a_i≤10^5) 所以我们直接开桶维护就可以了 离散化都不带的
出现k次的数的和：我们也可以直接使用数组维护 但是需要注意的是为了防止重复 我们需要在每一次修改次数的时候进行特判
区间里面所有的k：这里的话也是需要去重的 我们可以使用一个叫做unordered_set的东西加以维护 就像set一样具有insert，erase，find等操作
跟set相比 unordered_set正如其名 不存在有序性 这里也不需要什么有序性 所以可以当作一个可去重的数组来使用
然后的话 我们直接通过unorder_set里面的k进行答案的累加就可以了
等一下 你觉得这样的话 就可以过了吗？
这题是需要卡常数的看在珂朵莉的面子上我就不追究了
卡常数技巧：
1.莫队排序的奇偶优化
struct Node
{
int le,ri,id;
long long mod;
friend bool operator <(const Node &A,const Node &B)
{
if(bel[A.le]^bel[B.le]) return A.le<B.le;
else return (bel[A.le]&1) ? A.ri<B.ri : A.ri>B.ri;
}
}e[N];
2.求2的指数幂时的优化
由于这里指数的最高上限是n 所以我们可以考虑一下(sqrt{n})预处理求指数幂
就是(2^x=2^{frac{x}{sqrt{n}}×sqrt{n}+x\%sqrt{n}})
//sq=sqrt(n);
long long getpow(int x,long long p)
{return (qpow[(x/sq)*sq]*qpow[x%sq])%p;}
for(int j=1;j<=sq;++j) qpow[j]=qpow[j-1]*2LL%e[i].mod;
for(int j=2;j*sq<=(e[i].ri-e[i].le+1);++j)
3.undered_set的使用
为什么我们使用unordered_set而不使用set
由于跟set相比 unordered_set更像是一个散列表 所以insert、erase以及find的平均复杂度相比于set来讲优秀很多
自然也就成为了一个卡常数技巧
CODE：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<unordered_set>
#define N 100080
using namespace std;
int n,q,tot,sq;
int num[N],vis[N],bel[N];
long long qpow[N],sum[N],ans[N];
unordered_set<int> allsum;
struct Node
{
int le,ri,id;
long long mod;
friend bool operator <(const Node &A,const Node &B)
{
if(bel[A.le]^bel[B.le]) return A.le<B.le;
else return (bel[A.le]&1) ? A.ri<B.ri : A.ri>B.ri;
}
}e[N];
long long getpow(int x,long long p)
{return (qpow[(x/sq)*sq]*qpow[x%sq])%p;}
void add(int x)
{
if(vis[num[x]])
{
sum[vis[num[x]]]-=num[x];
if(!sum[vis[num[x]]]) allsum.erase(vis[num[x]]);
}
vis[num[x]]++;
if(!sum[vis[num[x]]])
{
sum[vis[num[x]]]+=num[x];
allsum.insert(vis[num[x]]);
}
else sum[vis[num[x]]]+=num[x];
}
void del(int x)
{
sum[vis[num[x]]]-=num[x];
if(!sum[vis[num[x]]]) allsum.erase(vis[num[x]]);
vis[num[x]]--;
if(!vis[num[x]]) return;
if(!sum[vis[num[x]]])
{
sum[vis[num[x]]]+=num[x];
allsum.insert(vis[num[x]]);
}
else sum[vis[num[x]]]+=num[x];
}
void solve()
{
int lenow=1,rinow=0;
for(int i=1;i<=q;++i)
{
qpow[0]=1LL;
for(int j=1;j<=sq;++j) qpow[j]=qpow[j-1]*2LL%e[i].mod;
for(int j=2;j*sq<=(e[i].ri-e[i].le+1);++j)
qpow[j*sq]=qpow[(j-1)*sq]*qpow[sq]%e[i].mod;
while(rinow<e[i].ri) add(++rinow);
while(lenow>e[i].le) add(--lenow);
while(lenow<e[i].le) del(lenow++);
while(rinow>e[i].ri) del(rinow--);
for(unordered_set<int>::iterator key=allsum.begin();key!=allsum.end();++key)
{
int now=*key;
ans[e[i].id]=(ans[e[i].id]+sum[now]*(getpow(rinow-lenow+1,e[i].mod)-getpow(rinow-lenow+1-now,e[i].mod)+e[i].mod)%e[i].mod)%e[i].mod;
}
}
}
int main()
{
scanf("%d%d",&n,&q);sq=(int)sqrt(1.0*n);
for(int i=1;i<=n;++i) scanf("%d",&num[i]);
for(int i=1;i<=n;++i) bel[i]=(i/sq)+1;
for(int i=1;i<=q;++i)
{
scanf("%d%d%lld",&e[i].le,&e[i].ri,&e[i].mod);
e[i].id=i;
}
sort(e+1,e+q+1);
solve();
for(int i=1;i<=n;++i)
printf("%lld
",ans[i]);
return 0;
}