题解 | #区间异或#

区间异或

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;
}
全部评论

相关推荐

牛客868257804号:九个中铁八个中建
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务