hdu5419 Victor and Toys

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

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

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

http://acm.hdu.edu.cn/showproblem.php?pid=5419

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 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
");
45             continue;
46         }
47         LL D = gcd(A, B);
48         A /= D, B /= D;
49         if(B == 1) printf("%I64d
", A);
50         else printf("%I64d/%I64d
", A, B);
51     }
52     return 0;
53 }

View Code