q3LPfX - Online C++ Compiler & Debugging Tool

#include <bits/stdc++.h>
using namespace std;

static const int B = 20;

struct PB {
  int base[B]{};
  int pos[B]{};
};

static inline void ins(PB &pb, int x, int idx) {
  int v = x, p = idx;
  for (int b = B - 1; b >= 0; --b) {
    if (((v >> b) & 1) == 0)
      continue;
    if (pb.base[b] == 0) {
      pb.base[b] = v;
      pb.pos[b] = p;
      return;
    }
    if (pb.pos[b] < p) {
      swap(v, pb.base[b]);
      swap(p, pb.pos[b]);
    }
    v ^= pb.base[b];
  }
}

static inline int rk(const PB &pb, int l) {
  int r = 0;
  for (int b = 0; b < B; ++b)
    if (pb.base[b] && pb.pos[b] >= l)
      ++r;
  return r;
}

struct TB {
  int v[B]{};
  int piv[B];
  int len = 0;

  void clear() {
    memset(v, 0, sizeof(v));
    len = 0;
  }

  void ins(int x) {
    for (int b = B - 1; b >= 0; --b) {
      if (((x >> b) & 1) == 0)
        continue;
      if (v[b] == 0) {
        v[b] = x;
        return;
      }
      x ^= v[b];
    }
  }

  void fin() {
    len = 0;
    for (int b = B - 1; b >= 0; --b)
      if (v[b])
        piv[len++] = b;
  }

  long long cnt_from(int idx, int offset, int K) const {
    if (idx == len)
      return (offset <= K) ? 1 : 0;
    int b = piv[idx];
    int half = 1 << (len - idx - 1);
    int kb = (K >> b) & 1;
    int ob = (offset >> b) & 1;
    if (kb == 0) {
      int next = ob ? (offset ^ v[b]) : offset;
      return cnt_from(idx + 1, next, K);
    } else {
      int next = ob ? offset : (offset ^ v[b]);
      return (long long)half + cnt_from(idx + 1, next, K);
    }
  }

  long long cnt_leq(int K) const {
    if (K < 0)
      return 0;
    return cnt_from(0, 0, K);
  }

  int kth(long long t) const {
    int offset = 0;
    for (int idx = 0; idx < len; ++idx) {
      int b = piv[idx];
      int half = 1 << (len - idx - 1);
      int ob = (offset >> b) & 1;
      if (t <= half) {
        if (ob)
          offset ^= v[b];
      } else {
        t -= half;
        if (!ob)
          offset ^= v[b];
      }
    }
    return offset;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t;
  cin >> t;
  while (t--) {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
      cin >> a[i];

    vector<PB> pref(n + 1);
    for (int i = 1; i <= n; ++i) {
      pref[i] = pref[i - 1];
      ins(pref[i], a[i], i);
    }

    auto build = [&](int l, int e) {
      TB tb;
      tb.clear();
      const PB &pb = pref[e];
      for (int b = B - 1; b >= 0; --b) {
        if (pb.base[b] && pb.pos[b] >= l) {
          tb.ins(pb.base[b]);
        }
      }
      tb.fin();
      return tb;
    };

    auto firstpos = [&](int l, int r, int need_rank) {
      int lo = l, hi = r;
      while (lo < hi) {
        int mid = (lo + hi) >> 1;
        if (rk(pref[mid], l) >= need_rank)
          hi = mid;
        else
          lo = mid + 1;
      }
      return lo;
    };

    while (q--) {
      int l, r;
      cin >> l >> r;

      int d = rk(pref[r], l);

      vector<int> s(d + 1);
      int last = l;
      for (int k = 1; k <= d; ++k) {
        int sk = firstpos(l, r, k);
        s[k] = sk;
        last = sk;
      }

      bool ok = true;
      int prev = -1;
      int seg_start = l;

      for (int k = 0; k <= d; ++k) {
        int seg_end = (k < d ? s[k + 1] - 1 : r);
        int L = seg_end - seg_start + 1;
        if (L <= 0)
          continue;

        TB tb = build(l, seg_end);
        int sz = 1 << tb.len;
        long long c = tb.cnt_leq(prev);
        if (c + L > sz) {
          ok = false;
          break;
        }
        int t = (int)(c + L);
        prev = tb.kth(t);

        seg_start = seg_end + 1;
      }

      cout << (ok ? "YES\n" : "NO\n");
    }
  }
  return 0;
}