C++11(clang++ 3.9) 解法, 执行用时: 3759ms, 内存消耗: 6628K, 提交时间: 2018-08-11 08:54:08

#include <bits/stdc++.h>
using namespace std;
#define N 100100
#define ll long long

struct ques {
	int l,r,p,id;
}q[N];
int n,m,head,sz;
int num[N],pre[N],nex[N];
ll p1[N],p2[N],sum[N];

bool cmp(ques a,ques b) {
	if (a.l/sz==b.l/sz) return a.r<b.r;
	return a.l/sz<b.l/sz;
}

void erase(int x) {
	int l=pre[x],r=nex[x];
	if (l) nex[l]=r; else head=r;
	if (r) pre[r]=l;
	nex[x]=pre[x]=0;
}

void insert(int x) {
	nex[x]=head;
	pre[head]=x;
	head=x; pre[x]=0;
}

void change(int x,int f)
{
	int now=num[x];
	if (f>0)
	{
		if (now) {
			sum[now]-=x;
			if (!sum[now]) erase(now);
		}
		if (!sum[++num[x]]) insert(now+1);
		sum[num[x]]+=x;
	} else
	{
		sum[now]-=x;
		if (!sum[now]) erase(now);
		if (now-1) {
			sum[now-1]+=x;
			if (sum[now-1]==x) insert(now-1);
		}
		num[x]--;
	}
}

ll power(int x,int p) {
	return p2[x/sz]*p1[x%sz]%p;
}

int query(int p,int len) {
	p1[0]=1; for (int i=1;i<=sz;i++) p1[i]=p1[i-1]*2%p;
	p2[0]=1; for (int i=1;i<=n/sz;i++) p2[i]=p2[i-1]*p1[sz]%p;
	int ret=0;
	for (int i=head;i;i=nex[i])
		ret=(ret+sum[i]*(power(len,p)-power(len-i,p)+p)%p)%p;
	return ret;
}

int a[N],ans[N];
int main()
{
	scanf("%d%d",&n,&m); sz=sqrt(n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=m;i++) scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].p),q[i].id=i;
	sort(q+1,q+m+1,cmp);
	int l=1,r=0;
	for (int i=1;i<=m;i++)
	{
		while (l>q[i].l) change(a[--l],1);
		while (r<q[i].r) change(a[++r],1);
		while (l<q[i].l) change(a[l++],-1);
		while (r>q[i].r) change(a[r--],-1);
		ans[q[i].id]=query(q[i].p,q[i].r-q[i].l+1);
	}
	for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}