NPY and girls

题目链接：

莫队算法

注意到没有修改区间的操作，使用莫队算法：将整个区间分成若干个块，将询问区间按块优先升序排序，同块内按区间右界升序排序，添加一个元素，满足条件的值sum就变为sum=(sum*times[a[r]]/(r-l+1));减少一个值同理。从第一个区间一直推到最后一个区间即可。（之前TLE一直以为是区间大小的问题，现在发现是这句话while(x<0)x+=M，不过因为这题M比较大，改改区间居然被我水过去了...）

代码如下：

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define N 30005  6 #define M 1000000007  7 #define LL long long  8 #define B 250/**((int)sqrt((double)n)) sqrt(n) will be TLE**/  9 #define mst(x) memset(x,0,sizeof(x)) 10 using namespace std; 11 LL times[N]; 12 LL T,n,m,x,y; 13 LL a[N]; 14 struct nod{ 15     LL l,r,no,value; 16 }q[N]; 17 LL exGCD(LL a,LL b){ 18     if(b==0){ 19         x=1; 20         y=0; 21         return a; 22     } 23     LL r=exGCD(b,a%b); 24     LL tmp=x; 25     x=y; 26     y=tmp-(a/b)*y; 27     return r; 28 } 29 bool cmp_by_range(nod x,nod y){ 30     if(x.l/B==y.l/B){ 31         return x.r
         
          q[i].r){ 73             exGCD((r-l+1),M); 74             while(x<0)x+=M; 75             sum=((sum*times[a[r]])%M*x)%M; 76             times[a[r]]--; 77             r--; 78         } 79         while(l
          
           q[i].l){ 87 l--; 88 times[a[l]]++; 89 exGCD(times[a[l]],M); 90 while(x<0)x+=M; 91 sum=((sum*(r-l+1)%M)*x)%M; 92 } 93 q[i].value=sum; 94 } 95 } 96 int main(void){ 97 scanf("%I64d",&T); 98 while(T--){ 99 init();100 solve();101 sort(q,q+m,cmp_by_no);102 for(LL i=0;i