P9371 [APIO2023] 序列 题解

Description

link

Solution

首先考虑一个序列的中位数满足什么条件。

设中位数 $a$ 的个数是 $x$，小于中位数的个数是 $y$，大于中位数的个数是 $z$。

那么满足下面两个条件：$x+y\geq z,x+z\geq y$。

转化一下就是：$-x\leq z-y\leq x$。

考虑给区间里小于 $a$ 的数赋一个权值 $-1$，大于 $a$ 的赋 $1$，等于 $a$ 为 $0$。设 $sum_k$ 为权值的前缀和，$cnt_k$ 为这个前缀的 $a$ 的个数。

就是求满足 $cnt_{l-1}-cnt_r\leq sum_r-sum_{l-1}\leq cnt_r-cnt_{l-1}$ 的区间 $[l,r]$ 中最大的 $cnt_r-cnt_{l-1}$。

---

考虑从小到大枚举 $a$，容易发现 $cnt$ 和 $sum$ 都可以用线段树维护，这里不再赘述。

把上面那个式子转化一下得：$sum_{l-1}+cnt_{l-1}\leq sum_r+cnt_r$ 且 $cnt_{l-1}-sum_{l-1}\leq cnt_r-sum_r$。

容易发现这是一个二维偏序的结构，所以把 $(sum_{x}+cnt_{x},cnt_{x}-sum_x)$ 看成一个点，就只要求一个二维偏序了。

暴力是 $O(n^2\log n)$。

---

考虑优化。

观察一下这些点的走势会发现 $A_x=a$ 时会向右上走，$A_x<a$ 向左上，$A_x>a$ 向右下。

于是可以画出样例 2 中 $a=1$ 的图像：

会发现 $cnt$ 相同的点在同一条 $y=-x+2\times cnt$ 的直线上，问题就转化为：给定若干条斜率为 $-1$ 的线段，求出所有线段 $l_1,l_2$，满足 $l_1$ 上存在点在 $l_2$ 的任一点的右上方的最大的 $l_1$ 与 $l_2$ 的距离。

假设给定 $l_2$，那么 $l_1$ 就要满足与下面的阴影有交点：

写成式子就是：$maxx_1\geq minx_2,maxy_1\geq miny_2,cnt_1\geq cnt_2$。容易发现这个式子是充分必要的。

所以只要把每条斜率为 $-1$ 的线段的 $(minx,miny)$ 和 $(maxx,maxy)$ 求出来，跑二维偏序即可。

（树状数组维护 $cnt$ 的最小值，这里不用考虑 $cnt_1\geq cnt_2$ 的条件，因为 $cnt_1 < cnt_2$ 时一定不是最优解。）

均摊下来就是 $O(n\log n)$。

Code

#include "sequence.h"
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

// #define int long long

using pii = std::pair<int, int>;

const int kMaxN = 5e5 + 5;

struct Node {
  int mxx, mxy, mix, miy;

  Node() {}
  Node(int _mxx, int _mxy, int _mix, int _miy) : mxx(_mxx), mxy(_mxy), mix(_mix), miy(_miy) {}
};

struct LYX {
  pii p;
  int op, id;

  LYX() {}
  LYX(pii _p, int _op, int _id) : p(_p), op(_op), id(_id) {}
};

int n;
int a[kMaxN], mxx[kMaxN << 2], mxy[kMaxN << 2], mix[kMaxN << 2], miy[kMaxN << 2], tagx[kMaxN << 2], tagy[kMaxN << 2];
int tr[kMaxN << 2];
std::vector<int> pos[kMaxN];
LYX pp[kMaxN << 1];

bool cmp(const LYX &l1, const LYX &l2) {
  return l1.p.first < l2.p.first;
}

Node merge(Node ls, Node rs) {
  return Node(std::max(ls.mxx, rs.mxx), std::max(ls.mxy, rs.mxy), std::min(ls.mix, rs.mix), std::min(ls.miy, rs.miy));
}

void pushup(int x) {
  mxx[x] = std::max(mxx[x << 1], mxx[x << 1 | 1]);
  mix[x] = std::min(mix[x << 1], mix[x << 1 | 1]);
  mxy[x] = std::max(mxy[x << 1], mxy[x << 1 | 1]);
  miy[x] = std::min(miy[x << 1], miy[x << 1 | 1]);
}

void addtagx(int x, int v) {
  mxx[x] += v, mix[x] += v, tagx[x] += v;
}

void addtagy(int x, int v) {
  mxy[x] += v, miy[x] += v, tagy[x] += v;
}

void pushdown(int x) {
  if (!tagx[x] && !tagy[x]) return;
  if (tagx[x]) addtagx(x << 1, tagx[x]), addtagx(x << 1 | 1, tagx[x]);
  if (tagy[x]) addtagy(x << 1, tagy[x]), addtagy(x << 1 | 1, tagy[x]);
  tagx[x] = tagy[x] = 0;
}

void update(int x, int l, int r, int ql, int qr, int vx, int vy) {
  if (l > qr || r < ql) {
    return;
  } else if (l >= ql && r <= qr) {
    return addtagx(x, vx), addtagy(x, vy);
  }
  pushdown(x);
  int mid = (l + r) >> 1;
  update(x << 1, l, mid, ql, qr, vx, vy), update(x << 1 | 1, mid + 1, r, ql, qr, vx, vy);
  pushup(x);
}

Node query(int x, int l, int r, int ql, int qr) {
  if (l > qr || r < ql) {
    return Node(-1e9, -1e9, 1e9, 1e9);
  } else if (l >= ql && r <= qr) {
    return Node(mxx[x], mxy[x], mix[x], miy[x]);
  }
  pushdown(x);
  int mid = (l + r) >> 1;
  Node ls = query(x << 1, l, mid, ql, qr), rs = query(x << 1 | 1, mid + 1, r, ql, qr);
  return merge(ls, rs);
}

void upd(int x, int v) {
  for (; x <= 2e6; x += x & -x)
    tr[x] = std::min(tr[x], v);
}

int qry(int x) {
  int ret = 1e9;
  for (; x; x -= x & -x)
    ret = std::min(ret, tr[x]);
  return ret;
}

void clr(int x) {
  for (; x <= 2e6; x += x & -x)
    tr[x] = 1e9;
}

int solve(int val = 1) {
  for (int i = 1; i <= n; ++i)
    update(1, 0, n, i, n, 1, -1);
  int ret = 0;
  memset(tr, 0x3f, sizeof(tr));
  for (int i = 1; i <= n; ++i) {
    for (auto x : pos[i])
      if (x && x <= n) update(1, 0, n, x, n, 0, 2);
    int cnt = 0;
    for (int j = 0; j + 1 < static_cast<int>(pos[i].size()); ++j) {
      auto p = query(1, 0, n, pos[i][j], pos[i][j + 1] - 1);
      pp[++cnt] = LYX(std::make_pair(p.mix, p.miy), 0, j);
      pp[++cnt] = LYX(std::make_pair(p.mxx, p.mxy), 1, j);
    }
    std::sort(pp + 1, pp + 1 + cnt, cmp);
    int now = 0;
    for (int j = 1, k; j <= cnt; j = k) {
      now = j;
      for (k = j; k <= cnt && pp[k].p.first == pp[j].p.first; ++k)
        if (pp[k].op == 0)
          upd(pp[k].p.second + 1e6, pp[k].id);
      for (int s = j; s < k; ++s)
        if (pp[s].op == 1)
          ret = std::max(ret, pp[s].id - qry(pp[s].p.second + 1e6));
    }
    for (int k = 1; k < now; ++k)
      clr(pp[k].p.second + 1e6);
    for (auto x : pos[i])
      if (x && x <= n) update(1, 0, n, x, n, -2, 0);
  }
  return ret;
}

int sequence(int N, std::vector<int> A) {
  n = N;
  for (int i = 0; i < n; ++i)
    a[i + 1] = A[i];
  for (int i = 1; i <= n; ++i)
    pos[i].emplace_back(0);
  for (int i = 1; i <= n; ++i)
    pos[a[i]].emplace_back(i);
  for (int i = 1; i <= n; ++i)
    pos[i].emplace_back(n + 1);
  return solve();
}