题解 P5502 【[JSOI2015]最大公约数】

· · 题解

对于这类求一段区间的权值 =length * value 的max或min值题目，相信大家都不陌生吧。这是一类非常经典的题目，一般采取用分治的思想解决。

我们考虑将 [l,r] 区间的答案转化为 [l,mid] 和 [mid+1,r] 以及合并产生的更优答案，其中mid = \lfloor \frac{l+r}{2} \rfloor。

显然，重点是如何合并两段区间，找出更优的答案。

我们采用类似归并排序的思路，在归并排序的时候，由于需要采取数从小到大的原则，所以我们的cmp函数是[a < b]。

类比过来，对于此题已知了g = gcd(a[x],a[x+1],a[x+2],...a[y])，我们的cmp函数即为[gcd(g,a[x-1])<gcd(g,a[y+1])]，大功告成。

%:pragma GCC optimize(2)
%:pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define lll __int128

const int N = 100005;

ll a[N];
int n;

ll gcd(ll x, ll y) {
  return y ? gcd(y, x % y) : x;
}

ll dfs(int l, int r) {
  if (l == r) return a[l];
  int mid = (l + r) >> 1;
  ll ans = max(dfs(l, mid), dfs(mid + 1, r));
  ll g = gcd(a[mid], a[mid + 1]);
  ans = max(ans, 2LL * g);

  int x = mid, y = mid + 1;
  while (x > l && y < r) {
    if (gcd(g, a[x - 1]) > gcd(g, a[y + 1])) {
      g = gcd(g, a[x - 1]); x--;
    }
    else {
      g = gcd(g, a[y + 1]); y++;
    }
    ans = max(ans, (ll)(y - x + 1) * g);
  } 
  while (x > l) {
    g = gcd(g, a[x - 1]); x--;
    ans = max(ans, (ll)(y - x + 1) * g);
  }
  while (y < r) {
    g = gcd(g, a[y + 1]); y++;
    ans = max(ans, (ll)(y - x + 1) * g);
  }
  return ans;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
  }
  printf("%lld\n", dfs(1, n));
  return 0;
}

我曾经做过一道题目，题面是求max\{ (r-l+1) \times max\{ a[l],a[l+1],...,a[r] \} \}。

读者可以考虑一下，此时我们的cmp函数即为[max(a[l-1],Max)<max(a[r+1],Max)]，其余均不变。

题目可在我私人团队里提交，跳转链接 ： 区间Max

也贴下代码，供读者理解：

%:pragma GCC optimize(2)
%:pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define lll __int128
#define dd double
#define _i int
#define RE register
#define rep(i, l, r) for (RE int i = l; i <= r; i++)
#define req(i, l, r) for (RE int i = l; i >= r; i--)
#define range(i, l, r) rep(i, l, r - 1)
#define Be(s, t) memset(s, t, sizeof(s))
#define poly vector <int>
#define pii pair <int, int>
template <typename T> void read(T &x) { x = 0; int FF = 1; char op = getchar(); while (!isdigit(op)) { if (op == '-') FF = -1; op = getchar(); } while (isdigit(op)) { x = (x << 1) + (x << 3) + op - '0'; op = getchar(); } x *= FF; }
template <typename T> void print(T x) { if (x < 0) { putchar('-'); x = -x; } if (x < 1) return ; print(x / 10); putchar(x % 10 + '0'); }
template <typename T> void print(T x, char _tab) { print(x); putchar(_tab); }

const int N = 500005;
ll a[N];
int n;

ll dfs(int l, int r) {
  if (l == r) return a[l];
  int mid = (l + r) >> 1;
  ll ans = max(dfs(l, mid), dfs(mid + 1, r));
  ll x = mid, y = mid + 1, h = min(a[x], a[y]);
  ans = max(ans, 2 * h);
  while (x > l && y < r) {
    if (a[x - 1] < a[y + 1]) h = min(h, a[++y]);
    else h = min(h, a[--x]);
    ans = max(ans, (ll)(y - x + 1) * h);
  }
  while (x > l) {
    h = min(h, a[--x]);
    ans = max(ans, (ll)(y - x + 1) * h);
  }
  while (y < r) {
    h = min(h, a[++y]);
    ans = max(ans, (ll)(y - x + 1) * h);
  }
  return ans;
}

int main() {
  read(n);
  rep(i, 1, n) read(a[i]);
  print(dfs(1, n), '\n');
  return 0;
}