Hatsune Miku#11856

Hatsune Miku (Corrigé)

Auteur du problème :	(De3b0o)
Préparé par :	Hasan Saleh (MathModel)
Édité par :	(De3b0o)

Solution

Puisque $k$ est un facteur de $x$ , c'est-à-dire $x mod k = 0$ x \bmod k=0, nous pouvons ignorer $a_{i} mod k$ a_i \bmod k.

Preuve :

Disons que nous avons un nombre $y < x$ y<x, $y mod k = 0$ y \bmod k = 0 et nous avons besoin de $e$ opérations pour le rendre égal à $x$ , formellement

(y + e k = x)

\displaystyle (y + ek = x)

Alors pour le nombre $y + z$ y+z où $0 \leq z < k$ 0 \le z<k (ce qui signifie que $(y + z) mod k = z$ (y+z) \bmod k = z), si nous appliquons $e - 1$ e-1 opérations, le nouveau nombre est $y + z + (e - 1) \cdot k < y + e \cdot k = x$ y+z+(e-1) \cdot k < y+e \cdot k = x, donc nous avons toujours besoin d'une opération pour le rendre au moins $x$ , nous utilisons toujours $e$ opérations donc $a_{i} mod k$ a_i \bmod k est sans importance.

Maintenant, si nous mettons à jour chaque $a_{i}$ a_i à $a_{i} - a_{i} mod k$ a_i - a_i \bmod k, tous les éléments vont devenir des multiples de $k$ , donc nous pouvons simplement diviser tout par $k$ .

Il nous reste $k = \frac{k}{k} = 1$ k=\frac{k}{k}=1, $x = \frac{x}{k}$ x=\frac{x}{k} et $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.

Maintenant $k = 1$ k=1, donc il est beaucoup plus facile de trouver la réponse à la requête.

Pour une seule requête :

(nous allons nous référer au nombre maximum de fans obsédés comme $mx$ et au minimum d'opérations requises comme $mn$ , et toutes les valeurs sont après la mise à jour donc $k = 1$ k=1, $x = \frac{x}{k}$ x=\frac{x}{k} et $⌊ \frac{a _{i}}{k} ⌋$ \displaystyle \left \lfloor \frac{a_i}{k} \right \rfloor.

Nous pouvons facilement voir que

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

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

Pour trouver $mn$ , nous observons d'abord qu'il est optimal de rendre le plus grand fan $mx$ dans le tableau obsédé (car cela nécessite moins d'opérations).

Parmi les $mx$ plus grands éléments, si tous les éléments sont déjà supérieurs à $x$ , alors $mn = 0$ \text{mn} = 0.

Sinon, pour chaque élément qui est strictement inférieur à $x$ , nous devons le rendre égal à $x$ .

Disons qu'il y a $z$ tels éléments, $y_{1}, y_{2}, y_{3}, ..., y_{z}$ y_1 , y_2 , y_3 , ... , y_z.

Alors

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

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

Si le tableau $a$ est trié, nous pouvons facilement calculer $mx$ , $mn$ en utilisant des sommes préfixes et une recherche binaire.

Maintenant, nous n'avons besoin que d'un moyen de maintenir le tableau $a$ et les sommes préfixes pour chaque $k$ différent.

Pour un seul $k$ , le nombre de valeurs distinctes $⌊ \frac{a _{i}}{k} ⌋$ \displaystyle \left \lfloor \frac{a_i}{k} \right \rfloor est au maximum $\frac{m a x ( a )}{k}$ \frac{\max(a)}{k}, donc nous pouvons compresser le tableau a en $\frac{m a x ( a )}{k}$ \frac{\max(a)}{k} éléments et maintenir les fréquences.

Si nous faisons cela pour chaque $k$ , la complexité est au maximum $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}) ce qui est $O (A lo g (A))$ \mathcal{O}(A \log(A)), où $A = max (a)$ A = \max(a).

Référez-vous à la série harmonique, où :

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

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

donc la complexité finale est $O (A lo g (A) + q lo g (n))$ \mathcal{O}(A \log(A) + q \log(n)) ce qui est assez rapide.

#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 << "OUI" << "\n";
#define no cout << "NON" << "\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++