Red-Blue Operations (Hard Version)
spider_oyster
·
·
题解
ch-translater 来了。
先相信，再相信。
### 先说性质。
>- 每个数在【最终加】（最后一次加）之前，一定比原数小。于是我们要让【最终加】最大。
>- 【最终加】的条件是当前数之前被操作偶数次。
>- 【操作】（对同一个数连续进行两次操作）会令一个数变化 $1$。由上述性质，只会有 $-1$ 【操作】。
### 考虑将操作反过来。
先对数组里每个数进行【最终加】。
于是将 $a_i$ 从小到大排序，则前 $n$ 次操作最优是让 $a_i+k-i+1$。发现 $k$ 是常量，可以提出来，让最后输出答案时再加 $k$，以降低耦合度。
于是构造数组 $b_i=a_i-i+1$，并记 $b$ 的前缀最小值数组 $p$，再记 $b$ 数组和为 $s$。
这时还剩余 $k-n$ 个操作。
#### 若 $k \bmod 2=n \bmod 2$：
剩下偶数次操作。根据性质，这时会对执行 $(k-n)/2$ 次 【操作】。
前 $n$ 次操作后当前最小值为 $mi=p_n$。
注意这时对非最小值操作不会影响答案。于是可以【操作】 $s-mi\times n$ 次。
【操作】完后，会发现所有数相同了，这时再对 $n$ 个数整体进行【操作】。
答案：$k+mi-\lceil \frac{(k-n)/2-(s-mi\times n)}{n} \rceil$。
#### 若 $k \bmod 2\ne n\bmod 2$：
会多出一次操作。这东西很恶心，会令【最终加】少一次。考虑舍弃 $a_n$ 的【最终加】。
此时最小值为 $mi=\min(p_{n-1}+k,a_n)$。
同时注意 $s$ 的变化。
剩下的计算与 $k \bmod 2=n\bmod 2$ 相同。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int n,q;cin>>n>>q;
vector<int> a(n+1),p(n+1,2e9);
for(int i=1;i<=n;i++) cin>>a[i];
sort(a.begin()+1,a.end());
p[1]=a[1];
for(int i=2;i<=n;i++) p[i]=min(p[i-1],a[i]-i+1);
int s=0;
for(int i=1;i<=n;i++) s+=a[i]-i+1;
for(int i=1;i<=q;i++)
{
int k;cin>>k;
if(k<n) cout<<min(p[k]+k,a[k+1])<<' ';//只对前 k 个数进行【最终加】
else if(k%2==n%2) cout<<p[n]+k-(int)ceil(max(0ll,(k-n)/2-(s-p[n]*n))*1.0/n)<<' ';
else
{
int mi=min(p[n-1],a[n]-k);//由于最终答案+k,所以把 min(p[n-1]+k,a[n]) 变一下
int _s=s+n-1-k-mi*n;//注意 a[n]-n+1 变为 a[n]-k
cout<<mi+k-(int)ceil(max(0ll,(k-n+1)/2-_s)*1.0/n)<<' ';
}
}
}
```