JZOJ 3568 小纪的作业题

莫队 SB 题，不解释。

代码：

#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]);
}