题解：P12636 [UOI 2020] Array Reduction

· · 题解

显然可以对 a 从大到小排个序，那么 c_i\ge c_{i+1}。

下文的 k 实际上是题面里的 k+t。

有一个结论是，如果恰有 n 个 i 满足 c_i>0，且 k>nt，那么对于每个固定的 0\le x<n，则模 n 余 x 的不合法的答案一定是一段前缀，证明就是如果 x-n 合法，那么把每个数都操作一遍一定更优。

然后就可以二分了，假设我们现在要操作 x 次，那么 c_i\ge \lceil\dfrac{a_i+xt}{k}\rceil，那么总的操作次数就是 \sum \lceil\dfrac{a_i}{k}\rceil+n\lceil\dfrac{xt}{k}\rceil+f(xt\bmod k)。其中 f 是一个容易 O(\log n) 计算的东西，大概就是要查询 a_i\bmod k\in[l,r] 的 i 有几个，可以用树状数组维护。于是我们可以 O(\log n) 判定。

那么我们枚举操作的是哪一段前缀，再二分判断，就可以做到 O(n^2\log n(\log n+\log V))。可以只判断操作的是否是这一段前缀，这样就是 O(n^2\log n+n\log n(\log n+\log V)) 的。

这个做法好像不太好优化，考虑另外的做法。假设我们现在知道 ans\ge x，那么我们可以算得一个目前的最少需要的操作次数然后可以用它去更新 x，直到算得的数和 x 相等为止。

把这两个做法拼起来，当 (n+1)t<k 时不断更新，否则此时 n 将不再增加，我们只需要二分一次即可。后一半的复杂度是 O(n\log n(\log n+\log V))，经过检查，对于 1\le i <n，在 i 处的更新次数不超过 \dfrac{n}{n-i}，所以这个东西可能是 O(n\log^2 n) 的，那么总的时间复杂度就是 O(n\log n(\log n+\log V))，可以通过。

code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const __int128 bas=1;
int n,cnt,tr[1000005],C[1000005];
ll k,t,x,b[1000005],c[1000005],p[1000005];
pair<ll,int> a[1000005];
void Add(int x){
    for(;x<=cnt;x+=x&-x)
        tr[x]++;
}
int query(int x){
    int res=0;
    for(;x;x&=x-1)
        res+=tr[x];
    return res;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>k>>t,k+=t;
    for(int i=1;i<=n;i++) cin>>a[i].first,a[i].second=i;
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);
    if(k==t){
        if(a[1].first>0) return cout<<"-1\n",0;
        cout<<"0\n";
        for(int i=1;i<=n;i++) cout<<"0 ";
        cout<<'\n';
        return 0; 
    }
    for(int i=1;i<=n;i++) p[i]=b[i]=(k+a[i].first%k)%k;
    sort(p+1,p+n+1);
    cnt=unique(p+1,p+n+1)-p-1;
    for(int i=1;i<=n;i++) b[i]=lower_bound(p+1,p+cnt+1,b[i])-p;
    __int128 ns=0,ns2=0;
    for(int pos=0,nw=0;;){
        while(pos<n&&a[pos+1].first+x*t>0) pos++,Add(b[pos]),ns+=(a[pos].first-p[b[pos]])/k,nw=0;
        if(pos<n&&(pos+1)*t<k){
            ns2=bas*t*x/k*pos+pos-query(upper_bound(p+1,p+cnt+1,k-bas*t*x%k)-p-1)+(bas*t*x%k||p[1]?pos:pos-query(1));
            if(ns+ns2==x){
                cout<<x<<'\n';
                for(int i=1;i<=pos;i++)
                    c[a[i].second]=(a[i].first+t*x-1)/k+1;
                for(int i=1;i<=n;i++) cout<<c[i]<<' ';
                cout<<'\n';
                return 0;
            }
            x=ns+ns2;
        }
        else{
            ll ans=2000000000000000ll;
            for(int i=0;i<pos;i++){
                ll l=0,r=2000000000000000ll/pos+1;
                while(l<r-1){
                    ll mid=l+r>>1,x=mid*pos+i;
                    ns2=bas*t*x/k*pos+pos-query(upper_bound(p+1,p+cnt+1,k-bas*t*x%k)-p-1)+(bas*t*x%k||p[1]?pos:pos-query(1));
                    if(ns+ns2<=x) r=mid;
                    else l=mid; 
                }
                ans=min(ans,r*pos+i);
            }
            if(ans<1500000000000000ll&&(pos==n||a[pos+1].first+t*ans<=0)){
                cout<<ans<<'\n';
                for(int i=1;i<=pos;i++)
                    c[a[i].second]=(a[i].first+t*ans-1)/k+1;
                for(int i=1;i<=n;i++) cout<<c[i]<<' ';
                cout<<'\n';
                return 0; 
            }
            return cout<<"-1\n",0;
        }
    }
    return 0;
}