Obsessed with Hatsune Miku#11856

Obsessed with Hatsune Miku (Editorial)

Problem Author:	(De3b0o)
Prepared by:	Hasan Saleh (MathModel)
Edited by:	(De3b0o)

Solution

Since $k$ is a factor of $x$ , i.e. $x mod k = 0$ x \bmod k=0 , we can ignore $a_{i} mod k$ a_i \bmod k.

Proof :

let's say we have a number $y < x$ y<x , $y mod k = 0$ y \bmod k = 0 and we need $e$ operations to make it equal to $x$ , Formally

(y + e k = x)

\displaystyle (y + ek = x)

Then for the number $y + z$ y+z where $0 \leq z < k$ 0 \le z<k (this means $(y + z) mod k = z$ (y+z) \bmod k = z), if we apply $e - 1$ e-1 operations the new number is $y + z + (e - 1) \cdot k < y + e \cdot k = x$ y+z+(e-1) \cdot k < y+e \cdot k = x , so we still need one operation to make it at least $x$ , we still use $e$ operations so $a_{i} mod k$ a_i \bmod k is irrelevant.

Now if we update each $a_{i}$ a_i to $a_{i} - a_{i} mod k$ a_i - a_i \bmod k , all elements are going to be multiples of $k$ , so we can just divide everything by $k$ .

We're left with $k = \frac{k}{k} = 1$ k=\frac{k}{k}=1 , $x = \frac{x}{k}$ x=\frac{x}{k} and $a_{i} = \frac{( a _{i} - a _{i} mod k )}{k} = ⌊ \frac{a _{i}}{k} ⌋$ \displaystyle a_i=\frac{(a_i - a_i \bmod k)}{k} = \left \lfloor \frac{a_i}{k} \right \rfloor.

Now $k = 1$ k=1 so it's much easier to find the query's answer.

For a single query:

(we're going to be referring to the maximum number of obsessed fans as $mx$ and the minimum number of operations required as $mn$ , and all values are after the update so $k = 1$ k=1 , $x = \frac{x}{k}$ x=\frac{x}{k} and $⌊ \frac{a _{i}}{k} ⌋$ \displaystyle \left \lfloor \frac{a_i}{k} \right \rfloor.

We can easily see that

mx = min (\frac{\sum ( a )}{x}, n)

\displaystyle \text{mx} = \min(\frac{\sum(a)}{x} , n)

To find $mn$ , we first observe that it's optimal to make the biggest $mx$ fan in the array obsessed (because it takes less operations).

Among the $mx$ biggest elements , if all elements are already bigger than $x$ , then $mn = 0$ \text{mn} = 0.

Otherwise , for every element that's strictly less than $x$ , we have to make it equal to $x$ .

Let's say there's $z$ such elements , $y_{1}, y_{2}, y_{3}, ..., y_{z}$ y_1 , y_2 , y_3 , ... , y_z.

Then

mn = i = 1 \sum z (x - y_{i})

\displaystyle \text{mn} = \sum_{i=1}^z (x-y_i)

If array $a$ is sorted we can easily calculate $mx$ , $mn$ using prefix sums and binary search.

Now we only need a way to maintain the array $a$ and prefix sums for each different $k$ .

For a single $k$ , number of distinct values $⌊ \frac{a _{i}}{k} ⌋$ \displaystyle \left \lfloor \frac{a_i}{k} \right \rfloor. is at most $\frac{m a x ( a )}{k}$ \frac{\max(a)}{k} , so we can compress the array a into $\frac{m a x ( a )}{k}$ \frac{\max(a)}{k} elements and maintain frequencies.

If we do this for every $k$ , complexity is at most $O (\frac{A}{1} + \frac{A}{2} + \frac{A}{3} + .... + \frac{A}{A})$ \mathcal{O}(\frac{A}{1} + \frac{A}{2} + \frac{A}{3} + .... + \frac{A}{A}) which is $O (A lo g (A))$ \mathcal{O}(A \log(A)) , where $A = max (a)$ A = \max(a).

Refer to Harmonic Series , Where :

\int_{1}^{n} \frac{1}{x} d x = lo g_{e} (n)

\displaystyle \int_1^n \frac{1}{x} dx = \log_e(n)

so final complexity is $O (A lo g (A) + q lo g (n))$ \mathcal{O}(A \log(A) + q \log(n)) which is fast enough.

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll,ll>
#define lin cout << "\n";
#define mid ((l+r)/2)
#define lc (2*x)
#define rc (2*x+1)
 
using namespace std;

const ll N = 1e6+9;

ll n , q;
ll a[N];
pll ans[N];
ll frq[N];
pair<pll,ll> qu[N];
ll x , k;
vector<pll> v,p;

int main()
{
    d3
    cin >> n >> q;
    for(int i = 1 ; n>=i ; i++)
        cin >> a[i],frq[a[i]]++;
    for(int i = 1 ; N>i ; i++)
        frq[i]+=frq[i-1];
    for(int i = 0 ; q>i ; i++)
    {
        cin >> x >> k;
        qu[i]={{k,x},i};
    }
    sort(qu,qu+q);
    ll pk = 0;
    ll sum;
    ll sz;
    for(int h = 0 ; q>h ; h++)
    {
        x = qu[h].F.S;
        k = qu[h].F.F;
        ll id = qu[h].S;
        if(k!=pk)
        {
            v.clear();
            p.clear();
            v.pb({-1,0});
            p.pb({0,0});
            sum=0;
            for(ll i = 0 ; N>i ; i+=k)
            {
                ll r = min((i+k),N)-1;
                ll e = frq[r];
                if(i)
                    e-=frq[i-1];
                if(e)
                    v.pb({i/k,e}),p.pb({(i/k)*e,e});
                sum+=(i/k)*e;
            }
            for(int i = 1 ; p.size()>i ; i++)
                p[i].F+=p[i-1].F,p[i].S+=p[i-1].S;
            sz=p.size();
        }
        pk=k;
        x/=k;
        ll mx = min(n,sum/x);
        if(mx==0)
        {
            ans[id]={0,0};
            continue;
        }
        ll mn = 0;
        ll l = 1 , r = sz-1;
        ll id1=sz , id2;
        while(l<=r)
        {
            if(p[sz-1].S-p[mid-1].S<=mx)
                id1=mid,r=mid-1;
            else
                l=mid+1;
        }
        l=0 , r = sz-1;
        while(l<=r)
        {
            if(v[mid].F<=x)
                id2=mid,l=mid+1;
            else
                r=mid-1;
        }
        mn = x*(p[id2].S-p[id1-1].S)-(p[id2].F - p[id1-1].F);
        ans[id].F=mx;
        mx-=(n-p[id1-1].S);
        mn += x*mx - (v[id1-1].F*mx);
        ans[id].S=mn;
    }
    for(int i = 0 ; q>i ; i++)
        cout << ans[i].F << " " << ans[i].S << "\n";
}

C++