#pragma GCC optimize("O3,unroll-loops") #include using namespace std; using i64 = long long; static constexpr int MAXN = 200000; static constexpr int MAXQ = 200000; static constexpr int MAXLOG = 18; static constexpr int MAXG = MAXN + MAXLOG + 8; /* 各三角形について U0 = A+B U1 = B-A U2 = B L0 = A+B-2D L1 = B-A-2D L2 = B-D を使う。 区間で必要なのは min U0, min U1, min U2, max L0, max L1, max L2 なので、max を min に統一するため { U0, U1, U2, -L0, -L1, -L2 } を保持する。 */ struct Six { i64 v0, v1, v2; i64 v3, v4, v5; }; static Six basev[MAXN]; static Six agg[MAXN]; struct RawQ { int s, l, r, id, g; }; struct GQ { int s, l, r, id; }; static RawQ rawq[MAXQ]; static GQ gq[MAXQ]; static unsigned char ans[MAXQ]; static int off[MAXLOG + 1]; static int cnt[MAXG]; static int st[MAXG + 1]; static int pos[MAXG]; static int minL[MAXG]; static int maxR[MAXG]; static inline __attribute__((always_inline)) void take_min(Six& a, const Six& b) { if (b.v0 < a.v0) a.v0 = b.v0; if (b.v1 < a.v1) a.v1 = b.v1; if (b.v2 < a.v2) a.v2 = b.v2; if (b.v3 < a.v3) a.v3 = b.v3; if (b.v4 < a.v4) a.v4 = b.v4; if (b.v5 < a.v5) a.v5 = b.v5; } // [l,l] の1要素だけの場合 static inline __attribute__((always_inline)) bool check_one(const Six& x, const Six& s) { return x.v0 > -s.v3 && x.v1 > -s.v4 && x.v2 > -s.v5 && x.v3 > -s.v0 && x.v4 > -s.v1 && x.v5 > -s.v2; } // range aggregate = min(x,y) // min(x_i,y_i) > t // ⇔ x_i > t && y_i > t // // なので実際に min を作る必要すらない。 static inline __attribute__((always_inline)) bool check_two( const Six& x, const Six& y, const Six& s ) { return x.v0 > -s.v3 && y.v0 > -s.v3 && x.v1 > -s.v4 && y.v1 > -s.v4 && x.v2 > -s.v5 && y.v2 > -s.v5 && x.v3 > -s.v0 && y.v3 > -s.v0 && x.v4 > -s.v1 && y.v4 > -s.v1 && x.v5 > -s.v2 && y.v5 > -s.v2; } class FastInput { static constexpr int SZ = 1 << 20; char buf[SZ]; int ptr = 0; int len = 0; inline char gc() { if (ptr == len) { len = (int)fread(buf, 1, SZ, stdin); ptr = 0; if (!len) return 0; } return buf[ptr++]; } public: inline i64 readLL() { char c = gc(); while (c <= ' ') c = gc(); bool neg = false; if (c == '-') { neg = true; c = gc(); } i64 x = 0; while (c >= '0') { x = x * 10 + (c - '0'); c = gc(); } return neg ? -x : x; } inline int readInt() { return (int)readLL(); } }; int main() { FastInput in; const int N = in.readInt(); for (int i = 0; i < N; ++i) { const i64 A = in.readLL(); const i64 B = in.readLL(); const i64 D = in.readLL(); const i64 U0 = A + B; const i64 U1 = B - A; const i64 U2 = B; const i64 L0 = U0 - 2 * D; const i64 L1 = U1 - 2 * D; const i64 L2 = B - D; basev[i] = { U0, U1, U2, -L0, -L1, -L2 }; } /* l != r のクエリについて k = msb(l xor r) とすると、長さ 2^(k+1) の同一ブロック内で mid -----------|----------- l r と必ず左右に分かれる。 左側は suffix minimum、 右側は prefix minimum だけ作ればよい。 */ int levels = 0; int G = 0; while ((1 << levels) < N) { off[levels] = G; const int blockSize = 1 << (levels + 1); G += (N + blockSize - 1) / blockSize; ++levels; } for (int g = 0; g < G; ++g) { minL[g] = N; maxR[g] = -1; } const int Q = in.readInt(); // l != r のクエリ数 int M = 0; for (int id = 0; id < Q; ++id) { const int s = in.readInt() - 1; const int l = in.readInt() - 1; const int r = in.readInt() - 1; /* 長さ1ならRMQを作る必要がない。 */ if (l == r) { ans[id] = (unsigned char)check_one( basev[l], basev[s] ); continue; } const unsigned z = (unsigned)(l ^ r); const int k = 31 - __builtin_clz(z); /* 2^(k+1) ブロックの番号 */ const int b = l >> (k + 1); const int g = off[k] + b; rawq[M++] = { s, l, r, id, g }; ++cnt[g]; if (l < minL[g]) minL[g] = l; if (r > maxR[g]) maxR[g] = r; } /* group ID による counting sort。 linked list にすると、 Query 配列をランダムに辿ることになる。 ここでは同じ group の Query を gq[] の連続領域に詰める。 */ for (int g = 0; g < G; ++g) { st[g + 1] = st[g] + cnt[g]; } memcpy( pos, st, G * sizeof(int) ); for (int i = 0; i < M; ++i) { const RawQ& q = rawq[i]; gq[pos[q.g]++] = { q.s, q.l, q.r, q.id }; } /* 各 Disjoint Sparse Table level を処理。 ただし Sparse Table 全体は作らない。 その group に属する Query の 最小 l ~ mid mid ~ 最大 r の部分だけ構築する。 */ for (int k = 0; k < levels; ++k) { const int half = 1 << k; const int blockSize = half << 1; const int groupCount = (N + blockSize - 1) / blockSize; const int groupOffset = off[k]; for ( int b = 0; b < groupCount; ++b ) { const int g = groupOffset + b; if (cnt[g] == 0) continue; const int mid = b * blockSize + half; const int lo = minL[g]; const int hi = maxR[g]; /* [lo, mid) の suffix componentwise-min */ Six cur = basev[mid - 1]; agg[mid - 1] = cur; for ( int i = mid - 2; i >= lo; --i ) { take_min( cur, basev[i] ); agg[i] = cur; } /* [mid, hi] の prefix componentwise-min */ cur = basev[mid]; agg[mid] = cur; for ( int i = mid + 1; i <= hi; ++i ) { take_min( cur, basev[i] ); agg[i] = cur; } /* group 内の Query は counting sort 済みなので連続。 */ const int end = st[g + 1]; for ( int p = st[g]; p < end; ++p ) { const GQ& q = gq[p]; ans[q.id] = (unsigned char) check_two( agg[q.l], agg[q.r], basev[q.s] ); } } } /* 出力 */ static char out[MAXQ * 4 + 8]; char* p = out; for (int i = 0; i < Q; ++i) { if (ans[i]) { *p++ = 'Y'; *p++ = 'e'; *p++ = 's'; *p++ = '\n'; } else { *p++ = 'N'; *p++ = 'o'; *p++ = '\n'; } } fwrite( out, 1, (size_t)(p - out), stdout ); return 0; }