专栏文章

题解：CF2126G2 Big Wins! (hard version)

zzxh923
CF2126G2题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miotmpgz
此快照首次捕获于
2025/12/03 00:57
3 个月前
此快照最后确认于
2025/12/03 00:57
3 个月前
查看原文

思路

倒开了一手，写了 9090 分钟切了。
首先发现有中位数，我们套路的扫描线扫值域。
把 ≥x\ge x 的数看成 11，剩下的数看成 −1-1。然后一个区间 [l,r][l,r] 的中位数 ≥x\ge x 当且仅当这个区间的和是 00 或者 11。
我们先假设我们有办法能求出所有这样区间的最小值，然后这里要说明一下，为什么中位数不是 xx 但是没有影响。
因为这里的贡献式子是中位数减去最小值，最小值不变，中位数我们当成 xx 来算，但是实际上 ≥x\ge x，所以答案不会算大。
然后我们考虑怎么求这个最小值。
我们设 sis_i 为这个只有 −1,1-1,1 的序列的前缀和数组。然后一个位置 ii 的数可能是最小值当且仅当 max⁡j=in(sj)≥min⁡k=0i−1(sk)\displaystyle\max_{j=i}^{n}(s_j)\ge\min_{k=0}^{i-1}(s_k)。
首先我们让一个更大的数成为最小值，一定不会使答案更优，所以没有必要检验这个数到底是不是区间内最小值。然后如果上面的式子被满足了，一定能够选到两个位置，使得这两个位置的差要么是 00，要么是 11。
下面我们说明一下这个东西的正确性：
假设 si−1+1=sis_{i-1}+1=s_i，那么直接合法了。所以我们只需要讨论其他情况。显然因为这个不等式关系，一定能选到两个数相差 00，然后就对了（上面的差指的是 sj−sks_j-s_k)。
所以对于一个位置，我们现在能快速判断他能不能成为最小值了。这里我猜想一个最小值如果某一时刻不再能作为最小值了，那么以后也不能。
下面是证明。假设我们之前对这个最小值选出两个位置 k,jk,j 使得满足上述不等式关系。我们考虑一次会把一些位置从 11 变为 −1-1，观察这个东西，发现只有这个位置在 k,jk,j 之间才有影响。
那么此时最小值不会变，最大值会变小，所以显然这个过程是不可逆的，于是结论就对了。
最后拿一个 vector 维护当前的最小值与其位置，用线段树维护 ss，这样应该能做到 O(nlog⁡n)O(n\log n)。虽然我场上写的 set，但是区别不大。

代码

把场上的 set 换成 vector 了。
CPP
#include<bits/stdc++.h>
#define int long long
#define N 200005
#define K 20
#define mod 998244353
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
int T=1,n,a[N],inf=2e9,s[N];
vector<int>e[N];
struct sgt{
	struct node{
		int mx,mn,tag;
	}tr[N<<2];
	void pushup(int u){
		tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
		tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
	}
	void build(int u,int l,int r){
		tr[u].tag=0;
		if(l==r){
			tr[u].mx=tr[u].mn=s[l];
			return;
		}
		int mid=l+r>>1;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u);
	}
	void maketag(int u,int v){
		tr[u].mx+=v;
		tr[u].mn+=v;
		tr[u].tag+=v;
	}
	void pushdown(int u){
		maketag(u<<1,tr[u].tag);
		maketag(u<<1|1,tr[u].tag);
		tr[u].tag=0;
	}
	void modify(int u,int l,int r,int L,int R,int v){
		if(l>=L&&r<=R){
			maketag(u,v);
			return;
		}
		int mid=l+r>>1;
		pushdown(u);
		if(L<=mid)modify(u<<1,l,mid,L,R,v);
		if(R>mid)modify(u<<1|1,mid+1,r,L,R,v);
		pushup(u);
	}
	int qry_min(int u,int l,int r,int L,int R){
		if(L>R)return inf;
		if(l>=L&&r<=R)return tr[u].mn;
		int mid=l+r>>1;
		int res=inf;
		pushdown(u);
		if(L<=mid)res=min(res,qry_min(u<<1,l,mid,L,R));
		if(R>mid)res=min(res,qry_min(u<<1|1,mid+1,r,L,R));
		return res;
	}
	int qry_max(int u,int l,int r,int L,int R){
		if(L>R)return -inf;
		if(l>=L&&r<=R)return tr[u].mx;
		int mid=l+r>>1;
		int res=-inf;
		pushdown(u);
		if(L<=mid)res=max(res,qry_max(u<<1,l,mid,L,R));
		if(R>mid)res=max(res,qry_max(u<<1|1,mid+1,r,L,R));
		return res;
	}
}sgt;
void solve(int cs){
    if(!cs)return;
	cin>>n;
	for(int i=1;i<=n;i++){
		e[i].clear();
	}
	vector<pii>t;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		t.push_back({a[i],i});
		e[a[i]].push_back(i);
		s[i]=s[i-1]+1;
	}
	sort(t.begin(),t.end());
	sgt.build(1,1,n);
	int res=0;
	int cur=0;
	for(int i=1;i<=n;i++){
		for(auto p:e[i-1]){
			sgt.modify(1,1,n,p,n,-2);
		}
		while(cur<t.size()){
			auto it=t[cur];
			if(sgt.qry_max(1,1,n,it.y,n)<min(0ll,sgt.qry_min(1,1,n,1,it.y-1))){
				cur++;
			}
			else break;
		}
		if(cur==t.size())continue;
		res=max(res,i-t[cur].x);
	}
	cout<<res<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	for(int cs=1;cs<=T;cs++){
		solve(cs);
	}
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...