自动搬运

查看原文

来自洛谷，原作者为

	Un1quAIoid **

搬运于2025-08-24 22:47:46，当前版本为作者最后更新于2023-05-23 17:43:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目大意：

给定序列 $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)$。

$n \le 5 \times 10^5$。

---

小清新数据结构。

容易想到枚举中位数的值，设为 $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)$。

代码：

//#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;
//}