# 朝田诗乃 的博客

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

posted on 2019-08-10 10:29:50 | under 题解 |

#include <bits/stdc++.h>
#define L(u) (u<<1)
#define R(u) (u<<1|1)
using namespace std;

const int MAXN = 200050;
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() {
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');
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));
}
}
}