51Nod 1295. XOR key[区间最大异或](可持久化Trie) 日付: 11月 01, 2018 リンクを取得 Facebook × Pinterest メール 他のアプリ ## Problem $q$次询问求数组区间$[l,r]$内与$x$异或的最大值。 数据范围：$1\le n\le 50000, \ 1 \le q \le 50000$ ## Solution 要求的是最大值，可以从二进制高位到低位处理，如果对第$i$位，$[l,r]$区间内存在数使其与$x$在这一位不同，那么异或的结果中第$i$位就是1，否则为0。同时每次选择后，区间$[l,r]$中要删除前缀不匹配的数。 因为在处理过程中，一直要保持前缀匹配，所以可以想到用Trie来做。Naive的想法是在Trie的每个结点用set保存一下有哪些下标访问到了。从根结点出发每次选择0或者1的子结点，如果这个子结点中出现了$[l,r]$的数，就是可以选择的，贪心选择就可以了。 但是这样肯定是会TLE的，正解是用可持久化Trie。每个结点只需要记录访问到的次数。那么该结点包含区间$[l,r]$内数的个数就是时间点$r$的值减去时间点$l$的值。 <details><summary>Code</summary> ```c++ #include <bits/stdc++.h> using namespace std; // Persistent Trie template <int N = 26, int B = 'a', typename T = int> struct PTrie { int n; vector<array<int, N>> D; vector<T> V; vector<int> Rt; function<T(T, T)> al; PTrie(function<T(T, T)> al = plus<T>()): n(1), D(1), V(1), Rt(1, 0), al(al) {} template <typename Seq> void insert(const Seq &S, T x, T m = T()) { static const function<int(int, int)> ins_ = [&](int o, size_t i) { int no = n++, tmp; D.emplace_back(D[o]), V.push_back(V[o]); V[no] = al(V[no], i == S.size() ? x : m); if (i < S.size()) { tmp = ins_(D[no].at(S[i] - B), i + 1), D[no][S[i] - B] = tmp; } return no; }; Rt.push_back(ins_(Rt.back(), 0)); } template <typename Seq> pair<bool, T> query(const Seq &S, int t = -1) { int u = t < 0 ? Rt.back() : Rt.at(t); for (auto x : S) { u = D[u][x - B]; if (!u) return {false, T()}; } return {true, V[u]}; } }; // 51Nod. 1295 PTrie<2, '0', int> tr; string query(int l, int r, const string &S, size_t i) { if (i == S.size()) return ""; int d = 1 - S[i] + '0'; int sum = tr.V[tr.D[r][d]] - tr.V[tr.D[l][d]]; if (sum > 0) return "1" + query(tr.D[l][d], tr.D[r][d], S, i + 1); else return "0" + query(tr.D[l][1 - d], tr.D[r][1 - d], S, i + 1); } int main() { int n, q; scanf("%d%d", &n, &q); auto tostr = [](int x) { return bitset<32>(x).to_string(); }; for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); tr.insert(tostr(x), 1, 1); } while (q--) { int x, l, r; scanf("%d%d%d", &x, &l, &r); l++, r++; auto S = query(tr.Rt[l - 1], tr.Rt[r], tostr(x), 0); printf("%d\n", stoi(S, NULL, 2)); } return 0; } ``` </details> ## Tips 类似这样的区间询问的问题，如果线段树等数据结构无法解决。一种思路是转离线询问用莫队算法做，另一种是可持久化数据结构(如果区间的结果可以用前缀和减法求的话)。 コメント
コメント
コメントを投稿