#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;
}