URAL 1707 Hypnotoad's Secret - 樹狀數組離線處理矩形點包含查詢

題目大意

給定 n × n 網格 (n ≤ 5000)，動態生成點集 (通過線性同餘序列) 和矩形查詢 (通過參數化生成)。每個查詢詢問矩形內是否包含點。輸出格式特殊：查詢數 ≤ 20 直接輸出 0/1 序列，否則輸出加權哈希值。多測資至 EOF。

核心技巧：離線掃描線 + 樹狀數組 (Fenwick Tree)

將 2D 包含查詢轉化為 1D 前綴和

矩形 [a, b] × [c, d] 內點數 = S(b,d) - S(a-1,d) - S(b,c-1) + S(a-1,c-1)，其中 S(x,y) = 左下角 (0,0) 到 (x,y) 的點數。
若能快速得到所有查詢相關的 S(x,y)，即可 O(1) 回答矩形查詢。

離線事件排序

構建事件列表：

• 點事件：(x, y, is_query=false)，來自生成的點集。
• 查詢子事件：每個矩形查詢拆解為 4 個 S(x,y) 查詢點：(b,d), (a-1,d), (b,c-1), (a-1,c-1)，標記 is_query=true 並記錄屬於哪個矩形的哪個角。

所有事件按 y 升序、再 x 升序、再 點事件優先於查詢事件 排序。

掃描線處理

按排序順序遍歷事件：

• 遇點事件 (x,y)：樹狀數組 add(x+1, 1) (x 0-based → 1-based)。
• 遇查詢事件 (x,y)：S(x,y) = query(x+1) (前綴和 1..x+1)，存入 map[(x,y)]。

掃描結束後，所有 S(x,y) 已就緒。

矩形查詢回答

對每個矩形查詢，用容斥原理組合 4 個 S 值得點數 cnt。cnt > 0 → 1，否則 0。按輸出格式輸出。

關鍵代碼結構

struct Event { int x, y; bool is_query; };
bool cmp(Event a, Event b) {
    if (a.y != b.y) return a.y < b.y;
    if (a.x != b.x) return a.x < b.x;
    return a.is_query < b.is_query; // 點優先 (false=0 < true=1)
}

// 樹狀數組
int bit[MAXN];
void add(int x, int v) { for (; x <= n; x += x&-x) bit[x] += v; }
int query(int x) { int r=0; for(;x;x-=x&-x) r+=bit[x]; return r; }

// 主流程
vector events;
// 1. 生成所有點加入 events (is_query=false)
// 2. 讀取查詢參數，生成矩形，拆解 4 角加入 events (is_query=true)，記錄映射
// 3. sort(events, cmp)
// 4. 掃描 events：點→add，查詢→query 存 map
// 5. 對每個矩形，容斥計算 cnt，輸出

複雜度

• 事件總數：點 O(n) + 查詢 O(m·q) (m≤350, q≤...)，總 ~1e6 級。
• 排序：O(E log E)。
• 掃描：O(E log n) (樹狀數組操作)。
• 總體 O((n + mq) log n) 極易通過。

特殊輸出處理

• 查詢組內子查詢數 q ≤ 20：直接輸出 0/1 字串。
• q > 20：輸出 ∑_{j=0}^{q-1} ans[j] * 7^j mod (200904040930+33)。預計算 7^j mod MOD。