#include #include #include #include #include #include using namespace std; typedef long long LL; const LL INF_EXT = 1LL << 60; const int INF_KEY = 2000000000; struct SegTree { int n, sz; vector tree; vector keys; unordered_map pos; void Init(const vector &sorted_keys) { keys = sorted_keys; sz = keys.size(); n = 1; while (n < sz) { n *= 2; } tree.assign(2 * n, 0); pos.clear(); for (int i = 0; i < sz; ++i) { pos[keys[i]] = i; } } void Update(int key, LL value) { if (pos.find(key) == pos.end()) return; int idx = pos[key] + n; tree[idx] = value; for (idx /= 2; idx >= 1; idx /= 2) { tree[idx] = max(tree[2 * idx], tree[2 * idx + 1]); } } int QueryMin(LL threshold) { if (tree[1] < threshold) return INF_KEY; int idx = 1; while (idx < n) { int left = 2 * idx; if (tree[left] >= threshold) idx = left; else idx = left + 1; } return keys[idx - n]; } int QueryMaxRec(int idx, int l, int r, LL threshold) { if (r - l == 1) return tree[idx] >= threshold ? keys[l] : -1; int mid = l + r >> 1; int right = 2 * idx + 1, left = 2 * idx; if (tree[right] >= threshold) return QueryMaxRec(right, mid, r, threshold); if (tree[left] >= threshold) return QueryMaxRec(left, l, mid, threshold); return -1; } int QueryMax(LL threshold) { if (tree[1] < threshold) return -1; return QueryMaxRec(1, 0, n, threshold); } }; SegTree seg_l, seg_r, seg_b, seg_t; unordered_map val_l, val_r, val_b, val_t; int w, h; LL ans; LL GetVal(char grp, int key) { if (grp == 'L') return val_l.count(key) ? val_l[key] : 0LL; if (grp == 'R') return val_r.count(key) ? val_r[key] : 0LL; if (grp == 'B') return val_b.count(key) ? val_b[key] : 0LL; return val_t.count(key) ? val_t[key] : 0LL; } void SetVal(char grp, int key, LL value) { if (grp == 'L') { val_l[key] = value; seg_l.Update(key, value); } else if (grp == 'R') { val_r[key] = value; seg_r.Update(key, value); } else if (grp == 'B') { val_b[key] = value; seg_b.Update(key, value); } else { val_t[key] = value; seg_t.Update(key, value); } } void ProcessL(int y, LL add) { LL cur = GetVal('L', y), new_val = cur + add; LL r_val = GetVal('R', y); LL cand1 = (w + 1) - r_val; int cand2_key = seg_b.QueryMin(y); LL cand2 = cand2_key == INF_KEY ? INF_EXT : cand2_key; int cand3_key = seg_t.QueryMin((h + 1) - y); LL cand3 = cand3_key == INF_KEY ? INF_EXT : cand3_key; LL safe_max = min(min(cand1, cand2), cand3) - 1; if (new_val <= safe_max) SetVal('L', y, new_val); else { SetVal('L', y, 0); if (cand1 == safe_max + 1) SetVal('R', y, 0); if (cand2 == safe_max + 1) SetVal('B', cand2_key, 0); if (cand3 == safe_max + 1) SetVal('T', cand3_key, 0); } } void ProcessR(int y, LL add) { LL cur = GetVal('R', y), new_val = cur + add; LL l_val = GetVal('L', y); LL cand1 = (w + 1) - l_val; int bottom_max = seg_b.QueryMax(y); LL cand2 = bottom_max == -1 ? INF_EXT : (w + 1) - bottom_max; int top_max = seg_t.QueryMax((h + 1) - y); LL cand3 = top_max == -1 ? INF_EXT : (w + 1) - top_max; LL safe_max = min(min(cand1, cand2), cand3) - 1; if (new_val <= safe_max) SetVal('R', y, new_val); else { SetVal('R', y, 0); if (cand1 == safe_max + 1) SetVal('L', y, 0); if (cand2 == safe_max + 1) SetVal('B', bottom_max, 0); if (cand3 == safe_max + 1) SetVal('T', top_max, 0); } } void ProcessB(int x, LL add) { LL cur = GetVal('B', x), new_val = cur + add; LL t_val = GetVal('T', x); LL cand1 = (h + 1) - t_val; int cand2_key = seg_l.QueryMin(x); LL cand2 = cand2_key == INF_KEY ? INF_EXT : cand2_key; int cand3_key = seg_r.QueryMin((w + 1) - x); LL cand3 = cand3_key == INF_KEY ? INF_EXT : cand3_key; LL safe_max = min(min(cand1, cand2), cand3) - 1; if (new_val <= safe_max) SetVal('B', x, new_val); else { SetVal('B', x, 0); if (cand1 == safe_max + 1) SetVal('T', x, 0); if (cand2 == safe_max + 1) SetVal('L', cand2_key, 0); if (cand3 == safe_max + 1) SetVal('R', cand3_key, 0); } } void ProcessT(int x, LL add) { LL cur = GetVal('T', x), new_val = cur + add; LL b_val = GetVal('B', x); LL cand1 = (h + 1) - b_val; int left_max = seg_l.QueryMax(x); LL cand2 = left_max == -1 ? INF_EXT : (h + 1) - left_max; int right_max = seg_r.QueryMax((w + 1) - x); LL cand3 = right_max == -1 ? INF_EXT : (h + 1) - right_max; LL safe_max = min(min(cand1, cand2), cand3) - 1; if (new_val <= safe_max) SetVal('T', x, new_val); else { SetVal('T', x, 0); if (cand1 == safe_max + 1) SetVal('B', x, 0); if (cand2 == safe_max + 1) SetVal('L', left_max, 0); if (cand3 == safe_max + 1) SetVal('R', right_max, 0); } } /** * 将边界蛇分四组 (Left/Right/Bottom/Top),各组按 key 建线段树(维护最大延伸值)。 * * 每次操作:new_val = cur + add * safe_max = min(三方向阻挡距离) - 1 * 若 new_val ≤ safe_max → 更新延伸值;否则 → 撞到的蛇均缩回(置 0) * * 阻挡查询(以左蛇 (0,y) 为例): * - 对面右蛇 (W+1,y):safe_max < (W+1) - r_val * - 底部蛇 (x,0):QueryMin(延伸值 ≥ y) 返回最小 x(即第一个挡住的列) * - 顶部蛇 (x,H+1):QueryMin(延伸值 ≥ H+1-y) 返回最小 x */ int main() { int n; scanf("%d%d%d", &h, &w, &n); vector> ops; ops.reserve(n); set s_l, s_r, s_b, s_t; for (int i = 0, x, y; i < n; ++i) { LL l_add; scanf("%d%d%lld", &x, &y, &l_add); ops.push_back({ x, y, l_add }); if (x == 0) s_l.insert(y); else if (x == w + 1) s_r.insert(y); else if (y == 0) s_b.insert(x); else s_t.insert(x); } vector vec_l(s_l.begin(), s_l.end()); vector vec_r(s_r.begin(), s_r.end()); vector vec_b(s_b.begin(), s_b.end()); vector vec_t(s_t.begin(), s_t.end()); seg_l.Init(vec_l); seg_r.Init(vec_r); seg_b.Init(vec_b); seg_t.Init(vec_t); for (int y : vec_l) { val_l[y] = 0; seg_l.Update(y, 0); } for (int y : vec_r) { val_r[y] = 0; seg_r.Update(y, 0); } for (int x : vec_b) { val_b[x] = 0; seg_b.Update(x, 0); } for (int x : vec_t) { val_t[x] = 0; seg_t.Update(x, 0); } for (auto [x, y, l_add] : ops) { if (x == 0) ProcessL(y, l_add); else if (x == w + 1) ProcessR(y, l_add); else if (y == 0) ProcessB(x, l_add); else ProcessT(x, l_add); } ans = 0LL; for (auto [k, v] : val_l) { ans += v; } for (auto [k, v] : val_r) { ans += v; } for (auto [k, v] : val_b) { ans += v; } for (auto [k, v] : val_t) { ans += v; } printf("%lld\n", ans); return 0; }