题目地址：HDU 5145

莫队真的好奇妙。。

这种复杂度竟然仅仅有n*sqrt(n)。。。

裸的莫队分块，先离线。然后按左端点分块，按块数作为第一关键字排序。然后按r值作为第二关键字进行排序。

都是从小到大，能够证明这种复杂度仅仅有n*sqrt(n)。

然后进行块之间的转移。

代码例如以下：

#include <iostream>

#include <string.h>

#include <math.h>

#include <queue>

#include <algorithm>

#include <stdlib.h>

#include <map>

#include <set>

#include <stdio.h>

#include <time.h>

using namespace std;

#define LL __int64

#define pi acos(-1.0)

//#pragma comment(linker, "/STACK:1024000000")

const int mod=1e9+7;

const int INF=0x3f3f3f3f;

const double eqs=1e-9;

const int MAXN=30000+10;

int a[MAXN];

LL ans[MAXN], inv[MAXN], ha[MAXN];

struct node

{

        int l, r, id, pos;

}fei[MAXN];

bool cmp(node x, node y)

{

        return x.pos<y.pos||(x.pos==y.pos&&x.r<y.r);

}

LL Pow(LL x, int k)

{

        LL ans=1;

        while(k){

                if(k&1) ans=ans*x%mod;

                x=x*x%mod;

                k>>=1;

        }

        return ans;

}

void init()

{

        for(int i=0;i<=30000;i++){

                inv[i]=Pow((LL)i,mod-2);

        }

}

int main()

{

        int t, n, m, i, j, l, r, k, Case=0;

        LL res;

        //freopen("1.txt","r",stdin);

        //freopen("2.txt","w",stdout);

        init();

        scanf("%d",&t);

        while(t--){

                scanf("%d%d",&n,&m);

                k=sqrt(n*1.0);

                for(i=1;i<=n;i++){

                        scanf("%d",&a[i]);

                }

                for(i=0;i<m;i++){

                        scanf("%d%d",&fei[i].l,&fei[i].r);

                        fei[i].id=i;

                        fei[i].pos=fei[i].l/k;

                }

                sort(fei,fei+m,cmp);

                l=1;r=1;

                res=1;

                memset(ha,0,sizeof(ha));

                ha[a[1]]=1;

                for(i=0;i<m;i++){

                        while(r<fei[i].r){

                                r++;

                                ha[a[r]]++;

                                res=res*(r-l+1)%mod*inv[ha[a[r]]]%mod;

                        }

                        while(r>fei[i].r){

                                res=res*ha[a[r]]%mod*inv[r-l+1]%mod;

                                ha[a[r]]--;

                                r--;

                        }

                        while(l>fei[i].l){

                                l--;

                                ha[a[l]]++;

                                res=res*(r-l+1)%mod*inv[ha[a[l]]]%mod;

                        }

                        while(l<fei[i].l){

                                res=res*ha[a[l]]%mod*inv[r-l+1]%mod;

                                ha[a[l]]--;

                                l++;

                        }

                        ans[fei[i].id]=res;

                }

                for(i=0;i<m;i++){

                        printf("%I64d\n",ans[i]);

                }

        }

        return 0;

}