题解：P5500 [LnOI2019] 真正的 OIer 从不女装

· · 题解

Link

线段树思维好题。

考虑一次女装操作的本质：

设原序列为

a_1, a_{2},\dots, a_{n-1}, a_{n}

选择一个整数 p\in [1,n]，序列将变成

a_p, a_{p-1}, \dots, a_2, a_1, a_n, a_{n-1}, \dots, a_{p+2}, a_{p+1}

由于把整个序列翻转不会对答案产生影响，所以将整个序列翻转后会变成

a_{p+1}, a_{p+2}, \dots, a_{n-1}, a_n, a_1, a_2, \dots, a_{p-1}, a_p

也就是说，一次女装操作可以看成将一个区间的前任意项挪到区间末尾。

那经过转化操作后，这道题就很简单了，用一个线段树维护区间最长相同颜色色块长度即可，这个想必大家都会做。

当然还要考虑 k 对答案的影响。如果把序列放到一个环上，一次女装操作相当于把这个环旋转了任意角度。所以任意次女装操作的结果都可以通过一次女装操作来完成。也就可以不用考虑 k 的具体值了，只需要知道 k 是否大于 0 即可。

如果 k 大于 0，那么还要考虑一下序列旋转后是否可以更优，然后就做完了。具体怎么知道序列选转后的最优答案，可以看看下面的参考代码。

::::success[AC 代码]

// Problem: P5500 [LnOI2019] 真正的 OIer 从不女装
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5500
// Memory Limit: 500 MB
// Time Limit: 1000 ms

#include <iostream>
#include <algorithm>

namespace Qwarth {

const int N = 200007;

int a[N];

struct SegmentTree {

    int tag[N << 2];

    struct node {
        int n, lv, rv, m, lm, rm; // n: 序列长度 lv/rv: 序列左/右端颜色 m: 序列最长色块长度 lm/rm: 前/后缀相同色块长度
    } f[N << 2];

    node merge(node a, node b) {
        node res;
        res.n = a.n + b.n;
        res.lv = a.lv;
        res.rv = b.rv;
        res.m = std::max({ a.m, b.m, (a.rv == b.lv ? a.rm + b.lm : 0) });
        res.lm = (a.rv == b.lv && a.lm == a.n) ? (a.n + b.lm) : a.lm;
        res.rm = (a.rv == b.lv && b.rm == b.n) ? (b.n + a.rm) : b.rm;
        return res;
    }

    void pushup(int rt) {
        int ls = rt << 1, rs = ls | 1;
        f[rt] = merge(f[ls], f[rs]);
    }

    void pushdown(int rt, int l, int r) {
        if (tag[rt]) {
            int v = tag[rt], mi = (l + r) >> 1, ls = rt << 1, rs = ls | 1;
            int llen = mi - l + 1, rlen = r - mi;
            f[ls] = { llen, v, v, llen, llen, llen };
            f[rs] = { rlen, v, v, rlen, rlen, rlen };
            tag[ls] = tag[rs] = v;
            tag[rt] = 0;
        }
    }

    void build(int rt, int l, int r) {
        if (l == r) {
            f[rt] = { 1, a[l], a[l], 1, 1, 1 };
            return;
        }
        int mi = (l + r) >> 1, ls = rt << 1, rs = ls | 1;
        build(ls, l, mi);
        build(rs, mi + 1, r);
        pushup(rt);
    }

    void upd(int rt, int l, int r, int x, int y, int z) {
        if (l == x && r == y) {
            int len = r - l + 1;
            f[rt] = { len, z, z, len, len, len };
            tag[rt] = z;
            return;
        }
        int mi = (l + r) >> 1, ls = rt << 1, rs = ls | 1;
        pushdown(rt, l, r);
        if (y <= mi) {
            upd(ls, l, mi, x, y, z);
        } else if (x > mi) {
            upd(rs, mi + 1, r, x, y, z);
        } else {
            upd(ls, l, mi, x, mi, z);
            upd(rs, mi + 1, r, mi + 1, y, z);
        }
        pushup(rt);
    }

    node qry(int rt, int l, int r, int x, int y) {
        if (l == x && r == y) {
            return f[rt];
        }
        int mi = (l + r) >> 1, ls = rt << 1, rs = ls | 1;
        pushdown(rt, l, r);
        if (y <= mi) {
            return qry(ls, l, mi, x, y);
        } else if (x > mi) {
            return qry(rs, mi + 1, r, x, y);
        } else {
            return merge(qry(ls, l, mi, x, mi), qry(rs, mi + 1, r, mi + 1, y));
        }
    }

} seg;

void main() {
    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }
    seg.build(1, 1, n);
    while (m--) {
        char op;
        int x, y, k;
        std::cin >> op >> x >> y >> k;
        if (op == 'R') {
            seg.upd(1, 1, n, x, y, k);
        } else {
            auto res = seg.qry(1, 1, n, x, y);
            int ans = std::max(res.m, (k && res.lv == res.rv) ? std::min(res.n, res.lm + res.rm) : 0); // 如果前缀和后缀颜色相同(lv == rv)就把前缀颜色相同的长度和后缀颜色相同长度之和(std::min(n, lm + rm)) 和 m 取个 max
            std::cout << ans << '\n';
        }
    }
}
}  // namespace Qwarth

int main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int _T = 1;
    // std::cin >> _T;
    while (_T--) {
        Qwarth::main();
    }
    return 0;
}

::::

最后感谢洛谷管理员的耐心审核，也祝各位读者能够在 OI 赛事上获得理想的成绩。