Прямокутна спіраль Фібоначчі (Розбір)

Автор задачі:	Андрій Холод (Connect)
Підготував:	Андрій Холод (Connect)
Розбір:	Андрій Холод (Connect)

Ідея

Кожна спіраль задається лише початковою точкою $(x_{i}, y_{i})$ (x_i,y_i). Усе інше в неї однакове: ті самі напрямки, ті самі довжини відрізків, ті самі кути.

Тобто будь-яка спіраль — це просто одна й та сама канонічна спіраль, зсунута на вектор $(x_{i}, y_{i})$ (x_i,y_i).

Тому замість того, щоб працювати з $n$ різними спіралями окремо, достатньо:

побудувати одну канонічну спіраль із початком у $(0, 0)$ ;
для кожного її відрізка порахувати, скільки стартових точок переводять цей відрізок у точку запиту.

1) Канонічна спіраль

Побудуємо спіраль, що починається в $(0, 0)$ .

Нехай її $i$ -й відрізок має один із чотирьох напрямків: $[(1, 0), (0, 1), (- 1, 0), (0, - 1)]$ [ (1,0),\ (0,1),\ (-1,0),\ (0,-1) ] а довжина дорівнює $f_{i}$ f_i.

Код просто симулює перші відрізки цієї ламаної і зберігає:

усі горизонтальні та вертикальні відрізки;
усі точки зламу (corners).

Для кожного відрізка зберігається:

його тип: горизонтальний чи вертикальний;
фіксована координата;
межі по другій координаті.

2) Чому достатньо лише перших 55 відрізків

Це ключовий момент.

Початкові точки спіралей задовольняють: $∣ x_{i} ∣, ∣ y_{i} ∣ \leq 1 0^{9}$ |x_i|, |y_i| \le 10^9 а точки запитів: $∣ x ∣, ∣ y ∣ \leq 1 0^{7}$ |x|, |y| \le 10^7

Отже якщо точка $(x, y)$ лежить на спіралі з початком у $(x_{i}, y_{i})$ (x_i,y_i), то відповідна точка на канонічній спіралі має координати $(x - x_{i}, y - y_{i})$ (x - x_i,\ y - y_i) тобто $∣ x - x_{i} ∣ \leq 1.01 \cdot 1 0^{9}, ∣ y - y_{i} ∣ \leq 1.01 \cdot 1 0^{9} .$ |x - x_i| \le 1.01 \cdot 10^9, |y - y_i| \le 1.01 \cdot 10^9.

А координати канонічної спіралі ростуть приблизно як числа Фібоначчі. Уже через кілька десятків кроків вони за модулем стають значно більшими за $1 0^{9}$ 10^9. Тому жоден пізніший відрізок уже не може дати точку, яка після зсуву потрапить у жоден запит.

У коді взято запас із 55 відрізків, цього більш ніж достатньо.

3) Як порахувати внесок одного горизонтального відрізка

Нехай у канонічній спіралі є горизонтальний відрізок: $y = c, x \in [L, R] .$ y = c, x \in [L,R].

Після зсуву на стартову точку $(s_{x}, s_{y})$ (s_x,s_y) він стане: $y = s_{y} + c, x \in [s_{x} + L, s_{x} + R] .$ y = s_y + c, x \in [s_x + L,\ s_x + R].

Точка запиту $(q_{x}, q_{y})$ (q_x,q_y) лежить на цьому зсунутому відрізку тоді й лише тоді, коли:

$q_{y} = s_{y} + c$ q_y = s_y + c і $q_{x} \in [s_{x} + L, s_{x} + R] .$ q_x \in [s_x + L,\ s_x + R].

Перепишемо це як умови на стартову точку:

$s_{y} = q_{y} - c$ s_y = q_y - c і $s_{x} \in [q_{x} - R, q_{x} - L] .$ s_x \in [q_x - R,\ q_x - L].

Тобто для кожного горизонтального відрізка задача зводиться до такого запиту:

Порахувати, скільки стартових точок мають $y = q_{y} - c$ y = q_y - c i $x \in [q_{x} - R, q_{x} - L]$ x \in [q_x - R,\ q_x - L].

4) Як порахувати внесок вертикального відрізка

Аналогічно, якщо канонічний відрізок вертикальний: $x = c, y \in [L, R],$ x = c, y \in [L,R], то після зсуву на $(s_{x}, s_{y})$ (s_x,s_y) він стане: $x = s_{x} + c, y \in [s_{y} + L, s_{y} + R] .$ x = s_x + c, y \in [s_y + L,\ s_y + R].

Точка $(q_{x}, q_{y})$ (q_x,q_y) лежить на ньому тоді й лише тоді, коли: $s_{x} = q_{x} - c$ s_x = q_x - c і $s_{y} \in [q_{y} - R, q_{y} - L] .$ s_y \in [q_y - R,\ q_y - L].

Тобто треба порахувати кількість стартових точок із $x = q_{x} - c$ x = q_x - c та $y \in [q_{y} - R, q_{y} - L]$ y \in [q_y - R,\ q_y - L].

5) Як швидко рахувати такі точки

Маємо стартові точки спіралей: $(x_{i}, y_{i}) .$ (x_i,y_i).

Можна будувати два масиви:

by_X: пари $(x_{i}, y_{i})$ (x_i,y_i), відсортовані лексикографічно;
by_Y: пари $(y_{i}, x_{i})$ (y_i,x_i), також відсортовані.

Тоді:

для вертикального відрізка ми фіксуємо $x$ і шукаємо всі $y$ у проміжку;
для горизонтального відрізка ми фіксуємо $y$ і шукаємо всі $x$ у проміжку.

Це робиться двома бінарними пошуками:

lower_bound — початок підходящого діапазону;
upper_bound — кінець.

Кількість точок у цьому діапазоні й додається до відповіді.

6) Чому треба віднімати кути

Якщо точка запиту потрапляє рівно в точку зламу спіралі, то вона належить двом сусіднім відрізкам одночасно. Тоді ми порахуємо цю саму спіраль двічі:

один раз через попередній відрізок;
ще раз через наступний.

Тому після підрахунку всіх відрізків треба відняти кількість спіралей, для яких запит потрапив у вершину канонічної спіралі.

Це можна підтримувати окремим масивом

Якщо вершина канонічної спіралі має координати $(c_{x}, c_{y})$ (c_x,c_y), то для запиту $(q_{x}, q_{y})$ (q_x,q_y) шукаємо стартові точки: $(s_{x}, s_{y}) = (q_{x} - c_{x}, q_{y} - c_{y}) .$ (s_x,s_y) = (q_x - c_x,\ q_y - c_y).

Кількість таких стартів уже була врахована двічі, тому її потрібно відняти один раз.

9) Асимптотика

Нехай $K = 55$ K=55 — кількість згенерованих відрізків.

Попередня обробка:

сортування стартових точок — $O (n lo g n)$ O(n \log n);
побудова канонічної спіралі — $O (K)$ .

Один запит:

проходимо по всіх $K$ відрізках;
для кожного робимо $O (lo g n)$ O(\log n) через бінарні пошуки;
окремо проходимо по всіх $K - 1$ K-1 кутах.

Отже один запит працює за: $O (K lo g n)$ O(K \log n), а оскільки $K$ — константа, це просто $O (lo g n) .$ O(\log n).

Сумарно: $O (n lo g n + q lo g n) .$ O(n \log n + q \log n).

Код рішення

#include <bits/stdc++.h>
#include <random>
// fast_pragmas

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,tune=native")

// fast_pragmas ended

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using namespace std;

#define ull unsigned long long
#define ll long long
#define ld long double
#define speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define endl '\n'
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define pb push_back
#define ln log
#define lg log10
#define log log2
#define here cout<<"HERE"<<endl

const ll clasik = 5e5 + 7;
const ll mln = 1e6 + 7;
const ll mod = 1e9 + 7;
//const ll mod = 998244353;
const ll block_size = 450;
const ll INF = 1e17;

ll df[clasik];

struct Segment {
    char type;
    ll fixed;
    ll min_val;
    ll max_val;
};

void solve() {
    ll n;
    cin >> n;

    vector<pair<ll, ll>> by_X(n), by_Y(n);

    ll min_x = (ll)2e18, max_x = -(ll)2e18;
    ll min_y = (ll)2e18, max_y = -(ll)2e18;

    for (int i = 0; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        by_X[i] = {x, y};
        by_Y[i] = {y, x};

        min_x = min(min_x, x);
        max_x = max(max_x, x);
        min_y = min(min_y, y);
        max_y = max(max_y, y);
    }

    sort(by_X.begin(), by_X.end());
    sort(by_Y.begin(), by_Y.end());

    vector<ll> f(60);
    f[1] = 1;
    f[2] = 1;
    for (int i = 3; i <= 55; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }

    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};

    vector<Segment> segs;
    vector<pair<ll, ll>> corners;

    ll cx = 0, cy = 0;

    for (int i = 1; i <= 55; i++) {
        ll nx = cx + f[i] * dx[(i - 1) % 4];
        ll ny = cy + f[i] * dy[(i - 1) % 4];

        if ((i - 1) % 2 == 0) {
            segs.pb({'H', cy, min(cx, nx), max(cx, nx)});
        } else {
            segs.pb({'V', cx, min(cy, ny), max(cy, ny)});
        }

        if (i < 55) {
            corners.pb({nx, ny});
        }

        cx = nx;
        cy = ny;
    }

    ll q;
    cin >> q;

    while (q--) {
        ll qx, qy;
        cin >> qx >> qy;
        ll ans = 0;

        for (auto seg : segs) {
            if (seg.type == 'H') {
                ll py = qy - seg.fixed;
                ll px_min = qx - seg.max_val;
                ll px_max = qx - seg.min_val;

                if (py >= min_y && py <= max_y && px_max >= min_x && px_min <= max_x) {
                    auto it_start = lower_bound(by_Y.begin(), by_Y.end(), make_pair(py, px_min));
                    if (it_start != by_Y.end() && it_start->first == py && it_start->second <= px_max) {
                        auto it_end = upper_bound(it_start, by_Y.end(), make_pair(py, px_max));
                        ans += distance(it_start, it_end);
                    }
                }
            } else {
                ll px = qx - seg.fixed;
                ll py_min = qy - seg.max_val;
                ll py_max = qy - seg.min_val;

                if (px >= min_x && px <= max_x && py_max >= min_y && py_min <= max_y) {
                    auto it_start = lower_bound(by_X.begin(), by_X.end(), make_pair(px, py_min));
                    if (it_start != by_X.end() && it_start->first == px && it_start->second <= py_max) {
                        auto it_end = upper_bound(it_start, by_X.end(), make_pair(px, py_max));
                        ans += distance(it_start, it_end);
                    }
                }
            }
        }

        for (auto c : corners) {
            ll px = qx - c.first;
            ll py = qy - c.second;

            if (px >= min_x && px <= max_x && py >= min_y && py <= max_y) {
                auto it_start = lower_bound(by_X.begin(), by_X.end(), make_pair(px, py));
                if (it_start != by_X.end() && it_start->first == px && it_start->second == py) {
                    auto it_end = upper_bound(it_start, by_X.end(), make_pair(px, py));
                    ans -= distance(it_start, it_end);
                }
            }
        }

        cout << ans << endl;
    }
}

signed main() {

    //freopen("deciding_points_input.txt" , "r" , stdin);
    //freopen("outputA.txt" , "w" , stdout);

    speed;
    int test;
    test = 1;
    //precalc();
    //cin >> test;
    for (int tt = 1; tt <= test; tt++) {
        //cout << "Case #" << tt << ": ";
        solve();
    }

    return 0;
}

C++