「题解」P5500 真正的OIer从不女装

AtomAlpaca

题意
题解
代码

题意

给定一个长度为 $n$ 的序列 $a$ 。支持以下两种操作：

区间覆盖；
询问区间进行不超过 $k$ 次女装操作后，每个元素都相等的子串长度最大值。

其中一次区间女装操作指在区间 $[l,r]$ 内任选位置 $p$ ，将区间 $[l,p]$ 和 $(p,r]$ 分别翻转。

$1 \le n,m \le 200000$

题解

首先我们考虑每次“女装”操作其实就是把当前区间首尾相接成一个环，然后选一个地方把它断掉再展平成一个序列。因此多次“女装”其实答案不会更优。因此只有女装和不女装的区别。

没有女装操作是简单的，考虑有女装操作怎么做。

我们发现把区间接成一个环之后，只会在原来右侧值和左侧值相等时，多出一个原来的右侧相等连续段和左侧极长相等段拼出来的一个子串，可能比原来的答案更优。因此我们考虑用线段树维护区间左、右侧极长相等段和区间极长相等段即可。

代码

记得注意左、右侧极长相等段可能重合，要和询问区间长度取 $\min$ 。

#include <bits/stdc++.h>

const int MAX = 2e5 + 5;
char op;
int l, r, c, k, n, m, a[MAX];

struct N
{
  int l, r, lv, rv, lm, rm, mx, tg = 0;
  void pu(N l, N r)
  {
    this -> l = l.l; this -> r = r.r; lm = l.lm; rm = r.rm; lv = l.lv; rv = r.rv; mx = std::max(l.mx, r.mx);
    if (l.rv == r.lv)
    { 
      mx = std::max(mx, l.rm + r.lm);
      if (l.lm == l.r - l.l + 1) { lm = std::max(lm, l.lm + r.lm); }
      if (r.rm == r.r - r.l + 1) { rm = std::max(rm, r.rm + l.rm); }
    }
  }

  void mdf(int x) { lm = rm = mx = r - l + 1; lv = rv = tg = x; }
  
  void pd(N & l, N & r)
  {
    l.mdf(tg); r.mdf(tg);
    tg = 0;
  }
} st[MAX << 2];

void build(int l, int r, int x)
{
  st[x].l = l; st[x].r = r;
  if (l == r) { st[x].lv = st[x].rv = a[l]; st[x].lm = st[x].rm = st[x].mx = 1; return ; }
  int k = l + ((r - l) >> 1);
  build(l, k, x << 1); build(k + 1, r, x << 1 | 1);
  st[x].pu(st[x << 1], st[x << 1 | 1]);
}

void mdf(int l, int r, int s, int t, int c, int x)
{
  if (l >= s and r <= t) { st[x].mdf(c); return ; }
  if (st[x].tg) { st[x].pd(st[x << 1], st[x << 1 | 1]); };
  int k = l + ((r - l) >> 1);
  if (s <= k) { mdf(l, k, s, t, c, x << 1); }
  if (t >  k) { mdf(k + 1, r, s, t, c, x << 1 | 1); }
  st[x].pu(st[x << 1], st[x << 1 | 1]);
}

N qry(int l, int r, int s, int t, int x)
{
  if (l >= s and r <= t) { return st[x]; }
  if (st[x].tg) { st[x].pd(st[x << 1], st[x << 1 | 1]); };
  N res; int k = l + ((r - l) >> 1);
  if (s <= k and t > k) { res.pu(qry(l, k, s, t, x << 1), qry(k + 1, r, s, t, x << 1 | 1)); return res; }
  if (s <= k) { return qry(l, k, s, t, x << 1); }
  if (t >  k) { return qry(k + 1, r, s, t, x << 1 | 1); }
}

int main()
{
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); }
  build(1, n, 1);
  for (int i = 1; i <= m; ++i)
  {
    scanf("\n%c", &op);
    if (op == 'Q')
    {
      scanf("%d%d%d", &l, &r, &k);
      N res = qry(1, n, l, r, 1);
      if (k and res.lv == res.rv) { printf("%d\n", std::max(res.mx, std::min(res.lm + res.rm, r - l + 1))); }
      else { printf("%d\n", res.mx); }
    }
    else { scanf("%d%d%d", &l, &r, &c); mdf(1, n, l, r, c, 1); }
  }
}

Table of contents

题意

题解

代码