pre = set([0]) # nums[i] ^ nums[j] ans = set([nums[0]]) for k inrange(1, n): for i inrange(k + 1): pre.add(nums[i] ^ nums[k]) # nums[i] ^ nums[j] for p in pre: ans.add(p ^ nums[k]) # (nums[i] ^ nums[j]) ^ nums[k] returnlen(ans)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution { public: intuniqueXorTriplets(vector<int>& nums){ nums.erase(unique(nums.begin(), nums.end()), nums.end()); // 去重 int n = nums.size(); int mx = *max_element(nums.begin(), nums.end()); int U = 1 << (32 - __builtin_clz(mx)); vector<bool> pre(U), ans(U); // 用 vector 代替 set pre[0] = ans[nums[0]] = true; for (int k = 1; k < n; k++) { for (int i = 0; i <= k; i++) // nums[i] ^ nums[j] pre[nums[i] ^ nums[k]] = true; for (int i = 0; i < U; i++) // (nums[i] ^ nums[j]) ^ nums[k] if (pre[i]) ans[i ^ nums[k]] = true; } returncount(ans.begin(), ans.end(), true); } };
graph TD
%% 原始樹範例
subgraph "Tree"
A((1)) --> B((2))
A --> C((3))
B --> D((4))
B --> E((5))
C --> F((6))
end
%% 設定節點樣式
classDef root fill:#f9d5e5,stroke:#333,stroke-width:2px
classDef node fill:#eeeeee,stroke:#333,stroke-width:1px
%% 套用樣式
class A root
class B,C,D,E,F node
# update the range [l, r] with value v @staticmethod defupdate(node: SegNode, left: int, right: int, l: int, r: int, v: int) -> None: if l <= left and right <= r: # update node value (Customized) SegmentTree._update(node, left, right, v) return SegmentTree.pushdown(node, left, right) # push down lazy tags mid = (left + right) // 2 if l <= mid: SegmentTree.update(node.ls, left, mid, l, r, v) if r > mid: SegmentTree.update(node.rs, mid + 1, right, l, r, v) SegmentTree.pushup(node) # push up node value
# update node value (Customized) @staticmethod def_update(node: SegNode, left: int, right: int, v: int) -> None: node.val += v * (right - left + 1) node.lazy += v
# query the range [l, r] @staticmethod defquery(node: SegNode, left: int, right: int, l: int, r: int) -> int: if l <= left and right <= r: return node.val # Ensure all lazy tags have been pushed down SegmentTree.pushdown(node, left, right) mid = (left + right) // 2 # Calculate answer (Customized) ans = 0 if l <= mid: ans += SegmentTree.query(node.ls, left, mid, l, r) if r > mid: ans += SegmentTree.query(node.rs, mid + 1, right, l, r) return ans # push down lazy tags @staticmethod defpushdown(node: SegNode, left: int, right: int) -> None: if node.ls isNone: node.ls = SegNode() if node.rs isNone: node.rs = SegNode() if node.lazy != 0: # Update node value (Customized) mid = (left + right) // 2 SegmentTree._update(node.ls, left, mid, node.lazy) SegmentTree._update(node.rs, mid + 1, right, node.lazy) node.lazy = 0 # push up node value @staticmethod defpushup(node: SegNode) -> None: # Update method (Customized) node.val = node.ls.val + node.rs.val
classSolution: deftreeQueries(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]: g = defaultdict(list) mp = {} for u, v, w in edges: if u > v: u, v = v, u g[u].append((v, w)) g[v].append((u, w)) mp[(u, v)] = w
defdfs(u, fa, d): nonlocal time time += 1 dfns[u] = time dist[u] = d for v, w in g[u]: if v == fa: continue dfs(v, u, d + w) dfne[u] = time
dfs(1, 0, 0) st = SegmentTree([0] * n) # 維護變化量
ans = [] for query in queries: op, *args = query if op == 1: u, v, w = args if u > v: u, v = v, u c = u if dist[u] > dist[v] else v # 判斷哪個是子節點 st.update(st.root, 1, n, dfns[c], dfne[c], w - mp[(u, v)]) mp[(u, v)] = w elif op == 2: x = args[0] ans.append(dist[x] + st.query(st.root, 1, n, dfns[x] , dfns[x])) return ans
voidbuild(SegNode<T> *node, int left, int right, vector<T> &nums){ if (left == right) { node->val = nums[left - 1]; // assert nums is 0-indexed return; } int mid = left + ((right - left) >> 1); node->ls = newSegNode<T>(); node->rs = newSegNode<T>(); build(node->ls, left, mid, nums); build(node->rs, mid + 1, right, nums); pushup(node); // Push up node value }
// Update the range [l, r] with value v voidupdate(SegNode<T> *node, int left, int right, int l, int r, T v){ if (l <= left && right <= r) { // Update node value (Customized) _update(node, left, right, v); return; } pushdown(node, left, right); int mid = left + ((right - left) >> 1); if (l <= mid) update(node->ls, left, mid, l, r, v); if (r > mid) update(node->rs, mid + 1, right, l, r, v); pushup(node); // Push up node value }
// Update node value (Customized) void _update(SegNode<T> *node, int left, int right, T v) { node->val += v * (right - left + 1); node->lazy += v; }
// Query the range [l, r] T query(SegNode<T> *node, int left, int right, int l, int r){ if (l <= left && right <= r) { return node->val; } pushdown(node, left, right); int mid = left + ((right - left) >> 1); // Calculate answer (Customized) T ans = 0; if (l <= mid) ans += query(node->ls, left, mid, l, r); if (r > mid) ans += query(node->rs, mid + 1, right, l, r); return ans; }
// Push down lazy tags voidpushdown(SegNode<T> *node, int left, int right){ if (node->ls == nullptr) node->ls = newSegNode<T>(); if (node->rs == nullptr) node->rs = newSegNode<T>(); if (node->lazy != 0) { int mid = left + ((right - left) >> 1); // Update node value (Customized) _update(node->ls, left, mid, node->lazy); _update(node->rs, mid + 1, right, node->lazy); node->lazy = 0; } }
// Push up node value voidpushup(SegNode<T> *node){ // Update method (Customized) node->val = node->ls->val + node->rs->val; } };
classSolution { public: vector<int> treeQueries(int n, vector<vector<int>>& edges, vector<vector<int>>& queries){ vector<vector<pair<int, int>>> g(n + 1); for (auto &edge : edges) { int u = edge[0], v = edge[1], w = edge[2]; g[u].emplace_back(v, w); g[v].emplace_back(u, w); }
vector<int> dist(n + 1), dfns(n + 1), dfne(n + 1), weight(n + 1); int time = 0; // timestamp, 1-indexed auto dfs = [&](thisauto &&dfs, int u, int fa, int d) -> void { dfns[u] = ++time; dist[u] = d; for (auto [v, w] : g[u]) { if (v == fa) continue; weight[v] = w; // store weight at child node dfs(v, u, d + w); } dfne[u] = time; }; dfs(1, 0, 0); SegmentTree<longlong> st; vector<int> ans; for (auto &query : queries) { int op = query[0]; if (op == 1) { int u = query[1], v = query[2], w = query[3]; if (dist[u] > dist[v]) swap(u, v); // let v be the child node st.update(st.root, 1, n, dfns[v], dfne[v], w - weight[v]); weight[v] = w; // update weight } else { int x = query[1]; ans.push_back(dist[x] + st.query(st.root, 1, n, dfns[x], dfns[x])); } } return ans; } };
寫在最後
PROMPT
masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, anime style, ((artist:reoen), (artist:fuzichoco), (artist:atdan), (artist:torino_aqua), year 2024:0.8), [artist:wlop], [artist:ningen_mame], artist:ciloranko, [[artist:rhasta]], artist:tidsean,
1girl, solo, Mumei, Nanashi Mumei, virtual youtuber, vtuber, brown hair, long hair, very long hair, brown eyes, hair ornament, feather, sitting pose, elegant white dress with floral embellishments, sheer sleeves with pearl details, dimly lit background with soft lighting,
The image features a character with long brown hair and brown eyes, dressed in an elegant white dress adorned with floral patterns and sheer sleeves decorated with pearls. She is seated in a dimly lit setting with a soft, warm glow illuminating her figure.
這場打得有點隨興，Q2 直接暴力打表猜了結論，Q3 也是看到值域後直接寫了個很接近很暴力的東西，幸好沒有在這種手速場吃到 WA XD
![Luogu 🟢 P2627 [USACO11OPEN] Mowing the Lawn G](https://i.gdst.dev/works/846172612737479668.webp)
