「ROI 2026 Day1」体育训练

admin LV 10 SU @ 2026-8-5 1:08:36

本质是一般题，但代码有些恶臭，画点图造福后人。

先考虑排列固定的情况：

题目中说找左边和右边比它小的最远的点，显然只会出现在前缀最小值和后缀最小值之中。

把点分为四类： $L$ 表示它是前缀最小值， $R$ 表示它是后缀最小值， $mn$ 为全局最小值（ $L$ 和 $R$ 不包含它）， $M$ 表示其他点。

对于 $L$ 和 $R$ ，它只在另一侧有后继，对于 $M$ 则在两侧分别有后继。对应的后继就是某一侧小于它的最大值。

考虑把每个 $M$ 挂在它两个后继较大的那个上，因为显然小的是大的的后继。

按值域从小到大把不是 $M$ 的点排成一列，如上图是： $mn,L,L,R,R,L,L$ 。

对于第一问，只能从上往下走，令 $C$ 为排成一列后颜色段的个数，那么不难观察到答案是 $C-1$ 或 $C$ ，减一取决于最后一段有没有挂 $M$ 。

考虑第二问，注意到无向图的路径大致也是从上往下走，但在每一段内部会有一些起伏。将每一个颜色连续段单独考虑，假设颜色是 $L$ ：

不妨考虑最大子段和的维护方式，每一段维护 $[sum,pre,suf,ans]$ ，分别表示：从 $L_1$ 走到 $R$ 的最长路径、从 $L_1$ 走到内部某个点结束的最长路径、从某个点开始走到 $R$ 的最长路径，在内部走的最长路径。那么合并是容易的，只需要求出每一段内的信息即可。

令 $M_x$ 表示 $L_x$ 上挂的某个 $x$ ， $M'_x$ 表示挂的另一个（如果存在的话）， $M''_x$ 同理。进行分讨，括号表示可以不存在：

$sum:L_1(\to M_1)\to R$ ；
$pre:L_1(\to M_1)\to R(\to M_x)\to L_x(\to M'_x)$ ；
$pre:L_1(\to M_1)\to R(\to M'_1)$ ；
$suf:(M_x\to)L_x(\to M'_x)\to R$ ；
$ans:(M_x\to)L_x(\to M'_x)\to R((\to M_y)\to L_y(\to M'_y))$；
$ans:(M_x\to)L_x(\to M'_x)\to R(\to M''_x)$ 。

令 $cnt_x$ 表示 $x$ 上挂的 $M$ 的个数，显然上述信息只跟每一段最大的、次大的 $cnt$ 以及第一个 $cnt$ 有关，维护一下就行。

然后考虑动态插入，不妨假设是把 $p$ 插在左边。类似于单调栈，每次相当于 pop 掉一个前缀的 $L$ 。

显然颜色段是均摊 $O(1)$ 变化的。现在需要支持的是：

动态维护颜色连续段。由于是后缀 pop 也许可以用 vector 存，为了好写也可以用 set。
动态维护 $cnt$ 并区间查最大次大。用线段树即可。每次 pop 掉的点的 $cnt$ 会转移到它的后继上，需要注意新插进去的 $cnt_p$ 可能会分走原来的一些，需要特判（代码里写了个树状数组）。
动态维护最大子段和，也用线段树即可，在连续段或者 $cnt$ 变化的时候进行修改。
注意有可能出现 $p$ 变成 $mn$ 的情况，此时原来的 $mn$ 会作为 $R$ 插在右侧的开头（而不是结尾）。

然后写写写就行了。复杂度是 $O(n\log n)$ 的。

:::info[屎山]

#define N 300010
int OP;
int n, m, a[N];
char str[333];
int opt[N], x_[N];
int mn, cnt[N], tag[N];
struct node
{
	int l, r, op;
	bool operator < (const node &B) const { return l < B.l; }
};
std::set <int> now;
std::set <node> s;
std::deque <int> vec[2];
#define root 1, 1, n + m
#define lson k << 1
#define rson k << 1 | 1
#define ls lson, l, mid 
#define rs rson, mid + 1, r
namespace SGT1
{
struct mxnode
{
	int mx0, mx1, R;
	mxnode operator + (mxnode B)
	{
		if(!~B.R) return *this;
		if(!~R) return B;
		mxnode res = *this;
		res.R = B.R;
		if(B.mx0 > res.mx0) res.mx1 = res.mx0, res.mx0 = B.mx0;
		else ckmax(res.mx1, B.mx0);
		ckmax(res.mx1, B.mx1);
		return res;
	}
}tr[N << 2];
void build(int k, int l, int r)
{
	tr[k] = (mxnode){-1, -1, -1};
	if(l == r) return;
	int mid = (l + r) >> 1; build(ls); build(rs); tr[k] = tr[lson] + tr[rson];
}
void update(int k, int l, int r, int q, int z)
{
	// if(k == 1) debug("update %d %d\n", q, z);
	if(l == r) { tr[k].mx0 = tr[k].R = z; tr[k].mx1 = -1; return; }
	int mid = (l + r) >> 1; q <= mid ? update(ls, q, z) : update(rs, q, z); tr[k] = tr[lson] + tr[rson];
}
mxnode query(int k, int l, int r, int ql, int qr)
{
	if(ql > qr) return (mxnode){-1, -1, -1};
	if(ql <= l && r <= qr) return tr[k];
	int mid = (l + r) >> 1;
	if(qr <= mid) return query(ls, ql, qr);
	if(mid < ql)  return query(rs, ql, qr);
	return query(ls, ql, qr) + query(rs, ql, qr);
}
} // namespace SGT1

struct node2
{
	int sum, pre, suf, ans;
	node2 operator + (node2 B)
	{
		node2 res;
		res.sum = sum + B.sum;
		res.pre = std::max(pre, sum + B.pre);
		res.suf = std::max(suf + B.sum, B.suf);
		res.ans = std::max({ans, B.ans, suf + B.pre});
		return res;
	}
}empty;
node2 makenode(int l, int r)
{
	if(l > r) return empty;
	auto t = SGT1::query(root, l, r);
	if(!~t.R) return empty;
	node2 res;
	res.sum = 1 + (t.R > 0);
	if(t.mx0 != t.R) res.pre = 1 + (t.R > 0) + 1 + (t.mx0 > 0) + (t.mx0 > 1);
	else res.pre = 1 + (t.R > 0) + (t.mx1 > -1) + (t.mx1 > 0) + (t.mx1 > 1);
	ckmax(res.pre, 1 + (t.R > 0) + (t.R > 1));
	res.suf = 1 + (t.mx0 > 0) + (t.mx0 > 1);
	res.ans = 1 + (t.mx0 > 0) + (t.mx0 > 1) + (t.mx1 > -1) + (t.mx1 > 0) + (t.mx1 > 1);
	ckmax(res.ans, 1 + (t.mx0 > 0) + (t.mx0 > 1) + (t.mx0 > 2));
	return res;
}
namespace SGT2
{
node2 tr[N << 2];
void build(int k, int l, int r)
{
	tr[k] = empty; if(l == r) return;
	int mid = (l + r) >> 1; build(ls); build(rs);
}
void update(int k, int l, int r, int q, node2 z)
{
	if(l == r) { tr[k] = z; return; }
	int mid = (l + r) >> 1; q <= mid ? update(ls, q, z) : update(rs, q, z);
	tr[k] = tr[rson] + tr[lson];
}
} // namespace SGT2

std::set<node>::iterator split(int x)
{
	if(s.empty() || x > s.rbegin()->r) return s.end();
	auto it = s.lower_bound((node){x});
	if(it == s.begin() || prev(it)->r < x) return it;
	--it;
	int l = it->l, r = it->r, op = it->op;
	SGT2::update(root, l, empty);
	s.erase(it);
	if(l <= x - 1) 
	{
		int t = *prev(now.lower_bound(x));
		SGT2::update(root, l, makenode(l, t));
		s.insert((node){l, t, op});
	}
	int t = *now.upper_bound(x);
	SGT2::update(root, t, makenode(t, r));
	return s.insert((node){t, r, op}).fi;
}

void insx(int x, int o)
{
	now.insert(x);
	auto it = split(x);
	int l = x, r = x;
	if(it != s.begin() && prev(it)->op == o)
	{
		SGT2::update(root, prev(it)->l, empty);
		l = prev(it)->l; s.erase(prev(it));
	}
	if(it != s.end() && it->op == o)
	{
		SGT2::update(root, it->l, empty);
		r = it->r; s.erase(it);
	}
	SGT2::update(root, l, makenode(l, r));
	s.insert((node){l, r, o});
}

namespace BIT
{
int tr[N];
void ins(int x, int z) { for(x = n + m - x + 1; x <= n + m; x += x & (-x)) tr[x] += z; }
int query(int x) { int res = 0; for(x = n + m - x + 1; x; x -= x & (-x)) res += tr[x]; return res; }
}

void ins(int x, int o)
{
	std::vector <int> delvec;
	while(!vec[o].empty() && vec[o].back() > x)
	{
		int p = vec[o].back(); vec[o].pop_back();
		delvec.push_back(p);
		now.erase(p);
	}
	std::vector <node> tmp;
	while(!s.empty() && s.rbegin()->r > x)
	{
		node t = *s.rbegin(); s.erase(--s.end());
		if(t.op == o)
		{
			int l = t.l, r = t.r;
			SGT2::update(root, l, empty);
			if(l > x) continue;
			r = *prev(now.lower_bound(x));
			s.insert((node){l, r, o}), SGT2::update(root, l, makenode(l, r));
			break;
		}
		else tmp.push_back(t);
	}
	if(!tmp.empty())
	{
		if(!s.empty() && s.rbegin()->op == tmp.back().op)
		{
			tmp.push_back(*s.rbegin());
			s.erase(--s.end());
		}
		int l = tmp.back().l, r = tmp.back().r, op = tmp.back().op;
		for(node t : tmp) SGT2::update(root, t.l, empty), ckmin(l, t.l), ckmax(r, t.r);
		s.insert((node){l, r, op});
		SGT2::update(root, l, makenode(l, r));
	}
	int y;
	if(x < mn)
	{
		vec[o ^ 1].push_front(mn);
		insx(y = mn, o ^ 1);
		mn = x; 
	}
	else 
	{
		vec[o].push_back(x);
		insx(y = x, o);
	}
	for(int x : delvec)
	{
		BIT::ins(x, 1);
		SGT1::update(root, x, -1);
		auto it = s.lower_bound((node){x + 1});
		if(it != s.begin() && x <= prev(it)->r)
		{
			--it;
			SGT2::update(root, it->l, makenode(it->l, it->r));
		}
		int p = *(--now.lower_bound(x));
		cnt[p] += cnt[x] + 1;
		it = --s.lower_bound((node){p + 1});
		SGT1::update(root, p, cnt[p]);
		SGT2::update(root, it->l, makenode(it->l, it->r));
	}

	{
		int r = n + m + 1;
		auto itL = now.lower_bound(y);
		if(next(itL) != now.end()) ckmin(r, *next(itL));
		cnt[y] = BIT::query(y) - BIT::query(r);
		SGT1::update(root, y, cnt[y]);
		auto it = --s.lower_bound((node){y + 1});
		SGT2::update(root, it->l, makenode(it->l, it->r));
		int l = 0;
		if(itL != now.begin()) ckmax(l, *prev(itL));
		if(l)
		{
			cnt[l] = BIT::query(l) - BIT::query(y);
			SGT1::update(root, l, cnt[l]);
			it = --s.lower_bound((node){l + 1});
			SGT2::update(root, it->l, makenode(it->l, it->r));
		}
	}

	// gline;
	// debug("mn = %d\n", mn);
	// debug("vec[0] : "); for(int x : vec[0]) debug("%d(%d) ", x, cnt[x]); 
	// debug("\n");
	// debug("vec[1] : "); for(int x : vec[1]) debug("%d(%d) ", x, cnt[x]); 
	// debug("\n");
	// debug("s : \n"); 
	// for(node t : s) 
	// {
	// 	node2 v = makenode(t.l, t.r);
	// 	auto z = SGT1::query(root, t.l, t.r);
	// 	SGT2::update(root, t.l, v);
	// 	debug("[%d %d %d] : [%d %d %d %d] (%d %d %d)\n", t.l, t.r, t.op, v.sum, v.pre, v.suf, v.ans, z.mx0, z.mx1, z.R);
	// }
}

int query()
{
	if(now.empty()) return 0;
	if(OP == 1)
	{
		int res = s.size();
		node t = *s.rbegin();
		auto v = SGT1::query(root, t.l, t.r);
		if(v.mx0 > 0) res++;
		return res;
	}
	return SGT2::tr[1].ans;
}

void solve()
{
	// memset(h, idx = -1, sizeof(h));
	OP = read(), n = read(), m = read();
	for(int i = 1; i <= n; i++) a[i] = read();
	for(int i = 1; i <= m; i++)
	{
		readstr(str, 0);
		opt[i] = (str[0] == 'R');
		x_[i] = read();
	}
	int mnpos = std::min_element(a + 1, a + 1 + n) - a;
	mn = a[mnpos];
	SGT1::build(root); SGT2::build(root);
	for(int i = mnpos - 1; i >= 1; i--) ins(a[i], 0);
	for(int i = mnpos + 1; i <= n; i++) ins(a[i], 1);
	print(query(), '\n');
	for(int i = 1; i <= m; i++)
	{
		if(!opt[i]) ins(x_[i], 0);
		else ins(x_[i], 1);
		print(query(), '\n');
	}
}

:::

ID

12596

时间

2000ms

内存

1100MiB

难度

标签

递交数

已通过

上传者

huangzheng

1 条题解

信息

状态

开发

支持

关于

1 条题解

「ROI 2026 Day1」体育训练

信息

状态

开发

支持

关于

还没有账户？

登录