30pts
暴力搜索
我们可以把除了 的数都加到一个 里，然后两两搜索计算 ,找出最大值，加和然后输出，时间复杂度
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
while (b) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
long long sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
vector<int> A;
for (int k = 0; k < i; ++k) {
A.push_back(a[k]);
}
for (int k = j + 1; k < n; ++k) {
A.push_back(a[k]);
}
if (A.size() < 2) {
continue;
}
int max_gcd = 0;
for (int p = 0; p < A.size(); ++p) {
for (int q = p + 1; q < A.size(); ++q) {
max_gcd = max(max_gcd, gcd(A[p], A[q]));
}
}
sum += max_gcd;
}
}
cout << sum << endl;
return 0;
}
70pts
先预处理出，每个数值在序列里第一次和最后一次出现的位置。再枚举每个数值的倍数（时间复杂度是调和级数），求出每个值的倍数在序列里第一次和最后一次出现的位置。
考虑求 。设 取到最大值的两个位置为 ，不失一般性地设 。可以分三种情况:
- 全都在 内部。
- 全部在 内部。
- 在 , y 在 。
前两种情况是类似的。以第一种为例。从小到大枚举 。显然答案是单调不降的。 的答案相比于 的答案，其实就是多出了 的情况。考虑这种情况的 是多少。可以暴力枚举 的所有约数，看这个约数第一次出现的位置（前面已经预处理出来）是否小于 ，然后用这个约数更新答案。
因为每个数至多只有 个约数，所以暴力实现的时间复杂度是 。但是发现，如果当前 这个值在前面已经出现过，那 这个数直接可以更新答案，这一定比它的任何约数都优，因此此时就不必枚举约数了。于是，对每个数值，我们只枚举一次约数，时间复杂度就是 里所有数的约数个数和，是 的。
对于第三种情况。考虑从小到大枚举 ，在线段树上维护所有 的答案。仍然考虑从 变到 对答案的影响。发现只多出了 , 的情况。枚举 的所有约数，设它最后一次出现的位置为 ，则 的答案可以被更新（也就是对这个约数取 )。另外， 这个位置的答案需要被清空。综上，我们需要一个数据结构，支持:
- 让一段区间对一个数取 。
- 更改一个单点的数值（设为 )。
- 求全局和。
可以用吉司机线段树维护，单次操作时间复杂度是 的。因为要枚举约数，总时间复杂度 。和前面类似，我们发现，同一个 的值，如果在之前出现过，则现在并不会有新的价值。于是每个数值只枚举一次约数（并做线段树操作），时间复杂度 。
总时间复杂度 。
#include <bits/stdc++.h>
using namespace std;
#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template <typename T>
inline void ckmax(T& x, T y) {
x = (y > x ? y : x);
}
template <typename T>
inline void ckmin(T& x, T y) {
x = (y < x ? y : x);
}
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
if (S == T) {
T = (S = buf) + fread(buf, 1, SIZE, stdin);
if (S == T)
return '\n';
}
return *S++;
}
}
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
fwrite(buf, 1, S - buf, stdout);
S = buf;
}
inline void putchar(char c) {
*S++ = c;
if (S == T)
flush();
}
struct NTR {
~NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread ::getchar
#define putchar Fwrite ::putchar
#endif
namespace Fastio {
struct Reader {
template <typename T>
Reader& operator>>(T& x) {
char c = getchar();
T f = 1;
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
x = 0;
while (c >= '0' && c <= '9') {
x = x * 10 + (c - '0');
c = getchar();
}
x *= f;
return *this;
}
Reader& operator>>(char& c) {
c = getchar();
while (c == '\n' || c == ' ') c = getchar();
return *this;
}
Reader& operator>>(char* str) {
int len = 0;
char c = getchar();
while (c == '\n' || c == ' ') c = getchar();
while (c != '\n' && c != ' ') {
str[len++] = c;
c = getchar();
}
str[len] = '\0';
return *this;
}
Reader() {}
} cin;
const char endl = '\n';
struct Writer {
template <typename T>
Writer& operator<<(T x) {
if (x == 0) {
putchar('0');
return *this;
}
if (x < 0) {
putchar('-');
x = -x;
}
static int sta[45];
int top = 0;
while (x) {
sta[++top] = x % 10;
x /= 10;
}
while (top) {
putchar(sta[top] + '0');
--top;
}
return *this;
}
Writer& operator<<(char c) {
putchar(c);
return *this;
}
Writer& operator<<(char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator<<(const char* str) {
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer() {}
} cout;
}
#define cin Fastio ::cin
#define cout Fastio ::cout
#define endl Fastio ::endl
const int MAXN = 2e5;
const int INF = 1e9;
int n, a[MAXN + 5];
int fstpos[MAXN + 5], lstpos[MAXN + 5];
vector<int> d[MAXN + 5];
bool vis[MAXN + 5];
int f[MAXN + 5];
struct SegmentTree {
ll sum[MAXN * 4 + 5];
ll mn[MAXN * 4 + 5], semn[MAXN * 4 + 5];
int mncnt[MAXN * 4 + 5];
void push_up(int p) {
int ls = (p << 1), rs = (p << 1 | 1);
sum[p] = sum[ls] + sum[rs];
if (mn[ls] < mn[rs]) {
mn[p] = mn[ls];
mncnt[p] = mncnt[ls];
semn[p] = min(semn[ls], mn[rs]);
} else if (mn[ls] > mn[rs]) {
mn[p] = mn[rs];
mncnt[p] = mncnt[rs];
semn[p] = min(semn[rs], mn[ls]);
} else {
mn[p] = mn[ls];
mncnt[p] = mncnt[ls] + mncnt[rs];
semn[p] = min(semn[ls], semn[rs]);
}
}
void push_down(int p) {
int ls = (p << 1), rs = (p << 1 | 1);
if (mn[p] > mn[ls]) {
assert(mn[p] < semn[ls]);
sum[ls] += (ll)mncnt[ls] * (mn[p] - mn[ls]);
mn[ls] = mn[p];
}
if (mn[p] > mn[rs]) {
assert(mn[p] < semn[rs]);
sum[rs] += (ll)mncnt[rs] * (mn[p] - mn[rs]);
mn[rs] = mn[p];
}
}
template <typename Tp>
void build(int p, int l, int r, const Tp* arr) {
if (l == r) {
sum[p] = arr[l];
mn[p] = arr[l];
semn[p] = INF;
mncnt[p] = 1;
return;
}
int mid = (l + r) >> 1;
build(p << 1, l, mid, arr);
build(p << 1 | 1, mid + 1, r, arr);
push_up(p);
}
void range_ckmax(int p, int l, int r, int ql, int qr, ll v) {
if (v <= mn[p]) {
return;
}
if (ql <= l && qr >= r) {
if (v < semn[p]) {
sum[p] += (ll)mncnt[p] * (v - mn[p]);
mn[p] = v;
return;
}
}
int mid = (l + r) >> 1;
push_down(p);
if (ql <= mid) {
range_ckmax(p << 1, l, mid, ql, qr, v);
}
if (qr > mid) {
range_ckmax(p << 1 | 1, mid + 1, r, ql, qr, v);
}
push_up(p);
}
void point_clear(int p, int l, int r, int pos) {
if (l == r) {
sum[p] = 0;
mn[p] = 0;
semn[p] = INF;
mncnt[p] = 1;
return;
}
int mid = (l + r) >> 1;
push_down(p);
if (pos <= mid) {
point_clear(p << 1, l, mid, pos);
} else {
point_clear(p << 1 | 1, mid + 1, r, pos);
}
push_up(p);
}
SegmentTree() {}
};
SegmentTree T;
int main() {
cin >> n;
for (int i = 1; i <= MAXN; ++i) {
fstpos[i] = n + 1;
lstpos[i] = 0;
}
for (int i = 1; i <= n; ++i) {
cin >> a[i];
lstpos[a[i]] = i;
}
for (int i = n; i >= 1; --i) {
fstpos[a[i]] = i;
}
for (int i = 1; i <= MAXN; ++i) {
for (int j = i; j <= MAXN; j += i) {
ckmax(lstpos[i], lstpos[j]);
ckmin(fstpos[i], fstpos[j]);
d[j].push_back(i);
}
}
for (int i = n - 1; i >= 1; --i) {
f[i] = f[i + 1];
if (!vis[a[i + 1]]) {
vis[a[i + 1]] = 1;
for (int j = 0; j < SZ(d[a[i + 1]]); ++j) {
int x = d[a[i + 1]][j];
if (lstpos[x] > i + 1) {
ckmax(f[i], x);
}
}
} else {
ckmax(f[i], a[i + 1]);
}
}
for (int i = 1; i <= MAXN; ++i) vis[i] = 0;
T.build(1, 1, n, f);
ll ans = T.sum[1];
f[1] = 0;
for (int i = 2; i <= n; ++i) {
T.point_clear(1, 1, n, i - 1);
f[i] = f[i - 1];
if (!vis[a[i - 1]]) {
vis[a[i - 1]] = 1;
for (int j = 0; j < SZ(d[a[i - 1]]); ++j) {
int x = d[a[i - 1]][j];
if (lstpos[x] >= i + 1) {
T.range_ckmax(1, 1, n, i, lstpos[x] - 1, x);
}
if (fstpos[x] < i - 1) {
ckmax(f[i], x);
}
}
} else {
ckmax(f[i], a[i - 1]);
}
T.range_ckmax(1, 1, n, i, n, f[i]);
ans += T.sum[1];
}
cout << ans << endl;
return 0;
}
100pts
一般这种题可以先考虑枚举左端点，然后看所有右端点的整体贡献，但这道题要求 很不友好，无法这么处理。稍微转换一下思路，枚举答案，求每种答案的方案数，根据差分思想可以考虑求答案 的总方案数（下文称为 )，这样对于每个 求完之后可以差分得到某个值的答案，这样最终答案的计算是简单的。
设 为当前枚举的答案上界，我们尝试求出 的合法 数量。首先观察到当 为极大值的时候，所有区间都是符合条件的，因此我们考虑从大到小枚举 每次修改贡献的变化量。
固定现在枚举到的 ，设 为对于第 个数，在保证 的条件下的最小的 ，若不存在这样的 则 。于是有:
所以只需要考虑维护 的和即可，现在考虑当 变为 我们修改什么。显然地，对于所有答案等于 的区间我们需要舍去，而只有是 的倍数的数才能造成贡献。在某个所选区间外（即没有删除的数中)， 的倍数至多出现一次时，此区间才可以合法，换句话说，我们需要将所有区间外存在多个 的倍数的区间扩展，考虑分类讨论进行扩展。
设 , , , 表示 的倍数的出现位置 ，分以下几种进行讨论:
- : 此时区间左侧没有 的倍数，所以我们可以让区间右侧出现至多一个 的倍数，有
- : 此时区间左侧有一个 的倍数，所以我们必须让区间包括右侧所有 的倍数，有
- : 此时我们不论如何修改 都没有合法的值，因为区间左侧永远有至少两个 的倍数，所以 。
我们知道维护逻辑后考虑维护方式，这个东西是一个区间对某个数取 ，全局询问和的东西。 单纯的维护是较为困难的，我们需要注意到 在 固定时的取值是单调不降的，也就是说区间 对某数 取 等价于将某段区间 全都赋值为 （也可能完全不赋值），这个东西是可以用线段树上二分解决的。所以考虑将 扔到线段树上维护，线段树上二分时需要注意边界以及返回条件。
目前为止还没有提到 的求法，我们发现只有 是有用的，所以对于每个数字只需要求出其倍数的前两次出现和后两次出现即可。维护方式是简单的，首先预处理每个数的约数，复杂度是 的，然后对于每个输入的 都枚举其因数，用 去更新维护的 ，详见代码。这里因为 互不相同所以复杂度是调和级数的，如果 都拉满并且相同，那预处理复杂度上界应该就是 了。
最后注意所有 初值都有 。 代码实现需要注意的地方:
- 求和需要开 。
- 线段树上二分注意边界，尤其是左端点大于右端点的情况。
时间复杂度 。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned long long UIT;
typedef double DB;
typedef pair<long long, long long> PII;
#define fi first
#define se second
const long long N = 2e5 + 5;
long long n, a[N], l[N][2], r[N][2];
LL val[N];
vector<long long> d[N];
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
const long long TN = 8e5 + 5;
struct Seg_Tree {
struct Seg_Tree_Node {
long long mnv, mxv, lazy;
LL sum;
} t[TN];
void tag(long long rt, long long L, long long R, long long val) {
t[rt].mnv = t[rt].mxv = t[rt].lazy = val;
t[rt].sum = 1LL * (R - L + 1) * t[rt].mnv;
}
void push_up(long long rt) {
t[rt].sum = t[ls(rt)].sum + t[rs(rt)].sum;
t[rt].mnv = min(t[ls(rt)].mnv, t[rs(rt)].mnv);
t[rt].mxv = max(t[ls(rt)].mxv, t[rs(rt)].mxv);
}
void push_down(long long rt, long long L, long long R) {
if (!t[rt].lazy)
return;
long long mid = L + R >> 1;
tag(ls(rt), L, mid, t[rt].lazy), tag(rs(rt), mid + 1, R, t[rt].lazy);
t[rt].lazy = 0;
}
void change(long long rt, long long L, long long R, long long l, long long r, long long val) {
if (l > r || t[rt].mnv >= val)
return;
if (L >= l && R <= r && t[rt].mxv <= val)
return tag(rt, L, R, val);
push_down(rt, L, R);
long long mid = L + R >> 1;
if (l <= mid)
change(ls(rt), L, mid, l, r, val);
if (r > mid)
change(rs(rt), mid + 1, R, l, r, val);
push_up(rt);
}
} T;
void init() {
for (long long i = 1; i <= N - 5; i++)
for (long long j = i; j <= N - 5; j += i) d[j].push_back(i);
}
int main() {
init();
scanf("%lld", &n);
for (long long i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
for (auto j : d[a[i]]) {
if (!l[j][0])
l[j][0] = i;
else if (!l[j][1])
l[j][1] = i;
r[j][1] = r[j][0], r[j][0] = i;
}
}
for (long long i = 1; i <= n; i++) T.change(1, 1, n, i, i, i);
for (long long i = N - 4; i; i--) {
if (l[i][0] != r[i][0]) {
T.change(1, 1, n, 1, l[i][0], r[i][1]);
T.change(1, 1, n, l[i][0] + 1, l[i][1], r[i][0]);
T.change(1, 1, n, l[i][1] + 1, n, n + 1);
}
val[i] = 1LL * n * (n + 1) - T.t[1].sum;
}
LL ans = 0;
for (long long i = 1; i <= N - 5; i++) ans += (val[i + 1] - val[i]) * i;
printf("%lld", ans);
return 0;
}