2

极寒神冰 · 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;
}