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

　　看见$a_i\leq 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=;

struct poi{int mx, mn, delta; ll sum;}tree[maxn<<];

int n, a[maxn], pos[maxn], mx;

ll ans, H[maxn];

vector<int>v[maxn];

inline void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-' && (f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', 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+)*delta;

    tree[x].delta=delta;

}

inline void up(int x)

{

    tree[x].mn=min(tree[x<<].mn, tree[x<<|].mn);

    tree[x].mx=max(tree[x<<].mx, tree[x<<|].mx);

    tree[x].sum=tree[x<<].sum+tree[x<<|].sum;

}

inline void down(int x, int l, int r)

{

    if(!tree[x].delta) return;

    int mid=(l+r)>>;

    change(x<<, l, mid, tree[x].delta);

    change(x<<|, mid+, r, tree[x].delta);

    tree[x].delta=;

}

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)>>;

    build(x<<, l, mid); build(x<<|, mid+, 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)>>;

    if(cl<=mid) update(x<<, l, mid, cl, cr, delta);

    if(cr>mid) update(x<<|, mid+, r, cl, cr, delta);

    up(x);

}

int main()

{

    read(n);

    for(int i=;i<=n;i++) read(a[i]), pos[a[i]]=i, mx=max(mx, a[i]);

    for(int i=;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(, , n);

    for(int i=mx;~i;i--)

    {

        H[i]=1ll*n*n-tree[].sum+n;

        int m=v[i].size();

        if(m<=) continue;

        update(, , n, v[i][]+, n, n+);

        update(, , n, v[i][]+, v[i][], v[i][m-]);

        update(, , n, , v[i][], v[i][m-]);

    }

    for(int i=;i<=mx;i++) ans+=1ll*i*(H[i]-H[i-]);

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

}

巴特西

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

最新文章

热门文章