c++

Equiseca 发表于 8天前 · 关联问题 找女朋友

ouo

#include <bits/stdc++.h> #define int long long using namespace std; constexpr const int N = 105; struct Node_x { int ls, rs; int rty; } sgt_x[N * 100]; struct Node_y { int ls, rs; int v; } sgt_y[N * 100]; int idx, idy; int rngx, rngy; void ins_y(int y, int v, int ly, int ry, int &rty) { if (not rty) rty = ++idy; sgt_y[rty].v += v; if (ly == ry - 1) return ; int mid = (ly + ry) >> 1; if (y < mid) ins_y(y, v, ly, mid, sgt_y[rty].ls); else ins_y(y, v, mid, ry, sgt_y[rty].rs); } void ins_x(int x, int y, int v, int lx, int rx, int &rtx) { if (not rtx) rtx = ++idx; ins_y(y, v, 0, rngy + 1, sgt_x[rtx].rty); if (lx == rx - 1) return ; int mid = (lx + rx) >> 1; if (x < mid) ins_x(x, y, v, lx, mid, sgt_x[rtx].ls); else ins_x(x, y, v, mid, rx, sgt_x[rtx].rs); } int que_y(int sy, int ey, int ly, int ry, int rty) { if (sy <= ly && ry <= ey) return sgt_y[rty].v; int mid = (ly + ry) >> 1, ans = 0; if (sy < mid) ans += que_y(sy, ey, ly, mid, sgt_y[rty].ls); if (ey > mid) ans += que_y(sy, ey, mid, ry, sgt_y[rty].rs); return ans; } int que_x(int sx, int sy, int ex, int ey, int lx, int rx, int rtx) { if (sx <= lx && rx <= ex) return que_y(sy, ey, 0, rngy + 1, sgt_x[rtx].rty); int mid = (lx + rx) >> 1, ans = 0; if (sx < mid) ans += que_x(sx, sy, ex, ey, lx, mid, sgt_x[rtx].ls); if (ex > mid) ans += que_x(sx, sy, ex, ey, mid, rx, sgt_x[rtx].rs); return ans; } void build(int x, int y) { idx = 0, idy = 0; rngx = x, rngy = y; memset(sgt_x, 0, sizeof sgt_x); memset(sgt_y, 0, sizeof sgt_y); } void solve() { int n, m; cin >> n >> m; int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; build(n, m); int rtx = 0; ins_x(x1, y1, 1, 0, rngx + 1, rtx); ins_x(x2, y2, 1, 0, rngx + 1, rtx); int res = que_x(x1, y1, rngx + 1, rngy + 1, 0, rngx + 1, rtx); if (res == 1) cout << "Single dog!" << "\n"; else cout << abs(x1 - x2) + abs(y1 - y2) << "\n"; } signed main() { std::cin.tie(nullptr) -> sync_with_stdio(false); int t; cin >> t; while (t--) solve(); }