Hatsune Miku#11856

Hatsune Miku (Editorial)

Autor del Problema:	(De3b0o)
Preparado por:	Hasan Saleh (MathModel)
Editado por:	(De3b0o)

Solución

Dado que $k$ es un factor de $x$ , es decir, $x mod k = 0$ x \bmod k=0, podemos ignorar $a_{i} mod k$ a_i \bmod k.

Prueba :

digamos que tenemos un número $y < x$ y<x, $y mod k = 0$ y \bmod k = 0 y necesitamos $e$ operaciones para hacerlo igual a $x$ , formalmente

(y + e k = x)

\displaystyle (y + ek = x)

Entonces para el número $y + z$ y+z donde $0 \leq z < k$ 0 \le z<k (esto significa $(y + z) mod k = z$ (y+z) \bmod k = z), si aplicamos $e - 1$ e-1 operaciones, el nuevo número es $y + z + (e - 1) \cdot k < y + e \cdot k = x$ y+z+(e-1) \cdot k < y+e \cdot k = x, así que todavía necesitamos una operación para hacerlo al menos $x$ , seguimos usando $e$ operaciones, por lo que $a_{i} mod k$ a_i \bmod k es irrelevante.

Ahora, si actualizamos cada $a_{i}$ a_i a $a_{i} - a_{i} mod k$ a_i - a_i \bmod k, todos los elementos serán múltiplos de $k$ , así que solo podemos dividir todo por $k$ .

Nos queda $k = \frac{k}{k} = 1$ k=\frac{k}{k}=1, $x = \frac{x}{k}$ x=\frac{x}{k} y $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.

Ahora $k = 1$ k=1, así que es mucho más fácil encontrar la respuesta de la consulta.

Para una sola consulta:

(vamos a referirnos al número máximo de fans obsesionados como $mx$ y la mínima cantidad de operaciones requeridas como $mn$ , y todos los valores son después de la actualización, así que $k = 1$ k=1, $x = \frac{x}{k}$ x=\frac{x}{k} y $⌊ \frac{a _{i}}{k} ⌋$ \displaystyle \left \lfloor \frac{a_i}{k} \right \rfloor.

Podemos ver fácilmente que

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

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

Para encontrar $mn$ , primero observamos que es óptimo hacer que el fan más grande $mx$ en el arreglo esté obsesionado (porque toma menos operaciones).

Entre los $mx$ elementos más grandes, si todos los elementos ya son mayores que $x$ , entonces $mn = 0$ \text{mn} = 0.

De lo contrario, para cada elemento que es estrictamente menor que $x$ , tenemos que hacerlo igual a $x$ .

Digamos que hay $z$ tales elementos, $y_{1}, y_{2}, y_{3}, ..., y_{z}$ y_1 , y_2 , y_3 , ... , y_z.

Entonces

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

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

Si el arreglo $a$ está ordenado, podemos calcular fácilmente $mx$ , $mn$ usando sumas prefijas y búsqueda binaria.

Ahora solo necesitamos una forma de mantener el arreglo $a$ y las sumas prefijas para cada $k$ diferente.

Para un solo $k$ , el número de valores distintos $⌊ \frac{a _{i}}{k} ⌋$ \displaystyle \left \lfloor \frac{a_i}{k} \right \rfloor es como máximo $\frac{m a x ( a )}{k}$ \frac{\max(a)}{k}, así que podemos comprimir el arreglo $a$ en $\frac{m a x ( a )}{k}$ \frac{\max(a)}{k} elementos y mantener frecuencias.

Si hacemos esto para cada $k$ , la complejidad es como máximo $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}) que es $O (A lo g (A))$ \mathcal{O}(A \log(A)), donde $A = max (a)$ A = \max(a).

Refiérase a la serie armónica, donde:

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

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

así que la complejidad final es $O (A lo g (A) + q lo g (n))$ \mathcal{O}(A \log(A) + q \log(n)) que es lo suficientemente rápida.

#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++