BattleCows

    1#include <bits/stdc++.h>
    2using namespace std;
    3typedef long long ll;
    4const int inf = 1e9;
    5const long long INF = 1e17; //❄️
    6#define int long long
    7struct Node {
    8    ll xr;
    9};
    10int N;
    11vector<Node> seg;
    12vector<ll> A;
    13 
    14Node mergeNode(const Node &L, const Node &R) {
    15    Node res;
    16    res.xr = L.xr ^ R.xr;
    17    return res;
    18}
    19 
    20void build(int idx, int l, int r) {
    21    if (l == r) {
    22        seg[idx].xr = A[l];
    23        return;
    24    }
    25    int mid = (l + r) >> 1;
    26    build(idx << 1, l, mid);
    27    build(idx << 1 | 1, mid + 1, r);
    28    seg[idx] = mergeNode(seg[idx << 1], seg[idx << 1 | 1]);
    29}
    30 
    31void update(int idx, int l, int r, int pos, ll val) {
    32    if (l == r) {
    33        seg[idx].xr = val;
    34        return;
    35    }
    36    int mid = (l + r) >> 1;
    37    if (pos <= mid) update(idx << 1, l, mid, pos, val);
    38    else update(idx << 1 | 1, mid + 1, r, pos, val);
    39    seg[idx] = mergeNode(seg[idx << 1], seg[idx << 1 | 1]);
    40}
    41 
    42int queryAbove(int pos) {
    43    int idx = 1, l = 0, r = N - 1;
    44    int res = 0;
    45 
    46    while (l < r) {
    47        int mid = (l + r) >> 1;
    48        if (pos <= mid) {
    49            int leftX = seg[idx << 1].xr;
    50            int rightX = seg[idx << 1 | 1].xr;
    51            if (rightX > leftX) {
    52                res += (r - mid);
    53            }
    54            idx = idx << 1;
    55            r = mid;
    56        } else {
    57            int leftX = seg[idx << 1].xr;
    58            int rightX = seg[idx << 1 | 1].xr;
    59            if (leftX >= rightX) {
    60                res += (mid - l + 1);
    61            }
    62            idx = idx << 1 | 1;
    63            l = mid + 1;
    64        }
    65    }
    66    return res;
    67}
    68void solve() {
    69    int n, q;
    70    cin >> n >> q;
    71    N = 1 << n;
    72 
    73    A.resize(N);
    74    for (int i = 0; i < N; i++) cin >> A[i];
    75 
    76    seg.assign(4 * N, {0});
    77    build(1, 0, N - 1);
    78 
    79    while (q--) {
    80        int b;
    81        int c;
    82        cin >> b >> c;
    83        --b;
    84 
    85        int old = A[b];
    86        A[b] = c;
    87        update(1, 0, N - 1, b, c);
    88 
    89        cout << queryAbove(b) << '\n';
    90 
    91        A[b] = old;
    92        update(1, 0, N - 1, b, old);
    93    }
    94}
    95signed main() {
    96    ios::sync_with_stdio(0); cin.tie(0); 
    97    int t; cin >> t;
    98    while (t--) {
    99         solve();
    100    }
    101    return 0;
    102}