MINXORSEG
评分 3087, tourist 也没做出
给你长度n数组, q个询问,每次问区间[l,r]中任意两个数的异或的最小值
范围
n 2e5
q 2e5
ai 2^30
3s
400MB
题解
离线, 按查询的右端点排序
简单的扫描加入 是n方?
x=a[l]^a[r]
假设x最高位1在p位,那么高于p的bit,a[l]和a[r]一样
如果[l..r] 之间有同样的高于p的bit和它们一样的t,那么(l,r)这一对一定不是最小值,因为 (l,t) 或 (t,r) 比它小
如果区间有3个高w位一样,那么答案至少是高w位为0, 所以答案最小的只存两个高w一样,或者存在两个相等的数
这个观察很神奇,也就是说如果ai和aj高w位相同,那么要让它们可能是答案的必要条件是,它们中间没有高w位和它们相同的
换句话说, a[i]如果和它前面某个a[j]高w相同,贡献了最小xor,那么a[i]的w相同的前面最近的就是a[j]
所以直接记录每个数前面和它高0,1,2,3..位相同的最近的下标即可, 这可以简单的排序记录
最后扫描+fenwick一下
其中把每对的左点为index,异或和为值,做后缀min fenwick 就可以了, 这样每次询问就是[l… 中的最小值
代码
https://www.codechef.com/viewsolution/67421139
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
const ll INF = 0x3f3f3f3f3f3f;
ll read(){ll r;scanf("%lld",&r);return r;}
ll a[200010];
int idxs[200010];
struct fenwick_tree {
vector<ll> bit;
int n;
fenwick_tree(int n) : n(n) {
bit = vector<ll> (n + 1, INF);
}
void update(int u, ll v) {
for (u++; u > 0; u -= u & -u) bit[u] = min(bit[u], v);
}
int query(int u) {
ll r = INF;
for (u++; u <= n; u += u & -u) r = min(r, bit[u]);
return r;
}
};
int main() {
int n = read();
int q = read();
vector<vector<int>> lst(n);
vector<vector<pair<int, int>>> que(n);
rep(i,0,n) a[i] = read();
rep(b,0,30+1) {
iota(idxs,idxs+n,0);
sort(idxs,idxs+n,[=](int i,int j){return make_pair((a[i] >> b),i) < make_pair((a[j] >> b),j); });
rep(i,1,n) {
if ((a[idxs[i]] >> b) == (a[idxs[i-1]] >> b)) {
lst[idxs[i]].push_back(idxs[i-1]);
}
}
}
vector<int> ans(q);
rep(i,0,q) {
int l = read() - 1;
int r = read() - 1;
que[r].push_back({l, i});
}
fenwick_tree fen(n);
rep(i, 0, n) {
for (int v : lst[i]) fen.update(v, a[v] ^ a[i]);
for (auto [l, ind] : que[i]) ans[ind] = fen.query(l);
}
for(auto v:ans) printf("%d\n", v);
}
|
代码
总结
MINXORSEG
这个观察最小的可能贡献很厉害啊, 应该属于xor的一个神奇的知识点了?
另一个就是, 这种非统计的, 最大最小也是可以从”可能贡献”的角度去思考,这个我没有思路过,学到了
fenwick这个还有后缀写法,不需要做颠倒原数组的动作
参考
官方