rt，感觉没什么错误啊！

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;

struct ask
{
	int l,lx,r,id,p;
}pro[100005];

class ckjlist
{
	public:
		struct node
		{
			int nxt,fro;
		}dat[100005];
		int tai;
		ckjlist(){tai=0;}
		void ins(int x)
		{
			dat[tai].nxt=x;
			dat[x].fro=tai;
			dat[x].nxt=0;
			tai=x;
		}
		void del(int x)
		{
			if(x!=tai)
			{
				dat[dat[x].fro].nxt=dat[x].nxt;
				dat[dat[x].nxt].fro=dat[x].fro;
			}
			else
			{
				dat[dat[tai].fro].nxt=0;
				tai=dat[tai].fro;
			}
			dat[x].fro=0;
			dat[x].nxt=0;
		}
}lis;

int n,m,lpos=1,rpos,a[100005],cnt[100005];
ll sum[100005],out[100005],poww[2][100005];
int blo;

inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
		{
			w=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		s=(s<<1)+(s<<3)+ch-'0';
		ch=getchar();
	}
	return s*w;
}

inline bool cmp(ask &x,ask &y)
{
	if(x.lx==y.lx)
	{
		return x.r<y.r;
	}
	return x.lx<y.lx;
}

inline void initpow(int mod)
{
	poww[0][0]=1;
	poww[1][0]=1;
	for(int i=1;i<=blo;i++)
	{
		poww[0][i]=poww[0][i-1]<<1;
		poww[0][i]%=mod;
	}
	for(int i=1;i<=blo;i++)
	{
		poww[1][i]=poww[0][blo]*poww[1][i-1];
		poww[1][i]%=mod;
	}
}

inline ll getpow(int x,int mod)
{
	return (poww[0][x%blo]*poww[1][x/blo])%mod;
}

inline void add(int x,int k)
{
	int num=a[x];
	if((sum[cnt[num]]-=num)==0)
	{
		lis.del(cnt[num]);
	}
	if(sum[cnt[num]+=k]==0)
	{
		lis.ins(cnt[num]);
	}
	sum[cnt[num]]+=num;
}

int main()
{
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	blo=sqrt(n);
	for(int i=1;i<=m;i++)
	{
		pro[i].l=read();
		pro[i].r=read();
		pro[i].p=read();
		pro[i].id=i;
		pro[i].lx=(pro[i].l-1)/blo+1;
	}
	sort(pro+1,pro+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int nl=pro[i].l,nr=pro[i].r,np=pro[i].p;
		int len=nr-nl+1;
		initpow(np);
		while(lpos<nl) add(lpos++,-1);
		while(lpos>nl) add(--lpos,1);
		while(rpos>nr) add(rpos--,-1);
		while(rpos<nr) add(++rpos,1);
		for(int j=lis.dat[0].nxt;j;j=lis.dat[j].nxt)
		{
			ll pre=((getpow(len,np)-getpow(len-j,np)+np)*sum[j]+np)%np;
			out[pro[i].id]=(out[pro[i].id]+pre+np)%np;
		}
	}
	for(int i=1;i<=m;i++)
	{
		printf("%lld\n",out[i]);
	}
	return 0;
}