老瞎眼 pk 小鲜肉

老瞎眼 pk 小鲜肉

利用异或前缀和，离线处理。

我们定义为值为的异或前缀和最后一次出现在上。

我们通过枚举有区间，然后把异或相同的区间长度存在上，

之后我们只要在区间查询区间最小值即为答案了。

#include <bits/stdc++.h>
#define mid (l + r >> 1)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define ls rt << 1
#define rs rt << 1 | 1

using namespace std;

typedef pair<int, int> pii;

const int N = 2e6 + 10, inf = 0x3f3f3f3f;

int tree[N], a[N], pos[N], ans[N], n, m;

vector<pii> query[N];

void build(int rt, int l, int r) {
  if (l == r) {
    tree[rt] = inf;
    return ;
  }
  build(lson);
  build(rson);
  tree[rt] = min(tree[ls], tree[rs]);
}

int query_min(int rt, int l, int r, int L, int R) {
  if (l >= L && r <= R) {
    return tree[rt];
  }
  int ans = inf;
  if (L <= mid) ans = query_min(lson, L, R);
  if (R > mid)  ans = min(ans, query_min(rson, L, R));
  return ans;
}

void update(int rt, int l, int r, int L, int R, int value) {
  if (l >= L && r <= R) {
    tree[rt] = value;
    return ;
  }
  if (L <= mid) update(lson, L, R, value);
  if (R > mid)  update(rson, L, R, value);
  tree[rt] = min(tree[ls], tree[rs]);
}

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    a[i] = a[i - 1] ^ x;
  }
  for (int i = 1; i <= m; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    query[r].push_back(make_pair(l, i));
  }
  build(1, 1, n);
  for (int i = 1; i <= n; i++) {
    pos[a[i - 1]] = i;
    int pre = pos[a[i]];
    if (pre) {
      update(1, 1, n, pre, pre, i - pre + 1);
    }
    for (auto it : query[i]) {
      ans[it.second] = query_min(1, 1, n, it.first, i);
    }
  }
  for (int i = 1; i <= m; i++) {
    printf("%d\n", ans[i] == inf ? -1 : ans[i]);
  }
  return 0;
}