Codeforces 671C. Ultimate Weirdness of an Array（数论+线段树）

　　看见$a_ileq 200000$和gcd，就大概知道是要枚举gcd也就是答案了...

　　因为答案是max，可以发现我们很容易算出<=i的答案，但是很难求出单个i的答案，所以我们可以运用差分的思想。

　　$H[i]$表示$f(l,r)<=i$的$(l,r)$对数，显然这个是随i增大而单调不降的，考虑怎么计算出这个。

　　$next[l]$表示满足$f(l,r)<=i$的最小的$r$，则有$H[i]=sum_{l=1}^{n}n-next[l]+1$。显然$next[l]$也会随着$i$变小而单调不降，并且$next$数组本身也是单调不降的，于是我们可以从大到小枚举$i$。$i=max(a[i])$的时候显然有$next[i]=i$，接下来只要考虑每次从$i$变成$i-1$的时候$next$数组怎么变化。

　　用一个vector $v[i]$来存下约数里有$i$的数的下标，并且单调递增。设$v[i]$里有下标$x_1,x_2,x_3,...,x_m$，则从$i$变为$i-1$的时候，任何一个$[l,r]$至少包含$m-1$个$x_j$，所以$[x_2+1,n]$这段区间的$next[l]$应该全改为$n+1$，$[x_1+1,x_2]$这段区间的$next[l]$应该改为$max(next[l],x_m)$，$[1,x_1]$这段区间的$next[l]$应该改为$max(next[l],x_{m-1})$，这个可以用线段树来实现。

　　怎么实现呢？刚才我们提到过$next[l]$单调不降，有了这个性质就很好实现了。

　　每个节点维护$mn$和$mx$表示这个区间里的最小的$next$和最大的$next$，如果$mn geq delta$，那就不用再递归这个区间了，如果$mx<delta$，那么直接给这个区间打标记，这么做就能找到需要改的区间了。

　　然后求出$H[i]$就完了...

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=500010;
struct poi{int mx, mn, delta; ll sum;}tree[maxn<<2];
int n, a[maxn], pos[maxn], mx;
ll ans, H[maxn];
vector<int>v[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void change(int x, int l, int r, int delta)
{
    tree[x].mn=tree[x].mx=delta;
    tree[x].sum=1ll*(r-l+1)*delta;
    tree[x].delta=delta;
}
inline void up(int x)
{
    tree[x].mn=min(tree[x<<1].mn, tree[x<<1|1].mn);
    tree[x].mx=max(tree[x<<1].mx, tree[x<<1|1].mx);
    tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
}
inline void down(int x, int l, int r)
{
    if(!tree[x].delta) return;
    int mid=(l+r)>>1;
    change(x<<1, l, mid, tree[x].delta);
    change(x<<1|1, mid+1, r, tree[x].delta);
    tree[x].delta=0;
}
void build(int x, int l, int r)
{
    if(l==r) {tree[x].mn=tree[x].mx=tree[x].sum=l; return;}
    int mid=(l+r)>>1;
    build(x<<1, l, mid); build(x<<1|1, mid+1, r);
    up(x);
}
void update(int x, int l, int r, int cl, int cr, int delta)
{
    if(tree[x].mn>=delta) return;
    down(x, l, r);
    if(cl<=l && r<=cr && tree[x].mx<delta) {change(x, l, r, delta); return;}
    int mid=(l+r)>>1;
    if(cl<=mid) update(x<<1, l, mid, cl, cr, delta);
    if(cr>mid) update(x<<1|1, mid+1, r, cl, cr, delta);
    up(x);
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(a[i]), pos[a[i]]=i, mx=max(mx, a[i]);
    for(int i=1;i<=mx;i++)
    {
        for(int j=i;j<=mx;j+=i)
        if(pos[j]) v[i].push_back(pos[j]);
        sort(v[i].begin(), v[i].end());
    }
    build(1, 1, n);
    for(int i=mx;~i;i--)
    {
        H[i]=1ll*n*n-tree[1].sum+n;
        int m=v[i].size();
        if(m<=1) continue;
        update(1, 1, n, v[i][1]+1, n, n+1);
        update(1, 1, n, v[i][0]+1, v[i][1], v[i][m-1]);
        update(1, 1, n, 1, v[i][0], v[i][m-2]);
    }
    for(int i=1;i<=mx;i++) ans+=1ll*i*(H[i]-H[i-1]);
    printf("%I64d
", ans);
}

View Code

Codeforces 671C. Ultimate Weirdness of an Array（数论+线段树）

相关推荐