Hatsune Miku#11856

Hatsune Miku (Həll təhlili)

Problem Müəllifi:	(De3b0o)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	(De3b0o)

Həll

$k$ $x$ -in böləni olduğu üçün, yəni $x mod k = 0$ x \bmod k=0, $a_{i} mod k$ a_i \bmod k-ni nəzərə almaya bilərik.

Sübut :

Tutaq ki, $y < x$ y<x bir ədədimiz var, $y mod k = 0$ y \bmod k = 0 və onu $x$ -ə bərabər etmək üçün $e$ əməliyyata ehtiyac var, rəsmi olaraq

(y + e k = x)

\displaystyle (y + ek = x)

Sonra $y + z$ y+z ədədinə baxaq, burada $0 \leq z < k$ 0 \le z<k (bu, $(y + z) mod k = z$ (y+z) \bmod k = z deməkdir), əgər $e - 1$ e-1 əməliyyatını tətbiq etsək, yeni ədəd $y + z + (e - 1) \cdot k < y + e \cdot k = x$ y+z+(e-1) \cdot k < y+e \cdot k = x olacaq, buna görə də onu ən az $x$ -ə bərabər etmək üçün hələ bir əməliyyata ehtiyac var, $e$ əməliyyatını hələ də istifadə edirik, buna görə də $a_{i} mod k$ a_i \bmod k əhəmiyyətsizdir.

İndi əgər hər $a_{i}$ a_i-ni $a_{i} - a_{i} mod k$ a_i - a_i \bmod k-ya yeniləsək, bütün elementlər $k$ -nin tam ədədləri olacaq, beləliklə, hər şeyi $k$ -yə bölə bilərik.

Bizim qalan $k = \frac{k}{k} = 1$ k=\frac{k}{k}=1 , $x = \frac{x}{k}$ x=\frac{x}{k} və $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.

İndi $k = 1$ k=1 olduğu üçün sorğunun cavabını tapmaq daha asandır.

Bir tək sorğu üçün:

(biz obsesif azarkeşlərin maksimum sayını $mx$ və tələb olunan minimum əməliyyat sayını $mn$ adlandıracağıq, və bütün dəyərlər yeniləndikdən sonra $k = 1$ k=1 , $x = \frac{x}{k}$ x=\frac{x}{k} və $⌊ \frac{a _{i}}{k} ⌋$ \displaystyle \left \lfloor \frac{a_i}{k} \right \rfloor).

Asanlıqla görə bilərik ki,

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

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

$mn$ -ni tapmaq üçün əvvəlcə müşahidə edirik ki, massivdəki ən böyük $mx$ azarkeşi obsesif etmək optimaldır (çünki daha az əməliyyat tələb edir).

$mx$ ən böyük elementlər arasında, əgər bütün elementlər artıq $x$ -dən böyükdürsə, onda $mn = 0$ \text{mn} = 0.

Əks halda, $x$ -dən aşağı olan hər bir element üçün, onu $x$ -ə bərabər etmək lazımdır.

Tutaq ki, $z$ belə element var, $y_{1}, y_{2}, y_{3}, ..., y_{z}$ y_1 , y_2 , y_3 , ... , y_z.

Onda

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

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

Əgər massiv $a$ sıralanmışdırsa, $mx$ və $mn$ -ni prefiks cəmləri və ikili axtarışdan istifadə edərək asanlıqla hesablaya bilərik.

İndi yalnız $a$ massivini və hər fərqli $k$ üçün prefiks cəmlərini saxlamaq üçün bir yol lazımdır.

Tək bir $k$ üçün, fərqli dəyərlərin sayı $⌊ \frac{a _{i}}{k} ⌋$ \displaystyle \left \lfloor \frac{a_i}{k} \right \rfloor maksimum $\frac{m a x ( a )}{k}$ \frac{\max(a)}{k}-dir, beləliklə, massiv $a$ -nı $\frac{m a x ( a )}{k}$ \frac{\max(a)}{k} elementinə sıxışdırıb tezlikləri saxlaya bilərik.

Bunu hər $k$ üçün etsək, mürəkkəblik maksimum $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}) olacaq ki, bu da $O (A lo g (A))$ \mathcal{O}(A \log(A))-dir, burada $A = max (a)$ A = \max(a).

Harmonik Seriyaya baxın, Harada:

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

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

Beləliklə, son mürəkkəblik $O (A lo g (A) + q lo g (n))$ \mathcal{O}(A \log(A) + q \log(n))-dir ki, bu da kifayət qədər sürətlidir.

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