Luogu

分析

考虑每个数的贡献。假设 $x$ 在 $[l,r]$ 中出现了 $c$ 次，则有 $2^{r-l+1}-2^{r-l+1-c}$ 个子序列包含 $x$，所以其贡献为 $x(2^{r-l+1}-2^{r-l+1-c})$。

考虑把出现次数相同的放到一起，即求出每种出现次数对应的数的和。显然可以直接莫队。

注意到出现次数最多只有 $\mathcal{O}(\sqrt{n})$ 种，所以我们可以直接暴力枚举出现次数算答案。

然而我们并不能 $\mathcal{O}(n)$ 枚举出现次数，用 std::unordered_set 或者双向链表维护所有 $\mathcal{O}(\sqrt{n})$ 种出现次数即可。

还有一个问题是如何快速求出 $2$ 的幂。可以对每个询问处理出 $2^0,2^1,\cdots,2^{317}$ 和 $2^{2\times 317},2^{3\times 317},\cdots,2^{317\times 317}$，即可做到 $\mathcal{O}(1)$ 快速幂。

有些卡常。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
using namespace std;
typedef long long ll;

namespace io {
    const int SIZE=1<<21|1;
    char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55]; int f,qr;
    #define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
    void flush() { fwrite(obuf,1,oS-obuf,stdout); oS=obuf; }
    void putc(char x) { *oS++=x; if (oS==oT) flush(); }
    void read(int& x) {
        for (f=1,c=gc();c<'0'||c>'9';c=gc()) if (c=='-') f=-1;
        for (x=0;c<='9'&&c>='0';c=gc()) x=x*10+(c&15); x*=f;
    }
    void write(int x) {
        if (!x) putc ('0'); if (x<0) putc('-'),x=-x;
        while (x) qu[++qr]=x%10+'0',x/=10;
        while (qr) putc(qu[qr--]);
    }
    struct Flusher_ { ~Flusher_() { flush(); } } io_flusher_;
}
using io::putc;
using io::read;
using io::write;

const int N=100000+10;

int n,m,B,a[N],ans[N];
struct query { int l,r,mod,id; } q[N];
bool operator <(query a,query b) {
    if (a.l/B!=b.l/B) return a.l<b.l;
    else return (a.l/B)&1?a.r<b.r:a.r>b.r;
}

namespace L {
    int pre[N],nxt[N],lst=0;
    void insert(int x) {
        nxt[lst]=x,pre[x]=lst,lst=x;
    }
    void erase(int x) {
        if (x==lst) lst=pre[x];
        else nxt[pre[x]]=nxt[x],pre[nxt[x]]=pre[x];
        pre[x]=nxt[x]=0;
    }
}

int cnt[N],sum[N];
void add(int w) {
    sum[cnt[w]]-=w;
    if (!sum[cnt[w]]) L::erase(cnt[w]);
    ++cnt[w];
    if (!sum[cnt[w]]) L::insert(cnt[w]);
    sum[cnt[w]]+=w;
}
void del(int w) {
    sum[cnt[w]]-=w;
    if (!sum[cnt[w]]) L::erase(cnt[w]);
    --cnt[w];
    if (!sum[cnt[w]]) L::insert(cnt[w]);
    sum[cnt[w]]+=w;
}

int pw1[400],pw2[400];
int qpow(int x,int mod) { return 1ll*pw1[x%317]*pw2[x/317]%mod; }

int main() {
    read(n),read(m); B=sqrt(n);
    for (int i=1;i<=n;++i) read(a[i]);
    for (int i=1;i<=m;++i) read(q[i].l),read(q[i].r),read(q[i].mod),q[i].id=i;
    sort(q+1,q+m+1);
    for (int i=1,l=1,r=0;i<=m;++i) {
        while (l>q[i].l) --l,add(a[l]);
        while (r<q[i].r) ++r,add(a[r]);
        while (l<q[i].l) del(a[l]),++l;
        while (r>q[i].r) del(a[r]),--r;
        int mod=q[i].mod;
        for (int j=pw1[0]=1;j<=317;++j) pw1[j]=1ll*pw1[j-1]*2%mod;
        for (int j=pw2[0]=1;j<=317;++j) pw2[j]=1ll*pw2[j-1]*pw1[317]%mod;
        for (int t=L::nxt[0];t;t=L::nxt[t]) {
            int w=1ll*sum[t]*(qpow(r-l+1,mod)+mod-qpow(r-l+1-t,mod))%mod;
            ans[q[i].id]=(ans[q[i].id]+w)%mod;  
        }
    }
    for (int i=1;i<=m;++i) write(ans[i]),putc('\n');
    return 0;
}