评测机更新了还是过不掉 这常数怕不是1e9的
求大佬卡常
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <cstdio>
#include <algorithm>
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
register char c=getchar();
register int x=0;
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-48;c=getchar();}
return x;
}
struct ostream{
char buf[8000005],*s;
inline ostream(){s=buf;}
inline ostream&operator<<(register int d){
if(!d){
*s++='0';
}else{
static int w;
for(w=1;w<=d;w*=10);
for(;w/=10;d%=w)*s++=d/w^'0';
}
return*this;
}
inline ostream&operator<<(const char&c){*s++=c;return*this;}
inline void flush(){
fwrite(buf,1,s-buf,stdout);
s=buf;
}
inline~ostream(){flush();}
}cout;
int sq=317;
int pre[100005],nxt[100005],hd;
inline void L_add(int x)
{
pre[x]=0;
nxt[x]=hd;
pre[hd]=x;
hd=x;
}
inline void L_del(int x)
{
if(x==hd)
{
pre[nxt[x]]=-1;
hd=nxt[x];
}
else
{
nxt[pre[x]]=nxt[x];
pre[nxt[x]]=pre[x];
}
}
struct node
{
int l,r,id;
long long mod;
}q[100005];
int n,m,a[100005],cnt[100005],ans[100005],sum[100005],area[100005];
inline bool cmp(node p,node q) {
return((area[p.l]^area[q.l])?area[p.l]<area[q.l]:(area[p.l]&1?p.r<q.r:q.r<p.r));
}
int pw1[320],pw2[320];
inline long long ksm2(int x,int mod) {
return 1ll*pw2[x/sq]*pw1[x%sq]%mod;
}
int main()
{
hd=0;
n=read();m=read();
for(register int i=1;i<=n;++i)
{
a[i]=read();
area[i]=(i-1)/sq+1;
}
for(register int i=1;i<=m;++i)
{
q[i].id=i;
q[i].l=read();
q[i].r=read();
q[i].mod=read();
}
sort(q+1,q+m+1,cmp);
register int l=q[1].l,r=l-1;
for(register int i=1;i<=m;++i)
{
pw1[0]=pw2[0]=1;
for(register int j=1;j<=sq;++j) pw1[j]=(pw1[j-1]<<1)<q[i].mod?(pw1[j-1]<<1):(pw1[j-1]<<1)%q[i].mod;
for(register int j=1;j<=sq;++j) pw2[j]=1ll*pw2[j-1]*pw1[sq]%q[i].mod;
while(r<q[i].r)
{
++r;
if(cnt[a[r]])
{
sum[cnt[a[r]]]-=a[r];
if(!sum[cnt[a[r]]]) L_del(cnt[a[r]]);
}
++cnt[a[r]];
if(!sum[cnt[a[r]]]) L_add(cnt[a[r]]);
sum[cnt[a[r]]]+=a[r];
}
while(r>q[i].r)
{
sum[cnt[a[r]]]-=a[r];
if(!sum[cnt[a[r]]]) L_del(cnt[a[r]]);
--cnt[a[r]];
if(cnt[a[r]])
{
if(!sum[cnt[a[r]]]) L_add(cnt[a[r]]);
sum[cnt[a[r]]]+=a[r];
}
--r;
}
while(l<q[i].l)
{
sum[cnt[a[l]]]-=a[l];
if(!sum[cnt[a[l]]]) L_del(cnt[a[l]]);
--cnt[a[l]];
if(cnt[a[l]])
{
if(!sum[cnt[a[l]]]) L_add(cnt[a[l]]);
sum[cnt[a[l]]]+=a[l];
}
++l;
}
while(l>q[i].l)
{
--l;
if(cnt[a[l]])
{
sum[cnt[a[l]]]-=a[l];
if(!sum[cnt[a[l]]]) L_del(cnt[a[l]]);
}
++cnt[a[l]];
if(!sum[cnt[a[l]]]) L_add(cnt[a[l]]);
sum[cnt[a[l]]]+=a[l];
}
for(register int j=hd;j;j=nxt[j])
{
ans[q[i].id]=(ans[q[i].id]+sum[j]*((ksm2(r-l+1,q[i].mod)-ksm2(r-l+1-j,q[i].mod))%q[i].mod+q[i].mod)%q[i].mod)%q[i].mod;
}
}
for(register int i=1;i<=m;i++)
{
cout<<ans[i]<<'\n';
}
return 0;
}
无奈 好几天了都卡不过去