2015 Multi-University Training Contest 8 hdu 5381 The sum of gcd

The sum of gcd

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 641 Accepted Submission(s): 277

Problem Description

You have an array A with the length of $n$

[Letquad f(l,r) = sum_{i = l}^{r}sum_{j = i}^{r}quad gcd(a_{i},a_{i+1},dots,a_{j})]

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

First line has one integers $n$

Second line has $n$ integers $A_i$

Third line has one integers $Q$ the number of questions

Next there are $Q$ lines,each line has two integers $l,r$

$1 leq T leq 3$

$1 leq n,Q leq 10^4$

$1 leq a_i leq 10^9$

$1leq l,r leq n$

Output

For each question,you need to print $f(l,r)$

Sample Input

1 2 3 4 5

1 3

2 3

1 4

4 2 6 9

1 3

2 4

2 3

Sample Output

Author

SXYZ

Source

2015 Multi-University Training Contest 8 1002

解题：线段树，学习了一位大神的写法，原来区间是可以这样子合并，本菜表示涨姿势了，again

先说说区间的合并吧，$gcd(gcd(1,2) gcd(3,4)) = gcd(1,4)$

我们先模拟下四个数范围比较小的情况

1L:(11) 1R:(11)

2L:(22) 2R:(22)

3L:(33) 3R:(33)

4L:(44) 4R:(44)

1与2 合并 3与4合并

12L:(11,12) 12R:(22,12)

34L:(33,34) 34R:(44,34)

12 与 34 合并

1234L:(11,12,13,14)

1234R:(44,34,24,14)

非常巧妙。。。赞

每个R的最后一个都代表着整个区间

而且每个R的里面的区间最右边都是区间的最右边

所以左子树的右区间与有子树的右区间是可以合并的

因为左子树的右区间都是以右子树的最左-1结尾的

同理左区间合并。

至于数量的计算，上面说gcd的时候已经说了

另外，可能会有相同的gcd，所以用Ln Rn来记录相同gcd的出现次数

还有随着区间的增长，gcd不会变大，只会不变或者变得更小

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 10010;
 5 struct node {
 6     LL sum;
 7     int Lg[32],Rg[32],Ln[32],Rn[32],Lc,Rc;
 8 } tree[maxn<<2];
 9 node pushup(const node &a,const node &b) {
10     node ret;
11     ret.sum = a.sum + b.sum;
12     for(int i = 0; i < a.Rc; ++i)
13         for(int j = 0; j < b.Lc; ++j)
14             ret.sum += __gcd(a.Rg[i],b.Lg[j])*1LL*a.Rn[i]*b.Ln[j];
15     for(int i = 0; i < b.Rc; ++i) {
16         ret.Rg[i] = b.Rg[i];
17         ret.Rn[i] = b.Rn[i];
18     }
19     for(int i = 0; i < a.Lc; ++i) {
20         ret.Lg[i] = a.Lg[i];
21         ret.Ln[i] = a.Ln[i];
22     }
23     int d = b.Rg[b.Rc-1],p = b.Rc;
24     for(int i = 0; i < a.Rc; ++i) {
25         int tmp = __gcd(a.Rg[i],d);
26         if(tmp == ret.Rg[p-1]) ret.Rn[p-1] += a.Rn[i];
27         else {
28             ret.Rg[p] = tmp;
29             ret.Rn[p++] = a.Rn[i];
30         }
31     }
32     ret.Rc = p;
33     d = a.Lg[a.Lc-1],p = a.Lc;
34     for(int i = 0; i < b.Lc; ++i) {
35         int tmp = __gcd(d,b.Lg[i]);
36         if(tmp == ret.Lg[p-1]) ret.Ln[p-1] += b.Ln[i];
37         else {
38             ret.Ln[p] = b.Ln[i];
39             ret.Lg[p++] = tmp;
40         }
41     }
42     ret.Lc = p;
43     return ret;
44 }
45 void build(int L,int R,int v) {
46     if(L == R) {
47         tree[v].Lc = tree[v].Rc = 1;
48         tree[v].Ln[0] = tree[v].Rn[0] = 1;
49         scanf("%d",&tree[v].Lg[0]);
50         tree[v].sum = tree[v].Rg[0] = tree[v].Lg[0];
51         return;
52     }
53     int mid = (L + R)>>1;
54     build(L,mid,v<<1);
55     build(mid+1,R,v<<1|1);
56     tree[v] = pushup(tree[v<<1],tree[v<<1|1]);
57 }
58 void query(int L,int R,int lt,int rt,int v) {
59     if(lt <= L && rt >= R) {
60         if(lt == L) tree[0] = tree[v];
61         else tree[0] = pushup(tree[0],tree[v]);
62         return;
63     }
64     int mid = (L + R)>>1;
65     if(lt <= mid) query(L,mid,lt,rt,v<<1);
66     if(rt > mid) query(mid+1,R,lt,rt,v<<1|1);
67 }
68 int main() {
69     int kase,n,m,x,y;
70     scanf("%d",&kase);
71     while(kase--) {
72         scanf("%d",&n);
73         build(1,n,1);
74         scanf("%d",&m);
75         while(m--) {
76             scanf("%d%d",&x,&y);
77             query(1,n,x,y,1);
78             printf("%I64d
",tree[0].sum);
79         }
80     }
81     return 0;
82 }

View Code