Ultimate Weirdness of an Array CodeForces

大意: 定义一个数列的特征值为两个数gcd的最大值, $f(l,r)$表示数列删除区间$[l,r]$的元素后剩余元素的特征值, 求$\sum_{i=1}^n\sum_{j=i}^n{f(i,j)}$

怎么这div.1的C怎么这么难.....好像D过的人比C还要多.

特征值不好处理, 考虑将贡献转为前缀

即转化为对于所有的$x$, 求出$H[x]=\space f(l,r)\le x$的个数, 显然$H[x]$是单调不减的.

记$next[x]_l=\space f(l,r)\le x$的最小$r$, 就有$H[x]=\sum\limits_{i=1}^n(n+1-next[x]_i)$

显然$next[x]$是单调不增的, 考虑如何维护$next$.

我们从大到小枚举$x$, 这样初始$next[x]_i=i$, 考虑$x$变为$x-1$时, 每个位置的$next$值如何变化.

可以先枚举$gcd$, 预处理出$a_i|gcd$的位置$i$, 假设为$v_1,v_2,...,v_{m-1},v_{m}$.

那么显然对于$[v_2+1,n]$位置的$next$值与$n+1$取最大.

对于$[v_1+1,v_2]$位置的$next$值与$v_m$取最大.

对于$[1,v_1]$位置的$next$值与$v_{m-1}$取最大.

所以就需要支持区间取最大值, 区间求和, 可以用$STL$的$set$或线段树实现, 复杂度都是$O(nlog^2n)$

#include <iostream>

#include <algorithm>

#include <cstdio>

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define mid ((l+r)>>1)

#define lc (o<<1)

#define rc (lc|1)

#define ls lc,l,mid

#define rs rc,mid+1,r

using namespace std;

typedef long long ll;

const int N = 1e6+10, INF = 0x3f3f3f3f;

int n, mx, a[N];

struct {

	int ma,mi,tag;

	ll sum;

	void upd(int x, int t) {

		ma=mi=tag=x, sum=(ll)t*x;

	}

} tr[N<<2];

int L1[N], L2[N], R1[N], R2[N];

ll H[N];

void pu(int o) {

	tr[o].ma = max(tr[lc].ma,tr[rc].ma);

	tr[o].mi = min(tr[lc].mi,tr[rc].mi);

	tr[o].sum = tr[lc].sum+tr[rc].sum;

}

void pd(int o, int l, int r) {

	if (tr[o].tag) {

		tr[lc].upd(tr[o].tag,mid-l+1);

		tr[rc].upd(tr[o].tag,r-mid);

		tr[o].tag = 0;

	}

}

void build(int o, int l, int r) {

	if (l==r) return tr[o].upd(l,1);

	build(ls),build(rs);

	pu(o);

}

void update(int o, int l, int r, int ql, int qr, int v) {

	if (ql>qr||tr[o].mi>=v) return;

	if (ql<=l&&r<=qr&&tr[o].ma<=v) return tr[o].upd(v,r-l+1);

	pd(o,l,r);

	if (mid>=ql) update(ls,ql,qr,v);

	if (mid<qr) update(rs,ql,qr,v);

	pu(o);

}

int main() {

	scanf("%d", &n);

	REP(i,1,n) {

		int t;

		scanf("%d", &t);

		a[t] = i;

		mx = max(mx, t);

	}

	REP(i,1,mx) {

		for (int j=i; j<=mx; j+=i) if (a[j]) {

			if (!L1[i]||L1[i]>a[j]) L2[i] = L1[i], L1[i] = a[j];

			else if (!L2[i]||L2[i]>a[j]) L2[i] = a[j];

			if (R1[i]<a[j]) R2[i] = R1[i], R1[i] = a[j];

			else if (R2[i]<a[j]) R2[i] = a[j];

		}

	}

	build(1,1,n);

	PER(i,1,mx) {

		if (L1[i]!=R1[i]) {

			update(1,1,n,1,L1[i],R2[i]);

			update(1,1,n,L1[i]+1,L2[i],R1[i]);

			update(1,1,n,L2[i]+1,n,n+1);

		}

		H[i] = (ll)(n*(n+1))-tr[1].sum;

	}

	ll ans = 0;

	REP(i,1,mx-1) {

		ans += (ll)i*(H[i+1]-H[i]);

	}

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

}

巴特西

Ultimate Weirdness of an Array CodeForces - 671C (gcd,线段树)

最新文章

热门文章