题解 P5500 【[LnOI2019]真正的OIer从不女装】
诗乃
2019-08-10 10:29:50
我们发现,$\forall k>0, Ans_{k} = Ans_{1}$,其中 $Ans_{j}$表示正好反转$j$次的最大答案。所以对于本题,$k=0$和$k\neq 0$分开讨论即可。
为什么$\forall k>0, Ans_{k} = Ans_{1}$呢?
假设序列为 $\underrightarrow{1}\underrightarrow{2}\underrightarrow{3}$;
从某个位置翻转后变成: $\underleftarrow{2}\underleftarrow{1}\underleftarrow{3}$;
将序列整个翻转对答案没有影响,即: $\underrightarrow{3}\underrightarrow{1}\underrightarrow{2}$;
即一次翻转与把序列开头的某一段接到序列后面等效。因此, $\forall k>0, Ans_{k} = Ans_{1}$
我们发现翻转两次等于翻转一次,那么这样推出翻转多次等于翻转一次。
使用线段树来维护区间最长颜色段。对于所有$k \neq 0$且询问区间左右端点颜色相同的询问,将区间最长颜色段与询问区间左右最长颜色段长度的和取max即可。
代码(很丑):
```cpp
#include <bits/stdc++.h>
#define L(u) (u<<1)
#define R(u) (u<<1|1)
using namespace std;
const int MAXN = 200050;
void read(int &x) {
char ch; while(ch = getchar(), ch < '!'); x = ch - 48;
while(ch = getchar(), ch > '!') x = (x << 3) + (x << 1) + ch - 48;
}
struct Segment_Tree {
int lcol, rcol, col, lmax, rmax, v;
} t[MAXN << 2];
int n, m, a[MAXN];
void pushup(int u, int l, int r) {
int mid = (l + r) >> 1;
if(t[L(u)].col != t[R(u)].col || t[L(u)].col == -1 || t[R(u)].col == -1) t[u].col = -1;
else t[u].col = t[L(u)].col;
t[u].lcol = t[L(u)].lcol; t[u].rcol = t[R(u)].rcol;
if(t[L(u)].col != -1 && t[L(u)].col == t[R(u)].lcol) t[u].lmax = (mid-l+1)+t[R(u)].lmax;
else t[u].lmax = t[L(u)].lmax;
if(t[R(u)].col != -1 && t[R(u)].col == t[L(u)].rcol) t[u].rmax = (r-mid)+t[L(u)].rmax;
else t[u].rmax = t[R(u)].rmax;
t[u].v = max(t[L(u)].v, t[R(u)].v);
if(t[L(u)].rcol == t[R(u)].lcol) t[u].v = max(t[u].v, t[L(u)].rmax + t[R(u)].lmax);
}
void cover(int u, int l, int r, int c) {
//cout << l << " " << r << " " << c << endl;
t[u].col = t[u].lcol = t[u].rcol = c;
t[u].v = t[u].lmax = t[u].rmax = r-l+1;
}
void pushdown(int u, int l, int r) {
if(t[u].col != -1) {
int mid = (l + r) >> 1;
cover(L(u), l, mid, t[u].col);
cover(R(u), mid+1, r, t[u].col);
}
}
void build(int u, int l, int r) {
if(l == r) {
t[u].lcol = t[u].rcol = t[u].col = a[l];
t[u].lmax = t[u].rmax = 1; t[u].v = 1;
//cout << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << endl;
return;
}
int mid = (l + r) >> 1;
build(L(u), l, mid); build(R(u), mid+1, r);
pushup(u, l, r);
//cout << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << endl;
}
void print(int u, int l, int r) {
if(l == r) {
cout << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << endl;
return;
}
int mid = (l + r) >> 1;
print(L(u), l, mid); print(R(u), mid+1, r);
cout << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << endl;
}
void update(int u, int l, int r, int tl, int tr, int c) {
if(tr < l || tl > r) return;
if(tl <= l && r <= tr) {
cover(u, l, r, c);
return;
}
pushdown(u, l, r);
int mid = (l + r) >> 1;
update(L(u), l, mid, tl, tr, c); update(R(u), mid+1, r, tl, tr, c);
pushup(u, l, r);
}
int query(int u, int l, int r, int tl, int tr) {
if(tl <= l && r <= tr) return t[u].v;
pushdown(u, l, r);
int mid = (l + r) >> 1;
if(tr <= mid) return query(L(u), l, mid, tl, tr);
else if(tl > mid) return query(R(u), mid+1, r, tl, tr);
else {
int res = max(query(L(u), l, mid, tl, tr), query(R(u), mid+1, r, tl, tr));
if(t[L(u)].rcol == t[R(u)].lcol) {
int rm = min(mid-tl+1, t[L(u)].rmax), lm = min(tr-mid, t[R(u)].lmax);
res = max(res, rm + lm);
}
return res;
}
}
int Qcol(int u, int l, int r, int x) {
if(l == r) return t[u].col;
if(l <= x && x <= r && t[u].col != -1) return t[u].col;
pushdown(u, l, r);
int mid = (l + r) >> 1;
if(x <= mid) return Qcol(L(u), l, mid, x);
else return Qcol(R(u), mid+1, r, x);
}
int Qlmax(int u, int l, int r, int tl, int tr) {
//cout << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << endl;
if(l <= tl && tr <= r && l + t[u].lmax - 1 >= tl) return l+t[u].lmax-tl;
pushdown(u, l, r);
int mid = (l + r) >> 1;
if(tl > mid) return Qlmax(R(u), mid+1, r, tl, tr);
else if(tr <= mid) return Qlmax(L(u), l, mid, tl, tr);
else if(t[L(u)].rcol == t[R(u)].lcol && mid-t[L(u)].rmax+1 <= tl) return Qlmax(L(u), l, mid, tl, mid) + Qlmax(R(u), mid+1, r, mid+1, tr);
else return Qlmax(L(u), l, mid, tl, mid);
/*{
if(t[L(u)].col != -1) {
if(t[L(u)].col != t[R(u)].lcol) return mid-tl+1;
else return mid-tl+1+Qlmax(R(u), mid+1, r, mid+1, tr);
} else return Qlmax(L(u), l, mid, tl, mid);
}*/
}
int Qrmax(int u, int l, int r, int tl, int tr) {
//cout << u << " " << l << " " << r << " " << t[u].v << " " << t[u].lcol << " " << t[u].rcol << " " << t[u].lmax << " " << t[u].rmax << " " << t[u].col << endl;
if(l <= tl && tr <= r && r - t[u].rmax + 1 <= tr) return tr - r + t[u].rmax;
pushdown(u, l, r);
int mid = (l + r) >> 1;
//cout << R(u) << " " << L(u) << " " << t[R(u)].col << " " << t[L(u)].rcol << endl;
if(tl > mid) return Qrmax(R(u), mid+1, r, tl, tr);
else if(tr <= mid) return Qrmax(L(u), l, mid, tl, tr);
else if(t[R(u)].lcol == t[L(u)].rcol && mid+1+t[R(u)].lmax-1 >= tr) return Qrmax(L(u), l, mid, tl, mid) + Qrmax(R(u), mid+1, r, mid+1, tr);
else return Qrmax(R(u), mid+1, r, mid+1, tr);
/*{
if(t[R(u)].col != -1) {
if(t[R(u)].col != t[L(u)].rcol) return tr-mid;
else return tr-mid+Qrmax(L(u), l, mid+1, tl, mid);
} else return Qrmax(R(u), mid+1, r, mid+1, tr);
}*/
}
int main() {
read(n); read(m);
for(int i = 1; i <= n; ++i) read(a[i]);
build(1, 1, n);
int l, r, x; char opt;
while(m--) {
while(opt = getchar(), opt != 'R' && opt != 'Q');
read(l); read(r); read(x);
if(opt == 'R') update(1, 1, n, l, r, x);
else {
if(x) {
int lc = Qcol(1, 1, n, l), rc = Qcol(1, 1, n, r);
if(lc == rc) {
int lm = Qlmax(1, 1, n, l, r), rm = Qrmax(1, 1, n, l, r);
//cout << lm << " " << rm << endl;
printf("%d\n", max(query(1, 1, n, l, r), min(lm + rm, r-l+1)));
} else printf("%d\n", query(1, 1, n, l, r));
//print(1, 1, n);
} else printf("%d\n", query(1, 1, n, l, r));
}
}
}
```