codeforces 671C

题意定义f(l,r)为去掉[l,r]部分后剩下的数任意两个数的最大公约数的最大值

现在求f(l,r)的和

由于每个数ai最大只有200000，因此我们穷举因子x，记录以其为因子的a[i]的i值并按i升序。

下面我们从大到小穷举每个因子x，我们依次计算以f(l,r)=x的区间数，

有了上述的维护信息，我们很容易三种情况的区间满足f(l,r)=x（我就不具体细说了）

令pre[i]表示当前以第i个位置结尾的区间满足任意j(1<=j<=pre[i])，f(j,i)<x

显然f(l,r)=x的区间数=当前还没计算过的区间数-∑pre[i]

这就要维护∑pre[i]，每次修改是将一段区间pre[i]>x的数赋值为x

显然pre[i]是单调不上升，因此可以用线段树维护之

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int laz[*],mi[*],mx[*];

 ll tr[*];

 vector<int> g[];

 int n,m;

 void build(int i,int l,int r)

 {

     laz[i]=-;

     if (l==r) mx[i]=mi[i]=tr[i]=l;

     else {

         int m=(l+r)>>;

         build(i*,l,m);

         build(i*+,m+,r);

         tr[i]=tr[i*]+tr[i*+];

         mx[i]=max(mx[i*],mx[i*+]);

         mi[i]=min(mi[i*],mi[i*+]);

     }

 }

 void work(int i,int l,int r,int x,int y,int z)

 {

    // if (i==1) cout <<z<<endl;

     if (x>y) return;

     if (mx[i]<=z) return;

     if (x<=l&&y>=r&&mi[i]>z)

     {

         mi[i]=mx[i]=laz[i]=z;

         tr[i]=(ll)(r-l+)*z;

     }

     else {

         int m=(l+r)>>;

         if (laz[i]>-)

         {

             laz[i*]=laz[i*+]=laz[i];

             mi[i*]=mx[i*]=laz[i];

             mi[i*+]=mx[i*+]=laz[i];

             tr[i*]=(ll)laz[i]*(m-l+);

             tr[i*+]=(ll)laz[i]*(r-m);

             laz[i]=-;

         }

         if (x<=m) work(i*,l,m,x,y,z);

         if (y>m) work(i*+,m+,r,x,y,z);

         tr[i]=tr[i*]+tr[i*+];

         mx[i]=max(mx[i*],mx[i*+]);

         mi[i]=min(mi[i*],mi[i*+]);

     }

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=; i<=n; i++)

     {

         int x;scanf("%d",&x);

         for (int j=; j*j<=x; j++)

             if (x%j==)

             {

                 g[x/j].push_back(i);

                 if (j*j!=x) g[j].push_back(i);

             }

         m=max(m,x);

     }

     build(,,n);

     ll pre=(ll)n*(n+)/;

     ll ans=;

     for (int i=m; i; i--)

     {

         if (g[i].size()<) continue;

         int j=g[i].size()-;

         work(,,n,g[i][]+,g[i][j]-,g[i][]);

         work(,,n,,g[i][j-]-,);

         work(,,n,g[i][]+,n,g[i][]);

         ans+=(pre-tr[])*(ll)i;

        // cout <<tr[1]<<endl;

         pre=tr[];

     }

     printf("%lld\n",ans);

 }

巴特西

codeforces 671C

最新文章

热门文章