【HDU 5381】 The sum of gcd （子区间的xx和，离线）

【题目】

The sum of gcd

Problem Description

You have an array

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

Output

For each question,you need to print

Sample Input

2 5 1 2 3 4 5 3 1 3 2 3 1 4 4 4 2 6 9 3 1 3 2 4 2 3

Sample Output

9 6 16 18 23 10

Author

SXYZ

Source

2015 Multi-University Training Contest 8

【题意】

You have an array A,the length of A is n
Let f(l,r)=∑r i=l ∑r j=i gcd(ai,ai+1....aj) (n,m<=1000,ai<=1000000000)

【分析】

　　HHHHHH我又没有想出来【嘲笑一下自己

　　跟之前比赛那题的解法简直一模一样！！！

　　可以离线做，然后扫描右端点，左端点存一个f[l]表示gcd(al)+gcd(al,al+1)+gcd(al,al+1,al+2)+...gcd(al,al+1,al+2,...ar) 【r为当前扫描到的右端点

　　然后，如果新加入一个r，每一位的数都要加上gcd(a[l]+a[l+1]+…+a[r]),这最多只有logn段，因为左边的必然是右边的因数，（然后因数至少除以2吧）

　　用链表弄这个，然后线段树或者树状数组维护区间和（树状数组的话要区间修改区间查询）

　　 O(nlognlogn)

　　一生气全部LL 就能AC了ORZ。。

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<vector>
  8 using namespace std;
  9 #define Maxn 10010
 10 #define LL long long
 11 
 12 LL a[Maxn];
 13 
 14 struct hp
 15 {
 16     LL l,r,id;
 17     LL ans;
 18 }q[Maxn];
 19 
 20 bool cmp(hp x,hp y) {return x.r<y.r;}
 21 bool cmp2(hp x,hp y) {return x.id<y.id;}
 22 
 23 LL lt[Maxn],g[Maxn],last;
 24 LL n,m;
 25 
 26 LL gcd(LL a,LL b)
 27 {
 28     if(b==0) return a;
 29     return gcd(b,a%b);
 30 }
 31 
 32 LL c1[Maxn],c2[Maxn];
 33 void add(LL l,LL r,LL y)
 34 {
 35     // printf("add %d %d %d
",l,r,y);
 36     for(LL i=l;i<=n;i+=i&(-i))
 37         c1[i]+=y,c2[i]+=l*y;
 38     r++;
 39     for(LL i=r;i<=n;i+=i&(-i))
 40         c1[i]-=y,c2[i]-=r*y;
 41 }
 42 
 43 LL query(LL l,LL r)
 44 {
 45     // printf("ask %d %d ",l,r);
 46     LL ans=0;
 47     for(LL i=r;i>=1;i-=i&(-i))
 48         ans+=c1[i]*(r+1)-c2[i];
 49     l--;
 50     for(LL i=l;i>=1;i-=i&(-i))
 51         ans-=c1[i]*(l+1)-c2[i];
 52     // printf("%d
",ans);
 53     return ans;
 54 }
 55 
 56 void ffind(LL r)
 57 {
 58     if(r==1)
 59     {
 60         add(r,r,a[r]);
 61         last=1;lt[r]=0;g[r]=a[r];
 62         return;
 63     }
 64     lt[r]=last,last=r,g[r]=a[r];
 65     for(LL i=last;lt[i];)
 66     {
 67         g[lt[i]]=gcd(g[lt[i]],a[r]);
 68         if(g[lt[i]]==g[i])
 69         {
 70             lt[i]=lt[lt[i]];
 71         }
 72         else i=lt[i];
 73     }
 74     for(LL i=last;i;i=lt[i])
 75     {
 76         add(lt[i]+1,i,g[i]);
 77     }
 78 }
 79 
 80 int main()    
 81 {
 82     LL T;
 83     scanf("%lld",&T);
 84     while(T--)
 85     {
 86         scanf("%lld",&n);
 87         for(LL i=1;i<=n;i++) scanf("%lld",&a[i]);
 88         scanf("%lld",&m);
 89         for(LL i=1;i<=m;i++)
 90         {
 91             scanf("%lld%lld",&q[i].l,&q[i].r);
 92             q[i].id=i;
 93         }
 94         sort(q+1,q+1+m,cmp);
 95         memset(c1,0,sizeof(c1));
 96         memset(c2,0,sizeof(c2));
 97         LL now=0;
 98         for(LL i=1;i<=m;i++)
 99         {
100             while(now<q[i].r)
101             {
102                 now++;
103                 ffind(now);
104             }
105             q[i].ans=query(q[i].l,q[i].r);
106         }
107         sort(q+1,q+1+m,cmp2);
108         for(LL i=1;i<=m;i++) printf("%lld
",q[i].ans);
109     }
110     return 0;
111 }

View Code

2016-11-10 21:52:36

伟大的子区间离线做法，log段！！！！！

好多东东都是log段的说。。。

啊啊啊，我觉得我智障！！

想了好久子区间求和怎么破。。。

就记录一个lsm，rsm，满足结合律啊。。。。。

异或和sm的也是可以的！！！

每天智障24小时。。