APIO2023 T2 题解
Un1quAIoid
·
·
题解
题目大意：
给定序列 a_{1, \dots, n}，定义 S_{l,r} 为 a_{l,\dots,r} 的中位数集合（大小为 1 或 2），w_{l,r,x} = \sum_{i=l}^r [a_i=x]，求 \max_{1 \le l \le r \le n} \max_{x \in S_{l,r}} w(l,r,x)。
-------------------
小清新数据结构。
容易想到枚举中位数的值，设为 $x$，将序列中 $<x$ 的位置赋为 $0$，$>x$ 的位置赋为 $1$，目标即为计算所有 $x$ 是中位数的区间中 $x$ 的最大出现次数。
**step1**
先来考虑 $x \in S_{l,r}$ 的等价条件是什么，设区间中 $x$ 的出现次数为 $c$，$0$ 的出现次数为 $c_0$，$1$ 的出现次数为 $c_1$，不难得到：
$$
\begin{aligned}
&x \in S_{l,r}\\
\Leftrightarrow
&\begin{cases}
c+c_0 \ge c_1\\
c+c_1 \ge c_0\\
\end{cases}\\
\Leftrightarrow &\max(c_1-c_0-c,c_0-c_1-c) \le 0
\end{aligned}
$$
设 $u_{i} = w(1,i,1)-w(1,i,0)-w(1,i,x)$，$v_i = w(1,i,0)-w(1,i,1)-w(1,i,x)$，那么 $x \in S_{l,r}$ 当且仅当 $\max(u_r-u_{l-1}, v_r - v_{l-1}) \le 0$，将 $p_i=(u_i, v_i)$ 看作二维平面上的一个点，这个条件实际上就是在说 $p_r$ 在 $p_{l-1}$ 的左下方。
**step2**
现在再来观察 $p_{i-1}$ 和 $p_i$ 之间的位置关系。如果 $a_i = x$，那么 $p_{i}$ 是 $p_{i-1}$ 向左下走一步；如果 $a_i = 0$，那么是向左上走一步；如果 $a_i=1$，那么是向右下走一步。画出来会像下图：
画出来就能一眼看出这张图的特点：由若干条（准确来说是 $w(1,n,x)+1$ 条）斜率为 $-1$ 的线段以及连接它们的斜率为 $1$ 的线段组成。现在我们的目标就变成了找到相距最远的两条斜率为 $-1$ 线段（距离定义为从一条走到另一条需要向左下走的次数），满足能够从其上面分别找出一个点满足一个在另一个的左下方。
考虑能够找出这样两个点的等价条件是什么，不妨来看上图中的线段 BC 和 DE，画一下图就能得出条件：
$$
\begin{cases}
C_x \ge D_x\\
B_y \ge E_y\\
\end{cases}
$$
二维数点的形式。使用 BIT，支持单点修改，后缀 $\min$ 即可；第 $i$ 条斜率为 $-1$ 的线段实际上就是点 $x$ 的第 $i-1$ 次出现位置到第 $i$ 次出现位置之间的所有位置对应的点的集合，所以线段端点的横纵坐标只需要使用线段树，支持区间加，区间 $\max \And \min$ 即可。
总复杂度 $O(n \log n)$。
代码：
```cpp
//#include "sequence.h"
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') f = c == '-' ? -1 : 1, c = getchar();
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
typedef long long ll;
const int N = 5e5+5;
const int Mod = 998244353;
const int INF = 0x3f3f3f3f;
int n, a[N], ans;
vector<int> pos[N];
struct segT {
struct node {
int mx, mn, ad;
} T[N << 2];
#define ls (p << 1)
#define rs (p << 1 | 1)
inline void push_up(int p) {
T[p].mx = max(T[ls].mx, T[rs].mx) + T[p].ad;
T[p].mn = min(T[ls].mn, T[rs].mn) + T[p].ad;
}
void upd(int p, int l, int r, int gl, int gr, int k) {
if (l >= gl && r <= gr) {
T[p].mx += k, T[p].mn += k;
T[p].ad += k;
return;
}
int mid = (l + r) >> 1;
if (mid >= gl) upd(ls, l, mid, gl, gr, k);
if (mid < gr) upd(rs, mid + 1, r, gl, gr, k);
push_up(p);
}
int qry_mn(int p, int l, int r, int gl, int gr) {
if (l >= gl && r <= gr) return T[p].mn;
int mid = (l + r) >> 1, ret = INF;
if (mid >= gl) ret = qry_mn(ls, l, mid, gl, gr);
if (mid < gr) ret = min(ret, qry_mn(rs, mid + 1, r, gl, gr));
return ret + T[p].ad;
}
int qry_mx(int p, int l, int r, int gl, int gr) {
if (l >= gl && r <= gr) return T[p].mx;
int mid = (l + r) >> 1, ret = -INF;
if (mid >= gl) ret = qry_mx(ls, l, mid, gl, gr);
if (mid < gr) ret = max(ret, qry_mx(rs, mid + 1, r, gl, gr));
return ret + T[p].ad;
}
#undef ls
#undef rs
} Tx, Ty;
int cnt;
struct opt {
int op, x, y, k;//0询问，1修改
} P[N * 2];
struct Hsh {
int v[N * 2], c;
int operator [](int x) { return v[x]; }
inline void ins(int x) { v[++c] = x; }
inline void init() {
sort(v + 1, v + c + 1);
c = unique(v + 1, v + c + 1) - v - 1;
}
inline int f(int x) { return lower_bound(v + 1, v + c + 1, x) - v; }
} H;
struct BIT {
int T[N * 2];
inline void upd(int x, int k) { for (; x; x -= lowbit(x)) T[x] = min(T[x], k); }
inline int qry(int x) { int ret = INF; for (; x <= H.c; x += lowbit(x)) ret = min(ret, T[x]); return ret; }
inline void clr(int x) { for (; x; x -= lowbit(x)) T[x] = INF; }
} T;
inline void work() {//二维数点
sort(P + 1, P + cnt + 1, [](opt a, opt b) { return a.x == b.x ? a.op > b.op : a.x > b.x; });
H.c = 0;
for (int i = 1; i <= cnt; i++) H.ins(P[i].y);
H.init();
for (int i = 1; i <= cnt; i++) {
P[i].y = H.f(P[i].y);
if (P[i].op == 1) T.upd(P[i].y, P[i].k);
else ans = max(ans, P[i].k - T.qry(P[i].y));
}
for (int i = 1; i <= cnt; i++) T.clr(P[i].y);
}
int sequence(int N, std::vector<int> A) {
n = N;
for (int i = 1; i <= n; i++) pos[A[i - 1]].pb(i);
memset(T.T, 0x3f, sizeof(T.T));
for (int i = 1; i <= n; i++) Tx.upd(1, 0, n, i, i, i), Ty.upd(1, 0, n, i, i, -i);
for (int i = 1; i <= n; i++) if (!pos[i].empty()) {
for (int j : pos[i])//from c1 to c
Tx.upd(1, 0, n, j, n, -2);
cnt = 0;
pos[i].pb(n + 1);
int k = pos[i].size(), lst = 0;
for (int j = 0; j < k; j++) {
int cur = pos[i][j];
int mn_x = Tx.qry_mn(1, 0, n, lst, cur - 1), mn_y = Ty.qry_mn(1, 0, n, lst, cur - 1);
int mx_x = Tx.qry_mx(1, 0, n, lst, cur - 1), mx_y = Ty.qry_mx(1, 0, n, lst, cur - 1);
P[++cnt] = (opt) { 1, mx_x, mx_y, j };
P[++cnt] = (opt) { 0, mn_x, mn_y, j };
lst = cur;
}
work();
pos[i].pop_back();
for (int j : pos[i])//from c to c0
Ty.upd(1, 0, n, j, n, 2);
}
return ans;
}
//int main() {
// int n;
// vector<int> A;
// scanf("%d", &n); A.resize(n);
// for (int i = 0; i < n; i++) scanf("%d", &A[i]);
//
// printf("%d", sequence(n, A));
// return 0;
//}
```