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

诗乃

2019-08-10 10:29:50

Solution

我们发现,$\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)); } } } ```