自动搬运

查看原文

来自洛谷，原作者为

	极寒神冰 **

搬运于2025-08-24 22:25:49，当前版本为作者最后更新于2022-01-01 22:50:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考虑每次直接判断每个 $j$ 是否可行。

已经有 $b_j=l_1$，剩下的 $p-1$ 个人进行操作，可以假设这 $p-1$ 个人联合对抗你，然后就有一个显然的策略：

不管 $l_i$ 是否等于 $h_1$，总是会优先选择一个等于 $h_1$ 的数将其覆盖，然后尽量让某个 $\neq h_1$ 的数出现尽可能多。

因此需要考虑 $h_1$ 至少有几个：

设原先有 $x$ 个 $h_1$，$l_i,i\in [2,p]$ 中有 $y$ 个不等于 $h_1$ 的数，则一个显然的下界是 $\max(x-y,0)$。

特别的，当 $l_p=h_1$ 时需要对 $1$ 取 $\max$。记 $h_1$ 至少有 $N=\max(x-y,[l_p=h_1])$。

然后要考虑其他数最多能出现多少次：

对于每个数 $a\ne h_1$，统计出 $a$ 在 $b$ 中的出现次数 $p_a$，以及在 $l_i,i\in [2,p]$ 中的出现次数 $q_a$。显然 $a$ 最后最多出现 $M=\max\limits_{a\ne h_1}(p_a+q_a)$。

显然如果 $N>M$，则你是必胜的。但如果 $N\le M$，是否有可能必胜呢？

事实上，当且仅当 $n=1,l_p=h_1$ 此时有 $N=M=1$ 你才是必胜的，否则只要其他人联合起来就一定可以让 $h_1$ 出现 $N$ 次，$a$ 出现 $M$ 次。

这样直接做的时间复杂度是 $\mathcal O(n^2)$。

考虑优化，发现对于不同的 $j$，大部分的量都是相同，除了两部分：

1. 首先就是 $x$ 会发生 $\pm 1$ 的变化，而 $y$ 不变，$N$ 仍然可以快速得到。

2. 原先 $b_j$ 出现次数会 $-1$，$l_1$ 的出现次数会 $+1$。

若 $l_1\ne h_1$，则 $p_{l_1}+q_{l_1}$ 会比原先 $+1$，需要单独判断。

对于 $b_j$ 出现次数 $-1$，可以预处理出是否有其他的 $a$ 与 $b_j$ 有相同或更大的值。

同样也可以快速得到。

时间复杂度 $\mathcal O(n+c)$。

#include<bits/stdc++.h>
#define R(i,a,b) for(int i=(a),i##E=(b);i<=i##E;i++)
#define L(i,a,b) for(int i=(b),i##E=(a);i>=i##E;i--)
using namespace std;
int n,p,c,h;
int b[1111111],cnt[1111111];
int l[1111111];
vector<int>ans;
int mx,mmx,cy;
inline int check(int x)
{	
	if(n==1&&l[p]==h) return 1;
	--cnt[b[x]];
	++cnt[l[1]];
	int del=cnt[h]-cy;
	bool ok=1;
	if(del<=0) ok=0;
	if(cnt[mx]>=del) ok=0;
	if(cnt[mmx]>=del) ok=0;
	if(l[1]!=h&&cnt[l[1]]>=del) ok=0;
	++cnt[b[x]];
	--cnt[l[1]];
	return ok;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>p>>c>>h;
	R(i,1,n) cin>>b[i],++cnt[b[i]];
	R(i,1,p) cin>>l[i];
	R(i,2,p) if(l[i]!=h) ++cy,++cnt[l[i]];
	//cout<<cy<<endl;
	R(i,1,c) if(i!=h) 
	{
		if(cnt[i]>cnt[mx]) mmx=mx,mx=i;
		else if(cnt[i]>cnt[mmx]) mmx=i;
	}  
	R(i,1,n) if(check(i)) ans.emplace_back(i);
	cout<<ans.size()<<endl;
	for(int x:ans) cout<<x<<' ';
	cout<<endl;
}