就我一个小丑wa成了12分。

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map>
using namespace std;
#define int long long
int n,m;
int cnt;
int bl;
int l[100010],r[100010],p[100010],ans[100010];
int vl[100010],v2[100010],v3[100010];
int n2;
int d[100010],id[100010];
bool cmp(int x,int y)
{
	if(l[x]/bl!=l[y]/bl)
	{
		return l[x]/bl<l[y]/bl;
	}
	return ( ((l[x]/bl)&1) ? (r[x]<r[y]) : (r[x]>r[y]) );
}
bool cmp2(int x,int y)
{
	return vl[x]<vl[y];
}
int L,R;
int m2[100010];
int s[100010],s2[100010];
int vm[100010],mv[100010],vn;
int vs[100010];
void update(int x)
{
    if(vm[v2[x]])
    {
        vs[v2[x]]++;
        return;
    }
    s[s2[v2[x]]]-=vl[x];
    s2[v2[x]]++;
    s[s2[v2[x]]]+=vl[x];
}
void downdate(int x)
{
    if(vm[v2[x]])
    {
        vs[v2[x]]--;
        return;
    }
    s[s2[v2[x]]]-=vl[x];
    s2[v2[x]]--;
    s[s2[v2[x]]]+=vl[x];
}
signed main()
{
	cin>>n>>m;
	bl=sqrt(n);
	for(int i=1;i<=n;i++)
	{
		cin>>vl[i];
		id[i]=i;
	}
	sort(id+1,id+n+1,cmp2);
	for(int i=1;i<=m;i++)
	{
		cin>>l[i]>>r[i]>>p[i];
		d[i]=i;
	}
	sort(d+1,d+m+1,cmp);
	int js=0;
	for(int i=1;i<=n;i++)
	{
		if(vl[id[i]]!=vl[id[i-1]])
		{
		    cnt+=vl[id[i]];
		    if(js>bl)
            {
                vm[n2]=1;
                mv[++vn]=n2;
            }
			n2++;
			v2[id[i]]=n2;
			v3[n2]=vl[id[i]];
			js=1;
		}
		else
		{
			v2[id[i]]=v2[id[i-1]];
			js++;
		}
	}
	if(js>bl)
    {
        vm[js]=1;
        mv[++vn]=n2;
    }
    s[0]=cnt;
	L=1,R=0;
	for(int k=1;k<=m;k++)
	{
		int il=l[d[k]],ir=r[d[k]],ip=p[d[k]];
		m2[0]=1;
		for(int j=1;j<=bl;j++)
		{
			m2[j]=m2[j-1]*2%ip;
		}
		for(int j=2;j*bl<=n;j++)
		{
			m2[j*bl]=m2[j*bl-bl]*m2[bl]%ip;
		}
		while(il<L)
        {
            L--;
            update(L);
        }
        while(R<ir)
        {
            R++;
            update(R);
        }
        while(il>L)
        {
            downdate(L);
            L++;
        }
        while(R>ir)
        {
            downdate(R);
            R--;
        }
        int ll=R-L+1;
        ans[d[k]]=cnt%ip*m2[ll%bl]%ip*m2[ll/bl*bl]%ip;
        for(int i=0;i<=bl;i++)
        {
        	if(ll<i)
        	{
        		break;
			}
            ans[d[k]]=(ans[d[k]]-s[i]%ip*m2[(ll-i)%bl]%ip*m2[(ll-i)/bl*bl]%ip+ip)%ip;
        }
        for(int i=1;i<=vn;i++)
        {
            ans[d[k]]=(ans[d[k]]-m2[(ll-vs[i])%bl]*m2[(ll-vs[i])/bl*bl]%ip*v3[mv[i]]%ip+ip)%ip;
        }
	}
	for(int i=1;i<=m;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}