题面
离散化不必说
对每个不同的值分开考虑贡献
设区间长度为len，某个值的出现次数为cnt
于是乎这个值在所有不同子序列中出现次数为:$2^{len}-2^{len-cnt}$(容斥一下)
莫队？
然而布星 不愧是毒瘤，第一次见模数每次询问不同，大抵是我孤陋寡闻了
于是考虑莫队维护的东西
1.维护值x的出现次数
2.维护出现次数为x的值之和
根号分治一下
次数小于$\sqrt n$ 用方案2
否则用方案1
然后是O(1)2的幂次
预处理$2^1,2^2,\cdots,2^{\sqrt n}$ $2^{\sqrt n}, 2^{2\sqrt n},\cdots, 2^{\sqrt n * \sqrt n}$
$O(n\sqrt n)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
using namespace std;
int n, m, qsize;
typedef long long ll;
int a[100010];
int qid[100010], answ[100010];
struct query {
int l, r, p, id;
friend inline int operator < (const query &a, const query &b) {
if(qid[a.l] != qid[b.l]) return a.l < b.l;
if(qid[a.l] & 1) return a.r < b.r;
return a.r > b.r;
}
} q[100010];
int pw[100010], pw2[100010];
int cnt[100010], radio;
ll sum[100010];
int b[100010];
unordered_set<int> st;
inline void add(int x) {
if(cnt[x] < radio) sum[cnt[x]] -= b[x];
cnt[x]++;
if(cnt[x] == radio) st.insert(x);
if(cnt[x] < radio) sum[cnt[x]] += b[x];
}
inline void del(int x) {
if(cnt[x] < radio) sum[cnt[x]] -= b[x];
if(cnt[x] == radio) st.erase(x);
cnt[x]--;
if(cnt[x] < radio) sum[cnt[x]] += b[x];
}
int sp;
inline void build_pw(int p) {
int now = 1;
for(int i = 0; i < sp; i++, now = now * 2 % p) pw[i] = now;
pw2[0] = 1;
for(int i = 1, tmp = now; i < sp; i++, now = 1ll * now * tmp % p) pw2[i] = now;
}
inline int get_pw(int b, int p) {
return 1ll * pw2[b / sp] * pw[b % sp] % p;
}
int main() {
scanf("%d%d", &n, &m);
sp = radio = sqrt(n + 1);
sp++;
qsize = sqrt(n * n / m + 1);
for(int i = 1; i <= n; i++) qid[i] = (i - 1) / qsize, scanf("%d", a + i), b[i] = a[i];
sort(b + 1, b + 1 + n);
for(int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
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 + 1 + m);
int nowl = 1, nowr = 0;
for(int i = 1; i <= m; i++) {
while(nowr < q[i].r) add(a[++nowr]);
while(nowl > q[i].l) add(a[--nowl]);
while(nowr > q[i].r) del(a[nowr--]);
while(nowl < q[i].l) del(a[nowl++]);
build_pw(q[i].p);
int ans = 0, len = q[i].r - q[i].l + 1;
// fprintf(stderr, "%d %d %d\n", q[i].l, q[i].r, q[i].p);
// for(int j = 0; j < len; j++) fprintf(stderr, "%d ", get_pw(j, q[i].p));
// fprintf(stderr, "\n");
for(int j = 1; j < radio; j++)
ans = (ans + 1ll * sum[j] % q[i].p * (q[i].p + get_pw(len, q[i].p) - get_pw(len - j, q[i].p))) % q[i].p;
// fprintf(stderr, "case1 : %d, %lld\n", i, 1ll * sum[j] % q[i].p * (q[i].p + get_pw(len, q[i].p) - get_pw(len - j, q[i].p)) % q[i].p);
// fprintf(strerr, "%d\n", ans);
for(auto j : st) {
ans = (ans + 1ll * b[j] * (get_pw(len, q[i].p) - get_pw(len - cnt[j], q[i].p) + q[i].p)) % q[i].p;
// fprintf(stderr, "case2 : %d, %lld\n", i, 1ll * b[j] * (get_pw(len, q[i].p) - get_pw(len - cnt[j], q[i].p)) % q[i].p);
}
answ[q[i].id] = ans;
// fprintf(stderr, "%d\n", ans);
}
for(int i = 1; i <= m; i++) printf("%d\n", answ[i]);
return 0;
}