Хацуне Міку#11856

Хацуне Міку (Розбір)

Автор проблеми:	(De3b0o)
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	(De3b0o)

Рішення

Оскільки $k$ є дільником $x$ , тобто $x mod k = 0$ x \bmod k=0, ми можемо ігнорувати $a_{i} mod k$ a_i \bmod k.

Доказ :

Припустимо, у нас є число $y < x$ y<x, $y mod k = 0$ y \bmod k = 0 і нам потрібно $e$ операцій, щоб зробити його рівним $x$ , формально

(y + e k = x)

\displaystyle (y + ek = x)

Тоді для числа $y + z$ y+z, де $0 \leq z < k$ 0 \le z<k (це означає, що $(y + z) mod k = z$ (y+z) \bmod k = z), якщо ми виконаємо $e - 1$ e-1 операцій, нове число буде $y + z + (e - 1) \cdot k < y + e \cdot k = x$ y+z+(e-1) \cdot k < y+e \cdot k = x, тому нам все ще потрібна одна операція, щоб зробити його принаймні $x$ , ми все ще використовуємо $e$ операцій, тому $a_{i} mod k$ a_i \bmod k не має значення.

Тепер, якщо ми оновимо кожне $a_{i}$ a_i до $a_{i} - a_{i} mod k$ a_i - a_i \bmod k, всі елементи стануть кратними $k$ , тому ми можемо просто поділити все на $k$ .

Ми залишилися з $k = \frac{k}{k} = 1$ k=\frac{k}{k}=1, $x = \frac{x}{k}$ x=\frac{x}{k} і $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.

Тепер $k = 1$ k=1, тому набагато легше знайти відповідь на запит.

Для одного запиту:

(ми будемо посилатися на максимальну кількість одержимих фанатів як $mx$ і мінімальну кількість операцій, що потрібні, як $mn$ , і всі значення після оновлення, тому $k = 1$ k=1, $x = \frac{x}{k}$ x=\frac{x}{k} і $⌊ \frac{a _{i}}{k} ⌋$ \displaystyle \left \lfloor \frac{a_i}{k} \right \rfloor.

Ми можемо легко побачити, що

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

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

Щоб знайти $mn$ , ми спочатку спостерігаємо, що оптимально зробити найбільшого фаната $mx$ в масиві одержимим (оскільки це вимагає менше операцій).

Серед $mx$ найбільших елементів, якщо всі елементи вже більші за $x$ , тоді $mn = 0$ \text{mn} = 0.

В іншому випадку, для кожного елемента, який строго менше $x$ , ми повинні зробити його рівним $x$ .

Припустимо, є $z$ таких елементів, $y_{1}, y_{2}, y_{3}, ..., y_{z}$ y_1 , y_2 , y_3 , ... , y_z.

Тоді

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

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

Якщо масив $a$ відсортований, ми можемо легко обчислити $mx$ , $mn$ , використовуючи префіксні суми та бінарний пошук.

Тепер нам лише потрібно спосіб підтримувати масив $a$ та префіксні суми для кожного різного $k$ .

Для одного $k$ , кількість різних значень $⌊ \frac{a _{i}}{k} ⌋$ \displaystyle \left \lfloor \frac{a_i}{k} \right \rfloor є максимум $\frac{m a x ( a )}{k}$ \frac{\max(a)}{k}, тому ми можемо стиснути масив $a$ до $\frac{m a x ( a )}{k}$ \frac{\max(a)}{k} елементів і підтримувати частоти.

Якщо ми зробимо це для кожного $k$ , складність буде максимум $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}), що є $O (A lo g (A))$ \mathcal{O}(A \log(A)), де $A = max (a)$ A = \max(a).

Посилаючись на гармонічний ряд, де:

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

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

так що остаточна складність є $O (A lo g (A) + q lo g (n))$ \mathcal{O}(A \log(A) + q \log(n)), що є достатньо швидким.

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