NPY and girls
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5145
莫队算法
注意到没有修改区间的操作，使用莫队算法：将整个区间分成若干个块，将询问区间按块优先升序排序，同块内按区间右界升序排序，添加一个元素，满足条件的值sum就变为sum=(sum*times[a[r]]/(r-l+1));减少一个值同理。从第一个区间一直推到最后一个区间即可。（之前TLE一直以为是区间大小的问题，现在发现是这句话while(x<0)x+=M，不过因为这题M比较大，改改区间居然被我水过去了...）
代码如下：
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define N 30005
#define M 1000000007
#define LL long long
#define B 250/**((int)sqrt((double)n)) sqrt(n) will be TLE**/
#define mst(x) memset(x,0,sizeof(x))
using namespace std;
LL times[N];
LL T,n,m,x,y;
LL a[N];
struct nod{
LL l,r,no,value;
}q[N];
LL exGCD(LL a,LL b){
if(b==){
x=;
y=;
return a;
}
LL r=exGCD(b,a%b);
LL tmp=x;
x=y;
y=tmp-(a/b)*y;
return r;
}
bool cmp_by_range(nod x,nod y){
if(x.l/B==y.l/B){
return x.r<y.r;
}else return (x.l/B<y.l/B);
}
bool cmp_by_no(nod x,nod y){
return x.no<y.no;
}
void init(){
mst(times);
scanf("%I64d%I64d",&n,&m);
for(LL i=;i<n;++i)
scanf("%I64d",&a[i]);
for(LL i=;i<m;++i){
LL l,r;
scanf("%I64d%I64d",&l,&r);
l--,r--;
q[i].l=l;
q[i].r=r;
q[i].no=i;
q[i].value=;
}
sort(q,q+m,cmp_by_range);
}
void solve(){
LL l=q[].l,r=q[].r,sum=;
times[a[l]]++;
for(LL i=l+;i<=r;++i){
times[a[i]]++;
exGCD(times[a[i]],M);
while(x<)x+=M;
sum=((sum*(i-l+))%M*x)%M;
}
q[].value=sum;
for(LL i=;i<m;++i){
//l=q[i-1].l,r=q[i-1].r;
while(r<q[i].r){
r++;
times[a[r]]++;
exGCD(times[a[r]],M);
while(x<)x+=M;
sum=((sum*(r-l+))%M*x)%M;
}
while(r>q[i].r){
exGCD((r-l+),M);
while(x<)x+=M;
sum=((sum*times[a[r]])%M*x)%M;
times[a[r]]--;
r--;
}
while(l<q[i].l){
exGCD((r-l+),M);
while(x<)x+=M;
sum=((sum*times[a[l]])%M*x)%M;
times[a[l]]--;
l++;
}
while(l>q[i].l){
l--;
times[a[l]]++;
exGCD(times[a[l]],M);
while(x<)x+=M;
sum=((sum*(r-l+)%M)*x)%M;
}
q[i].value=sum;
}
}
int main(void){
scanf("%I64d",&T);
while(T--){
init();
solve();
sort(q,q+m,cmp_by_no);
for(LL i=;i<m;++i)
printf("%I64d\n",q[i].value);
}
}