3161. Block Placement Queries

#include <stdlib.h>
#include <stdbool.h>

/*
 * 演算法 / Algorithm:
 *  離線 + 逆向掃描。先把所有障礙物放好，由後往前處理；遇到 type-1 就「移除」障礙物，
 *  這樣較早的查詢看到的就是正確的障礙物集合。移除會把兩個相鄰間隙合併成一個。
 *  兩棵線段樹：segGap 維護相鄰障礙物間的最大間隙，segPos 維護不超過 x 的最大障礙物座標。
 *  Offline + reverse scan. Place all obstacles, walk queries backwards, "remove" an
 *  obstacle on its type-1 query (merging two gaps). segGap tracks max gap between
 *  consecutive obstacles; segPos finds the largest obstacle position <= x.
 */

/* 給 qsort 用的整數比較器 / integer comparator for qsort */
static int cmpInt(const void *a, const void *b) {
    int x = *(const int *)a, y = *(const int *)b;  // 解參考取出兩個 int / dereference both ints
    return (x > y) - (x < y);                       // 回傳 -1/0/1，避免相減溢位 / safe compare, no overflow
}

/* 線段樹：點更新 + 區間最大值 / point-assign + range-max segment tree */
typedef struct {
    int *tree;  // 隱式二元樹陣列（1-indexed）/ implicit binary tree array (1-indexed)
    int n;      // 葉子數，代表座標 1..n / number of leaves = positions 1..n
} Seg;

/* 建立一棵全為 0 的線段樹 / create a segment tree filled with zeros */
static Seg *segCreate(int n) {
    Seg *s = (Seg *)malloc(sizeof(Seg));        // 配置結構本身 / allocate the struct
    s->n = n;                                   // 記住葉子數 / store leaf count
    s->tree = (int *)calloc(4 * (n + 1), sizeof(int)); // calloc 會把記憶體清成 0 / calloc zeroes memory; 4*(n+1) is safe size
    return s;
}

/* 把座標 pos 的值設成 val / set the value at position pos to val */
static void segUpdate(Seg *s, int node, int lo, int hi, int pos, int val) {
    if (lo == hi) {            // 走到葉子節點 / reached the leaf
        s->tree[node] = val;   // 直接賦值 / assign the new value
        return;
    }
    int mid = lo + (hi - lo) / 2;                       // 取中點，避免溢位 / midpoint without overflow
    if (pos <= mid) segUpdate(s, 2 * node, lo, mid, pos, val);          // 往左子樹 / go left
    else            segUpdate(s, 2 * node + 1, mid + 1, hi, pos, val);  // 往右子樹 / go right
    int a = s->tree[2 * node], b = s->tree[2 * node + 1];               // 取兩個子節點 / two children
    s->tree[node] = a > b ? a : b;                      // 父節點存兩者較大值 / parent keeps the max
}

/* 查詢區間 [ql, qr] 的最大值 / query the maximum over [ql, qr] */
static int segQuery(Seg *s, int node, int lo, int hi, int ql, int qr) {
    if (qr < lo || hi < ql) return 0;            // 完全沒交集，回傳 0（間隙與座標都 >=0）/ no overlap -> 0
    if (ql <= lo && hi <= qr) return s->tree[node]; // 區間被完全覆蓋，直接回傳 / fully covered
    int mid = lo + (hi - lo) / 2;                // 中點 / midpoint
    int a = segQuery(s, 2 * node, lo, mid, ql, qr);        // 查左半 / query left half
    int b = segQuery(s, 2 * node + 1, mid + 1, hi, ql, qr);// 查右半 / query right half
    return a > b ? a : b;                        // 合併取最大 / combine by max
}

bool *getResults(int **queries, int queriesSize, int *queriesColSize, int *returnSize) {
    /* 1) 掃一遍：找最大座標 maxX、數出障礙物個數 / first pass: find maxX and count obstacles */
    int maxX = 1, obsCount = 0;
    for (int i = 0; i < queriesSize; i++) {
        if (queries[i][1] > maxX) maxX = queries[i][1]; // queries[i][1] 是 x（兩種查詢都有）/ x exists in both types
        if (queries[i][0] == 1) obsCount++;             // type-1 才放障礙物 / only type-1 places obstacles
    }

    /* 2) 收集所有障礙物座標並排序 / collect obstacle positions and sort */
    int *obs = (int *)malloc(sizeof(int) * (obsCount > 0 ? obsCount : 1)); // 至少配 1 格避免 0 大小 / at least size 1
    int k = 0;
    for (int i = 0; i < queriesSize; i++)
        if (queries[i][0] == 1) obs[k++] = queries[i][1]; // 依出現順序先放進去 / gather then sort
    qsort(obs, obsCount, sizeof(int), cmpInt);            // 由小到大排序 / sort ascending

    /* 3) 座標 -> 排序後索引，方便移除時找鄰居 / map position to its sorted index */
    int *pos2idx = (int *)malloc(sizeof(int) * (maxX + 1));
    for (int i = 0; i <= maxX; i++) pos2idx[i] = -1;      // -1 表示該座標沒障礙物 / -1 means no obstacle
    for (int i = 0; i < obsCount; i++) pos2idx[obs[i]] = i;

    /* 4) 雙向鏈結串列：記住每個障礙物的左右鄰居 / doubly linked list of obstacles */
    int m = obsCount;
    int *prevArr = (int *)malloc(sizeof(int) * (m + 1));  // 多配一格給右哨兵 / extra slot for right sentinel
    int *nextArr = (int *)malloc(sizeof(int) * (m + 1));
    for (int i = 0; i < m; i++) { prevArr[i] = i - 1; nextArr[i] = i + 1; }
    /* prevArr[0] = -1 代表左邊沒有障礙物（視為座標 0）/ -1 = no left obstacle (acts as coord 0) */
    /* nextArr[m-1] = m 代表右邊沒有障礙物 / m = no right obstacle */

    /* 5) 建兩棵線段樹，並把「全部障礙物都在」的初始狀態填進去 / build trees for the all-present state */
    Seg *segGap = segCreate(maxX);  // 每個障礙物存它與左鄰的間隙 / gap to left neighbor
    Seg *segPos = segCreate(maxX);  // 每個障礙物存自己的座標 / its own position
    for (int i = 0; i < m; i++) {
        int gapLeft = obs[i] - (i > 0 ? obs[i - 1] : 0);  // 左鄰不存在就用 0 / left neighbor defaults to 0
        segUpdate(segGap, 1, 1, maxX, obs[i], gapLeft);
        segUpdate(segPos, 1, 1, maxX, obs[i], obs[i]);
    }

    /* 6) 算 type-2 數量、配置答案、預先決定每個查詢的輸出位置 / prepare output slots */
    int q2 = 0;
    for (int i = 0; i < queriesSize; i++) if (queries[i][0] == 2) q2++;
    bool *ans = (bool *)malloc(sizeof(bool) * (q2 > 0 ? q2 : 1));
    *returnSize = q2;                                     // 透過指標回傳答案長度 / report length via pointer
    int *outSlot = (int *)malloc(sizeof(int) * queriesSize);
    int s = 0;
    for (int i = 0; i < queriesSize; i++) outSlot[i] = (queries[i][0] == 2) ? s++ : -1; // 第幾個 type-2 / its rank

    /* 7) 逆向掃描所有查詢 / scan all queries in reverse */
    for (int i = queriesSize - 1; i >= 0; i--) {
        if (queries[i][0] == 1) {
            /* --- 移除障礙物（插入的逆操作）/ remove an obstacle (inverse of insert) --- */
            int x = queries[i][1];
            int idx = pos2idx[x];                 // 它在排序陣列中的索引 / its sorted index
            int l = prevArr[idx], r = nextArr[idx]; // 左右鄰居 / left & right neighbors
            segUpdate(segGap, 1, 1, maxX, x, 0);  // 它的間隙消失 / its gap disappears
            segUpdate(segPos, 1, 1, maxX, x, 0);  // 它不再是障礙物 / no longer an obstacle
            if (l >= 0) nextArr[l] = r;           // 重接鏈結串列 / relink left -> right
            if (r < m)  prevArr[r] = l;           // 重接鏈結串列 / relink right -> left
            if (r < m) {                          // 右鄰存在，它的間隙要擴大 / right neighbor's gap grows
                int prevPos = (l >= 0) ? obs[l] : 0; // 合併後右鄰的新左界 / merged gap's new left bound
                segUpdate(segGap, 1, 1, maxX, obs[r], obs[r] - prevPos);
            }
        } else {
            /* --- 回答 type-2 查詢 / answer a type-2 query --- */
            int x = queries[i][1], sz = queries[i][2];
            int lastObs = segQuery(segPos, 1, 1, maxX, 1, x); // 不超過 x 的最近障礙物（無則 0）/ nearest obstacle <= x
            int trailing = x - lastObs;            // 尾段空白：從該障礙物到 x / trailing free span
            int internalMax = segQuery(segGap, 1, 1, maxX, 1, x); // 內部最大間隙 / max internal gap with right end <= x
            int best = trailing > internalMax ? trailing : internalMax; // 兩種空白取較大 / largest empty span
            ans[outSlot[i]] = (best >= sz);        // 夠大就放得下 / fits iff best >= sz
        }
    }

    /* 8) 釋放暫存記憶體（ans 要回傳，不能 free）/ free scratch memory (keep ans) */
    free(obs); free(pos2idx); free(prevArr); free(nextArr); free(outSlot);
    free(segGap->tree); free(segGap);
    free(segPos->tree); free(segPos);
    return ans;
}

#include <vector>
#include <algorithm>
using namespace std;

/*
 * 演算法 / Algorithm:
 *  離線 + 逆向掃描。先放好所有障礙物，由後往前處理，type-1 視為「移除」(合併兩個間隙)。
 *  segGap 維護相鄰障礙物間的最大間隙，segPos 找出不超過 x 的最大障礙物座標。
 *  Offline + reverse scan: place all obstacles, walk backwards, treat type-1 as removal
 *  (merging two gaps). segGap = max gap between consecutive obstacles; segPos = largest
 *  obstacle position <= x. Each type-2 query is two O(log) lookups.
 */
class Solution {
    // 線段樹：點更新 + 區間最大值 / point-assign + range-max segment tree
    struct Seg {
        int n;                  // 葉子數 / number of leaves
        vector<int> tree;       // 隱式樹，vector 會自動管理記憶體 / implicit tree; vector manages memory
        Seg(int n) : n(n), tree(4 * (n + 1), 0) {}  // 建構：開 4*(n+1) 個 0 / build with zeros

        // 內部遞迴版點更新 / internal recursive point update
        void update(int node, int lo, int hi, int pos, int val) {
            if (lo == hi) { tree[node] = val; return; }      // 葉子直接賦值 / assign at leaf
            int mid = lo + (hi - lo) / 2;                    // 中點 / midpoint
            if (pos <= mid) update(2 * node, lo, mid, pos, val);        // 往左 / go left
            else            update(2 * node + 1, mid + 1, hi, pos, val);// 往右 / go right
            tree[node] = max(tree[2 * node], tree[2 * node + 1]);       // 父=子的最大 / parent = max of children
        }
        void update(int pos, int val) { update(1, 1, n, pos, val); }    // 對外簡化介面 / public wrapper

        // 內部遞迴版區間最大查詢 / internal recursive range-max query
        int query(int node, int lo, int hi, int ql, int qr) {
            if (qr < lo || hi < ql) return 0;                // 無交集 / no overlap
            if (ql <= lo && hi <= qr) return tree[node];     // 完全覆蓋 / fully covered
            int mid = lo + (hi - lo) / 2;
            return max(query(2 * node, lo, mid, ql, qr),
                       query(2 * node + 1, mid + 1, hi, ql, qr)); // 左右取最大 / combine by max
        }
        int query(int ql, int qr) { return query(1, 1, n, ql, qr); }    // 對外簡化介面 / public wrapper
    };

public:
    vector<bool> getResults(vector<vector<int>>& queries) {
        int n = queries.size();
        int maxX = 1;
        vector<int> obs;                                  // 所有障礙物座標 / all obstacle positions
        for (auto& q : queries) {                          // range-for：逐一取出每個查詢 / iterate each query
            maxX = max(maxX, q[1]);                         // q[1] 是 x / x for both types
            if (q[0] == 1) obs.push_back(q[1]);             // type-1 收集障礙物 / collect obstacles
        }
        sort(obs.begin(), obs.end());                       // 由小到大排序 / sort ascending
        int m = obs.size();

        vector<int> pos2idx(maxX + 1, -1);                  // 座標 -> 排序索引，-1 表示無 / position -> sorted index
        for (int i = 0; i < m; i++) pos2idx[obs[i]] = i;

        vector<int> prevArr(m + 1), nextArr(m + 1);         // 雙向鏈結串列 / doubly linked list
        for (int i = 0; i < m; i++) { prevArr[i] = i - 1; nextArr[i] = i + 1; }
        // prevArr[0] = -1：左邊視為座標 0；nextArr[m-1] = m：右邊無障礙物
        // prevArr[0] = -1 acts as coord 0; nextArr[m-1] = m means no right obstacle

        Seg segGap(maxX), segPos(maxX);                     // 兩棵線段樹 / two segment trees
        for (int i = 0; i < m; i++) {
            int gapLeft = obs[i] - (i > 0 ? obs[i - 1] : 0); // 與左鄰的間隙，無左鄰用 0 / gap to left neighbor
            segGap.update(obs[i], gapLeft);
            segPos.update(obs[i], obs[i]);
        }

        vector<int> outSlot(n, -1);                          // 每個查詢的輸出位置 / output slot per query
        int q2 = 0;
        for (int i = 0; i < n; i++) if (queries[i][0] == 2) outSlot[i] = q2++;
        vector<bool> ans(q2);                                // 答案陣列 / answers

        for (int i = n - 1; i >= 0; i--) {                   // 逆向掃描 / reverse scan
            if (queries[i][0] == 1) {
                // --- 移除障礙物 / remove obstacle ---
                int x = queries[i][1], idx = pos2idx[x];
                int l = prevArr[idx], r = nextArr[idx];      // 左右鄰居 / neighbors
                segGap.update(x, 0);                         // 間隙消失 / gap gone
                segPos.update(x, 0);                         // 不再是障礙物 / not an obstacle
                if (l >= 0) nextArr[l] = r;                  // 重接 / relink
                if (r < m)  prevArr[r] = l;                  // 重接 / relink
                if (r < m) {                                 // 右鄰間隙擴大 / right neighbor's gap grows
                    int prevPos = (l >= 0) ? obs[l] : 0;     // 合併後的左界 / merged left bound
                    segGap.update(obs[r], obs[r] - prevPos);
                }
            } else {
                // --- 回答 type-2 / answer type-2 ---
                int x = queries[i][1], sz = queries[i][2];
                int lastObs = segPos.query(1, x);            // 不超過 x 的最近障礙物 / nearest obstacle <= x
                int trailing = x - lastObs;                  // 尾段空白 / trailing span
                int internalMax = segGap.query(1, x);        // 內部最大間隙 / max internal gap (right end <= x)
                ans[outSlot[i]] = max(trailing, internalMax) >= sz; // 取較大者與 sz 比 / fits iff best >= sz
            }
        }
        return ans;
    }
};