有一天,阿克婭和惠惠一起走在路上聊天。
「惠惠阿,妳最近是不是很久沒用爆裂魔法啦~」
「並沒有喔,我每天還是有練習喔,而且經由長期練習,我現在一天要施放 $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)$ 的那棵樹的水完全消失。」
「不能使用爆裂魔法喔,好難過喔......」
「如果妳成功告訴我每次爆裂指令的答案,並且都是正確的話,我就讓妳對這整座森林使用爆裂魔法。」
「可是我不會算數學阿......」
你,身為惠惠的好友,決定挺身而出來幫助她。惠惠會告訴你每次阿克婭的指令,當發生爆裂指令時,請你告訴惠惠正確的答案。
輸入的第一行包含一個正整數 $N$ ,代表阿克婭的操作的數量。
接下來的 $N$ 行,每行代表一個指令,依序是惠惠和阿克婭要完成的。指令的格式不外乎是下面兩種:
測試資料範圍限制:
對於每次爆裂指令,請輸出一個數字:如果惠惠在 $(x, y)$ 這個格子點上,使用爆裂魔法,會需要使用多少單位,才能讓位於 $(x, y)$ 的那棵樹的水完全消失。
5
2 0 0
1 1 0 1 2 1
2 1 1
1 0 2 2 2 2
2 1 2
0
1
3
#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;
}
請輸出一個測試資料,使得上述的程式碼會不會得到 Accepted
。
以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。
#include <cstdio>
int main() {
printf("1\n2 0 0\n");
}
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 1 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 3000 | 262144 | 262144 |