设数列s，位置为i的元素被区间覆盖的数目定义为∑s[j], j ≤ i。

则给定区间[l, r], 更新数列s,只需：

++s[l]，--s[r + 1]。

 

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4  5 using namespace std; 6 typedef __int64 LL; 7  8 const int maxn = 5e4 + 10; 9 10 int w[maxn], cnt[maxn];11 LL A, B;12 int n, m;13 14 LL gcd(LL a, LL b){15     if(!b) return a;16     return gcd(b, a % b);17 }18 19 LL f[maxn];20 21 void init(){22     for(int i = 0; i < 3; i++) f[i] = 0;23     f[3] = 1;24     for(int i = 3; i < maxn; i++) f[i + 1] = f[i] * (i + 1) / (i - 2);25 }26 27 int main(){28     int T;29     scanf("%d", &T);30     init();31     while(T--){32         scanf("%d%d", &n, &m);33         memset(cnt, 0, sizeof cnt);34         for(int i = 1; i <= n; i++) scanf("%d", &w[i]);35         for(int i = 1, p, q; i <= m; i++){36             scanf("%d%d", &p, &q);37             ++cnt[p], --cnt[q + 1];38         }39         for(int i = 1; i <= n; i++) cnt[i] += cnt[i - 1];40         B = f[m];41         A = 0;42         for(int i = 1; i <= n; i++)    A += (LL)w[i] * f[cnt[i]];43         if(!A || !B){44             printf("0\n");45             continue;46         }47         LL D = gcd(A, B);48         A /= D, B /= D;49         if(B == 1) printf("%I64d\n", A);50         else printf("%I64d/%I64d\n", A, B);51     }52     return 0;53 }