JZOJ 3568.小纪的作业题

莫队 SB 题,不解释。

代码:

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
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int mod = 1e9 + 7;
int n,m,block;
int a[N + 5],pos[N + 5];
struct s_query
{
int l,r,id;
inline bool operator<(const s_query &o) const
{
return pos[l] ^ pos[o.l] ? pos[l] < pos[o.l] : pos[l] & 1 ? r < o.r : r > o.r;
}
} qry[N + 5];
int inv[N + 5],val[N + 5],cnt[N + 5];
int ans[N + 5],cur;
inline void add(int x)
{
cur = (cur - val[x] + mod) % mod;
!cnt[x]++ && (val[x] = 1);
val[x] = (long long)val[x] * x % mod;
cur = (cur + val[x]) % mod;
}
inline void del(int x)
{
cur = (cur - val[x] + mod) % mod;
!--cnt[x] && (val[x] = 0);
val[x] = (long long)val[x] * inv[x] % mod;
cur = (cur + val[x]) % mod;
}
int main()
{
inv[1] = 1;
for(register int i = 2;i <= N;++i)
inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
scanf("%d%d",&n,&m),block = sqrt(n);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),pos[i] = (i - 1) / block + 1;
for(register int i = 1;i <= m;++i)
scanf("%d%d",&qry[i].l,&qry[i].r),qry[i].id = i;
sort(qry + 1,qry + m + 1);
for(register int i = 1,l = 1,r = 0;i <= m;++i)
{
for(;r < qry[i].r;add(a[++r]));
for(;r > qry[i].r;del(a[r--]));
for(;l < qry[i].l;del(a[l++]));
for(;l > qry[i].l;add(a[--l]));
ans[qry[i].id] = cur;
}
for(register int i = 1;i <= m;++i)
printf("%d\n",ans[i]);
}