2097 . 爆裂遊戲（駭客題）
TopCoder
Tags
Description
Original Description
有一天，阿克婭和惠惠一起走在路上聊天。
「惠惠阿，妳最近是不是很久沒用爆裂魔法啦～」
「並沒有喔，我每天還是有練習喔，而且經由長期練習，我現在一天要施放 $10^ 5$ 次爆裂魔法都沒有問題喔～」
「真的喔，那，讓我見識一下吧！帶妳去一個好地方。」
阿克婭帶著惠惠到了一座巨大森林面前。這座森林可以視為一個 $[-10^ {18}, 10^ {18}] \times [-10^ {18}, 10^ {18}]$ 的二維平面，每一個格子點（座標 $(x, y)$ 中，$x, y$ 都是整數的點）都種了一棵樹。這座森林的樹有一個特殊功能：存水。每棵樹一開始的存水量都是 $0$ 單位，每棵樹都沒有存水量的上限，也就是說，每棵樹是可以存下無限多單位的水。
惠惠看到前面的森林是施放爆裂魔法的好地方，於是就開始準備念咒語：「比黑色更黑，比黑暗更暗的漆黑，在此寄託吾真紅的金光吧，覺醒之時的到來，荒謬教會的墮落章理，化作無形的扭曲而顯現吧，Ex-plo...」
「等一下啦，惠惠，直接讓妳釋放爆裂魔法太無聊了，為了讓妳有挑戰一點，我準備了一些東西～」
原來，身為水神的阿克婭，準備了很多的水，來挑戰惠惠的爆裂魔法。已知一單位的水需要一單位的爆裂魔法，才能讓水完全消失。
「接下來有一些指令，我們一同來完成。」阿克婭說道，「指令有倒水跟爆裂兩種。倒水指令是：我會在 $(x_1, y_1)$ 到 $(x_2, y_2)$ 這個線段上（包含兩個端點）所有的格子點上面的樹倒下 $w$ 單位的水，線段不是平行於 $x$ 軸，就是平行於 $y$ 軸。爆裂指令是要請妳告訴我，如果妳在 $(x, y)$ 這個格子點上，使用爆裂魔法的話，會需要使用多少單位，才能讓位於 $(x, y)$ 的那棵樹的水完全消失。」
「不能使用爆裂魔法喔，好難過喔......」
「如果妳成功告訴我每次爆裂指令的答案，並且都是正確的話，我就讓妳對這整座森林使用爆裂魔法。」
「可是我不會算數學阿......」
你，身為惠惠的好友，決定挺身而出來幫助她。惠惠會告訴你每次阿克婭的指令，當發生爆裂指令時，請你告訴惠惠正確的答案。
Original Input Format
輸入的第一行包含一個正整數 $N$ ，代表阿克婭的操作的數量。
接下來的 $N$ 行，每行代表一個指令，依序是惠惠和阿克婭要完成的。指令的格式不外乎是下面兩種：
- $1 \ x_1 \ y_1 \ x_2 \ y_2 \ w$：倒水指令，代表阿克婭會在 $(x_1, y_1)$ 到 $(x_2, y_2)$ 這個線段上所有的格子點上面的樹倒下 $w$ 單位的水。
- $2 \ x \ y$：爆裂指令，代表阿克婭要求惠惠算出：如果她在 $(x, y)$ 這個格子點上，使用爆裂魔法，會需要使用多少單位，才能讓位於 $(x, y)$ 的那棵樹的水完全消失。
測試資料範圍限制：
- $1 \leq N \leq 10^ 5$
- $x_1, y_1, x_2, y_2, w, x, y$ 全部都是整數
- $-10^ {18} \leq x_1 \le x_2 \leq 10^ {18}$
- $-10^ {18} \leq y_1 \le y_2 \leq 10^ {18}$
- $-10^ {18} \leq x, y \leq 10^ {18}$
- $1 \leq w \leq 10^ 9$
- $x_1 = y_1, x_2 = y_2$ 這兩個條件中至少一個會成立
Original Output Format
對於每次爆裂指令，請輸出一個數字：如果惠惠在 $(x, y)$ 這個格子點上，使用爆裂魔法，會需要使用多少單位，才能讓位於 $(x, y)$ 的那棵樹的水完全消失。
Original Sample Input
5
2 0 0
1 1 0 1 2 1
2 1 1
1 0 2 2 2 2
2 1 2
Original Sample Output
0
1
3
Original Limits
- Time Limit: 2 second
- Memory Limit: 1024 MB
Program To Be Hacked
#include <bits/stdc++.h> using namespace std; struct treap { long long pos, val, sum; int sz, pri; treap *lc, *rc; treap(long long p, long long v): pos(p), sum(v), val(v), sz(1), pri(rand()), lc(nullptr), rc(nullptr) {} void pull() { sum = val, sz = 1; if (lc) sz += lc->sz, sum += lc->sum; if (rc) sz += rc->sz, sum += rc->sum; } }; treap *merge(treap *a, treap *b) { if (!a || !b) return a ? a : b; if (a->pri > b->pri) return a->rc = merge(a->rc, b), a->pull(), a; else return b->lc = merge(a, b->lc), b->pull(), b; } void split(treap *t, long long k, treap *&a, treap *&b) { if (!t) return a = b = nullptr, void(); if (t->pos <= k) a = t, split(t->rc, k, a->rc, b), a->pull(); else b = t, split(t->lc, k, a, b->lc), b->pull(); } map<long long, int> dx, dy; int rev(long long x, map<long long, int> &d) { if (d.find(x) != d.end()) return d[x]; int res = (int)d.size(); return d[x] = res; } const int maxn = 1e6 + 5; treap *tx[maxn], *ty[maxn]; void insert(treap *&t, long long p, long long v) { treap *a, *b; split(t, p - 1, a, b); t = merge(merge(a, new treap(p, v)), b); } long long query(treap *t, long long p) { treap *a, *b; split(t, p, a, b); long long res = (a ? a->sum : 0); t = merge(a, b); return res; } int main() { int n; scanf("%d", &n); long long last = 0; for (int i = 0; i < maxn; ++i) { tx[i] = nullptr; ty[i] = nullptr; } for (int i = 0; i < n; ++i) { int t; scanf("%d", &t); if (t == 1) { long long xa, ya, xb, yb, w; scanf("%lld%lld%lld%lld%lld", &xa, &ya, &xb, &yb, &w); assert(xa == xb || ya == yb); if (xa == xb) { long long p = rev(xa, dx); insert(tx[p], min(ya, yb) + 0, +w); insert(tx[p], max(ya, yb) + 1, -w); } else { long long p = rev(ya, dy); insert(ty[p], min(xa, xb) + 0, +w); insert(ty[p], max(xa, xb) + 1, -w); } } else { long long x, y; scanf("%lld%lld", &x, &y); last = query(tx[rev(x, dx)], y) + query(ty[rev(y, dy)], x); printf("%lld\n", last); } } return 0; }
Judge Method
請輸出一個測試資料，使得上述的程式碼會不會得到 Accepted。
Sample Code
以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。
#include <cstdio> int main() { printf("1\n2 0 0\n"); }
Input Format
Output Format
Hints
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 1 |