自动搬运

查看原文

来自洛谷，原作者为

	诗乃 あなた以上の人なんて、どこにもいないよ♡

搬运于2025-08-24 22:11:24，当前版本为作者最后更新于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即可。

代码（很丑）：

#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));
		}
	}
}