题解 | #区间异或#
区间异或
https://ac.nowcoder.com/acm/problem/214363
考虑一个性质A xor B xor B = A
先记录a数组前缀异或值
注意数据量为3e3
可以开一个vector保存一下所以区间异或值,对区间排序按异或值
最后先将查询值保存,排序,从最大查询值大开始将区间存入set,保存答案即可。
#include<bits/stdc++.h>
#define rep(a,b) for( int i= a; i <= b ; ++i)
#define rep2(a,b) for( int j=a; j <= b ; ++j)
#define pre(a,b) for( int k= a; k >= b ; --k)
#define bn begin()
#define ed end()
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define cn(a) cin>>a
#define pt(a) cout<<a
#define ptn(a) cout<<a<<'\n'
#define ft first
#define sd second
#define met(a,b) memset(a,b,sizeof a)
#define pk(a) push_back(a)
#define pp pop()
#define lcm(a,b) a/(gcd(a,b)*b
#define it(a) insert(a)
#define gt greater<int>
#pragma GCC optimize(2)
using ll = long long;
using namespace std;
const int mod = 1610612741;
const int INF = 0x3f3f3f3f;
inline int read()
{
int s = 0, x = 1;
char ch = getchar();
while (ch < '0' || ch>'9') { if (ch == '-') x = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); }
return s * x;
}
const int N = 3e3 + 5;
int n, m, a[N];
vector<pair<int, int>>v;
set<int>segment;
int sm[N], ans[200005];
void solve() {
n = read(), m = read();
rep(1, n) {
a[i] = read();
sm[i] = sm[i-1]^a[i];
}
rep(1, n) {
rep2(i, n) {
v.push_back({ sm[j] ^ sm[i - 1],j - i + 1 });
}
}
sort(v.bn, v.ed);
reverse(v.bn, v.ed);
vector<pair<int, int>>b;
rep(1, m)b.push_back({ read(),i });
sort(b.bn, b.ed);
reverse(b.bn, b.ed);
int idx = 0;
for (auto& [u, y] : b) {
while (idx < v.size() && v[idx].ft >= u) {
segment.insert(v[idx].sd);
idx++;
}
if (segment.empty())
ans[y] = -1;
else ans[y] = *(segment.bn);
}
rep(1, m)ptn(ans[i]);
}
int main(void) {
solve();
return 0;
}