Будинок у Minecraft#12216

Будинок у Minecraft (Розбір)

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

Рішення

Протягом рішення ми будемо припускати, що $n \leq m$ n \le m, якщо ні, ми можемо просто повернути сітку.

Ми не можемо дозволити собі симулювати кожен запит клітинка за клітинкою. Замість цього, ми обробляємо ряд за рядком.

Для фіксованого рядка $i$ , розглянемо запит $(x, y, d, c, s)$ (x,y,d,c,s). Всі клітинки, які задовольняють першу умову (умова відстані), формують діапазон $[l, r]$ [l,r].

Таким чином, кожен запит додає інтервал на рядку $i$ .

Ми можемо використовувати підхід з лінійним скануванням, щоб обчислити всі значення масиву $b$ для рядка $i$ .

Для рядка $i$ ми створюємо події в $l$ і $r + 1$ r+1 для інтервалу $[l, r]$ [l,r]. Кожна подія означає: "почати додавати цей запит" або "зупинити додавання цього запиту".

Ми підтримуємо масив частот $f [c]$ = загальна $s$ активних запитів з параметром $c$ . Ми також підтримуємо $s u m =$ суму всіх активних $s$ .

Коли обробляємо рядок $i$ і стовпець $j$ :

Якщо $a_{i, j} = 0$ a_{i,j}=0, тоді $b_{i, j} = s u m$ b_{i,j}=sum.
В іншому випадку, для кожного дільника $d$ з $a_{i, j}$ a_{i,j}, додайте $f [d]$ до $b_{i, j}$ b_{i,j}.

На завершення:

ми ітеруємо по всіх рядках ( $1 \leq i \leq n$ 1 \le i \le n), для кожного рядка ми ітеруємо по всіх запитах і знаходимо діапазон $[l, r]$ [l,r] для кожного запиту. Потім, використовуючи підхід з лінійним скануванням, ми можемо визначити значення масиву $b$ для цього рядка.

Складність:

Попереднє обчислення дільників: $O (n \cdot m \cdot max A)$ \mathcal{O}(n \cdot m \cdot \sqrt{\max A}).
Для кожного рядка ми ітеруємо по всіх запитах, тому це $O (n \cdot q)$ \mathcal{O}(n \cdot q).
Для кожної клітинки $(x, y)$ ми ітеруємо по всіх дільниках $a_{x, y}$ a_{x,y}, тому це $O (n \cdot m \cdot max D)$ \mathcal{O}(n \cdot m \cdot \max D).

Загальна складність становить $O (n \cdot m \cdot (max A + max D) + n \cdot q)$ \mathcal{O}(n \cdot m \cdot (\sqrt{\max A} + \max D) + n \cdot q), і оскільки $n \leq m$ n \le m, то $n \leq n \cdot m \leq 320$ n \le \sqrt{n \cdot m} \le 320, $max A$ <= $1 0^{6}$ 10^6, $max D = 240$ \max D = 240.

Отже, найгірша загальна складність становить $O (3 e 8)$ , що проходить за менше ніж 4 секунди.

Наступне - реалізація:


#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)
#define double long double
 
using namespace std;

mt19937 rnd(time(0));

const int N = 1e5+9 , NN = 1e6+9;

int q,c[N],se[100LL*N],org,sq[NN];
ll s[N],f[100LL*N],sum;
ll x[N] , y[N] , d[N] , n , m;
bool g,vis[100LL*N];
vector<int> divisors[100LL*N];

ll sqr(ll x)
{
    ll l = 0 , r = min(x,100000LL);
    ll ans;
    while(l<=r)
    {
        if(mid*mid<=x)
            ans=mid,l=mid+1;
        else
            r=mid-1;
    }
    return ans;
}

void factorize(int v)
{
    if(vis[v])
        return;
    vis[v]=1;
    for(ll i = 1 ; v>=i*i ; i++)
    {
        if(v%i==0)
        {
            divisors[v].pb(i);
            if(v/i!=i)
                divisors[v].pb(v/i);
        }
    }
}

int main()
{
    d3
    vis[0]=1;
    for(ll i = 0 ; NN>i ; i++)
        sq[i]=sqr(i);
    for(ll i = 2 ; 100LL*N>i ; i++)
    {
        if(se[i])
            continue;
        se[i]=i;
        for(ll j = i*i ; 100LL*N>j ; j+=i)
        {
            if(se[j])
                continue;
            se[j]=i;
        }
    }
    cin >> n >> m;
    if(n>m)
        swap(n,m),g=1;
    int a[n+1][m+1];
    ll b[n+1][m+1];
    memset(b,0,sizeof(b));
    vector<int> e[m+2];
    if(g)
        swap(n,m),g=0;
    if(n>m)
    {
        g=1;
        for(int i = 1 ; n>=i ; i++)
        {
            for(int j = 1 ; m>=j ; j++)
                cin>>a[j][i];
        }
        swap(n,m);
    }
    else
    {
        for(int i = 1 ; n>=i ; i++)
        {
            for(int j = 1 ; m>=j ; j++)
                cin>>a[i][j];
        }
    }
    for(int i = 1 ; n>=i ; i++)
        for(int j = 1 ; m>=j ; j++)
            factorize(a[i][j]);
    cin >> q;
    for(int qe = 1 ; q>=qe ; qe++)
    {
        cin >> x[qe] >> y[qe] >> d[qe] >> c[qe] >> s[qe];
        d[qe]*=d[qe];
        if(g)
            swap(x[qe],y[qe]);
    }
    ll mo = m*m;
    for(ll i = 1 ; n>=i ; i++)
    {
        ll de;
        int l , r;
        for(int qe = 1 ; q>=qe ; qe++)
        {
            de=d[qe]-(i-x[qe])*(i-x[qe]);
            if(de<0)
                continue;
            if(mo<=de)
                de=m;
            else if(de<NN)
                de=sq[de];
            else
                de=sqr(de);
            l=max(1LL,y[qe]-de);
            r=min(m,y[qe]+de);
            e[l].pb(qe);
            e[r+1].pb(-qe);
        }
        for(int j = 1 ; m+1>=j ; j++)
        {
            for(auto it : e[j])
            {
                if(it<0)
                    f[c[-it]]-=s[-it],sum-=s[-it];
                else
                    f[c[it]]+=s[it],sum+=s[it];
            }
            if(j==m+1)
                break;
            if(a[i][j]==0)
            {
                b[i][j]=sum;
                continue;
            }
            for(auto it : divisors[a[i][j]])
                b[i][j]+=f[it];
        }
        for(int j = 1 ; m+1>=j ; j++)
            e[j].clear();
    }
    if(g)
    {
        swap(n,m);
        for(int i = 1 ; n>=i ; i++)
        {
            for(int j = 1 ; m>=j ; j++)
                cout << b[j][i] << " ";
            lin
        }
    }
    else
    {
        for(int i = 1 ; n>=i ; i++)
        {
            for(int j = 1 ; m>=j ; j++)
                cout << b[i][j] << " ";
            lin
        }
    }
}