【每日一题】老瞎眼 pk 小鲜肉 题解

Desription

链接：https://ac.nowcoder.com/acm/problem/50444
来源：牛客网

老瞎眼有一个长度为 n 的数组 a,为了为难小鲜肉，他准备了 Q 次询问，每次给出 一个区间[L,R],他让小鲜肉寻 找一对 l,r 使L<=l<=r<=R 且 a[l]^a[l+1]^a[l+2]...^a[r]=0,老瞎眼只让他回答r-l+1 最小是多少，若没有符合条件的 l,r 输出”-1”。

Solution

以为是01Trie之类的操作
偷偷看了happy的题解
才知道是离线+线段树
由原式子
转化为前缀和
所以必然有
考虑遍历每个值的时候，记录上一次出现的位置，在这段区间上做操作
区间操作用线段树来维护，查询需要离线。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = (1 << 20) + 100;
typedef long long ll;
vector<pair<int, int> > query[N];
int a[N], sum[N], ans[N], last[N];
struct node {
  int l, r, minz;
}t[N << 2];
void push_up(int rt) {
  t[rt].minz = min(t[rt << 1].minz, t[rt << 1 | 1].minz);
}
void build(int rt, int l, int r) {
  t[rt].l = l, t[rt].r = r;
  if(l == r) {
    t[rt].minz = 1e9;
    return ;
  }
  int mid = l + r >> 1;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
  push_up(rt);
}
void update(int rt, int ql, int qr, int val) {
  if(ql <= t[rt].l && qr >= t[rt].r) {
    t[rt].minz = val;
    return ;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  if(qr <= mid) {
    update(rt << 1, ql, qr, val);
  } else if(ql > mid) {
    update(rt << 1 | 1, ql, qr, val);
  } else {
    update(rt << 1, ql, mid, val);
    update(rt << 1 | 1, mid + 1, qr, val);
  }
  push_up(rt);
}
int query_min(int rt, int ql, int qr) {
  if(ql <= t[rt].l && qr >= t[rt].r) {
    return t[rt].minz;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  if(qr <= mid) {
    return query_min(rt << 1, ql, qr);
  } else if(ql > mid) {
    return query_min(rt << 1 | 1, ql, qr);
  } else {
    return min(query_min(rt << 1, ql, mid), query_min(rt << 1 | 1, mid + 1, qr));
  }
}
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    int n, m; cin >> n >> m;
  for(int i = 1; i <= n; i++) cin >> a[i], sum[i] = sum[i - 1] ^ a[i];
  for(int i = 1; i <= m; i++) {
    int l, r; cin >> l >> r;
    query[r].push_back({l, i});
  }
  build(1, 1, n); 
  for(int i = 1; i <= m; i++) ans[i] = 1e9;
  for(int i = 1; i <= n; i++) {
    last[sum[i - 1]] = i;
    int pre = last[sum[i]]; // 找到上一个位置
    if(pre) {
      update(1, pre, pre, i - pre + 1);
    }
    for(auto &x : query[i]) { //该点为终点的查询
      ans[x.second] = query_min(1, x.first, i); 
    }
  }
  for(int i = 1; i <= m; i++) {
    cout << (ans[i] == 1e9 ? -1 : ans[i]) << " \n";
  }
  return 0;
}