abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S3568 【小纪的作业题】

发表于 更新于

Description

小纪是个聪明活泼又可爱的小男孩。有一天，他做作业遇到一道题，小纪表示给跪，于是他向你求助。题目是这样的：

给你一个长度为 $n$ 的正整数序列 $a_1$ ~ $a_n$。

有 $m$ 次询问，对于每次询问 $\text{query}(l, r)$，需要在子串 $a_l, a_{l + 1}, …, a_{r - 1}, a_{r}$ 中求出答案：对于每一个在子串内的不同的数 $x$，如果它在子串中出现了 $f(x)$ 次，那么答案为 $\sum x^{f(x)}$。

由于这个答案可能很大，所以只需要求出答案对 $(10^9 + 7)$ 取模后的结果即可。

Solution

发现因为是求 $x^{f(x)}$ 的和，所以我们可以发现我们难以合并块与块之间的贡献，所以线段树和分块做不了。

于是我们考虑莫队。

纪念一下写过的第一道莫队题，感觉还挺有趣的？比较喜欢这个题。

可以通过预处理逆元和奇偶排序来加速。

Code

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <cmath>
#include <cstdio>
#define mod 1000000007
#define maxN 100010
struct Query{ long long l, r, k, id; } p[maxN];
long long tmp = 0;
long long res[maxN], val[maxN], a[maxN];
long long bucket[maxN], Ans[maxN], inv[maxN];
long long pow (long long x, long long y)
{
	if(!y)
	{
		return 1;
	}
	else
	{
		long long dq = pow(x, y >> 1);
		if(!(y % 2))
		{
			return dq * dq % mod;
		}
		else
		{
			return dq * dq % mod * x % mod;
		}
	}
}
void px (long long l, long long r)
{
	long long x = l, y = r;
	long long mid1 = p[(l + r) >> 1].k, mid2 = p[(l + r) >> 1].r;
	while(x <= y)
	{
		while((p[x].k < mid1) || (p[x].k == mid1 && (p[x].k & 1 ? p[x].r < mid2 : p[x].r > mid2)))
		{
			x++;
		}
		while((p[y].k > mid1) || (p[y].k == mid1 && (p[y].k & 1 ? p[y].r > mid2 : p[y].r < mid2)))
		{
			y--;
		}
		if(x <= y)
		{
			Query t = p[x];
			p[x] = p[y];
			p[y] = t;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px(l, y);
	}
	if(x < r)
	{
		px(x, r);
	}
}
void add (long long x)
{
	tmp -= val[a[x]];
	if(tmp < 0)
	{
		tmp += mod;
	}
	if(!bucket[a[x]])
	{
		val[a[x]] = 1;
	}
	bucket[a[x]]++;
	val[a[x]] *= a[x];
	val[a[x]] %= mod;
	tmp += val[a[x]];
	tmp %= mod;
}
void del (long long x)
{
	tmp -= val[a[x]];
	if(tmp < 0)
	{
		tmp += mod;
	}
	if(bucket[a[x]] == 1)
	{
		val[a[x]] = 0;
	}
	bucket[a[x]]--;
	val[a[x]] *= inv[a[x]];
	val[a[x]] %= mod;
	tmp += val[a[x]];
	tmp %= mod;
}
int main ()
{
	long long n = 0, m = 0;
	scanf("%lld %lld", &n, &m);
	long long SqrtN = sqrt(n + 1);
	for(long long i = 1;i <= n; i++)
	{
		scanf("%lld", &a[i]);
	}
	for(long long i = 1;i <= m; i++)
	{
		long long l = 0, r = 0;
		scanf("%lld %lld", &l, &r);
		p[i].l = l;
		p[i].r = r;
		p[i].k = (l - 1) / SqrtN + 1;
		p[i].id = i;
	}
	px(1, m);
	for(long long i = 1;i < maxN; i++)
	{
		inv[i] = pow(i, mod - 2);
	}
	long long l = 1, r = 0;
	for(long long i = 1;i <= m; i++)
	{
		while(l > p[i].l)
		{
			add(--l);
		}
		while(r < p[i].r)
		{
			add(++r);
		}
		while(l < p[i].l)
		{
			del(l++);
		}
		while(r > p[i].r)
		{
			del(r--);
		}
		Ans[p[i].id] = tmp;
	}
	for(long long i = 1;i <= m; i++)
	{
		printf("%lld\n", Ans[i]);
	}
	return 0;
}