Miguel și Baza 2

#include <bits/stdc++.h>

using namespace std;
using int64 = long long;

void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}

const int MAXN = 1e5 + 1;
int a[MAXN], p2[18];

int64 gauss(int64 x) {
  return (x * (x + 1)) >> 1;
}

void solve() {
  int N, Q;
  cin >> N >> Q;
  for (int i = 1; i <= N; ++i)
    cin >> a[i];
  set<pair<int,int>> S[17];
  p2[0] = 1;
  for (int i = 1; i < 18; ++i)
    p2[i] = p2[i - 1] << 1;
  int64 ans = 0;
  for (int bit = 0; bit < 17; ++bit) {
    int st = 0, dr = 0;
    for (int i = 1; i <= N; ++i)
      if (a[i] & p2[bit]) {
        if (st == 0)
          st = dr = i;
        else dr = i;
      } else
        if (st) {
          S[bit].emplace(st, dr);
          ans += gauss(dr - st + 1) * p2[bit];
          st = 0;
        }
    if (st) {
      S[bit].emplace(st, dr);
      ans += gauss(dr - st + 1) * p2[bit];
    }
  }
  for (int q = 0; q < Q; ++q) {
    int p, x;
    cin >> p >> x;
    for (int bit = 0; bit < 17; ++bit) {
      bool s1 = false, s2 = false;
      if (a[p] & p2[bit])
        s1 = true;
      if (x & p2[bit])
        s2 = true;
      if (s1 == s2)
        continue;
      if (s1) {
        auto it = S[bit].upper_bound(make_pair(p, N + 1));
        --it;
        int l = (*it).first, r = (*it).second;
        S[bit].erase(it);
        ans -= gauss(r - l + 1) * p2[bit];
        if (l <= p - 1) {
          S[bit].emplace(l, p - 1);
          ans += gauss(p - l) * p2[bit];
        }
        if (p + 1 <= r) {
          S[bit].emplace(p + 1, r);
          ans += gauss(r - p) * p2[bit];
        }
      } else {
        auto it = S[bit].upper_bound(make_pair(p, 0));
        if (it != S[bit].end() && (*it).first == p + 1) {
          int l2 = (*it).first, r2 = (*it).second;
          if (it != S[bit].begin()) {
            auto prv = it;
            --prv;
            int l1 = (*prv).first, r1 = (*prv).second;
            S[bit].erase(it);
            if (r1 == p - 1) {
              S[bit].erase(prv);
              ans -= gauss(r1 - l1 + 1) * p2[bit];
              ans -= gauss(r2 - l2 + 1) * p2[bit];
              S[bit].emplace(l1, r2);
              ans += gauss(r2 - l1 + 1) * p2[bit];
            } else {
              ans -= gauss(r2 - l2 + 1) * p2[bit];
              l2 = p;
              S[bit].emplace(l2, r2);
              ans += gauss(r2 - l2 + 1) * p2[bit];
            }
          } else {
            S[bit].erase(it);
            ans -= gauss(r2 - l2 + 1) * p2[bit];
            l2 = p;
            S[bit].emplace(l2, r2);
            ans += gauss(r2 - l2 + 1) * p2[bit];
          }
        } else {
          if (it != S[bit].begin()) {
            --it;
            int l = (*it).first, r = (*it).second;
            if (r == p - 1) {
              S[bit].erase(it);
              ans -= gauss(r - l + 1) * p2[bit];
              r = p;
              S[bit].emplace(l, r);
              ans += gauss(r - l + 1) * p2[bit];
            } else {
              S[bit].emplace(p, p);
              ans += p2[bit];
            }
          } else {
            S[bit].emplace(p, p);
            ans += p2[bit];
          }
        }
      }
    }
    a[p] = x;
    cout << ans << '\n';
  }
}

int main() {
  fastIO();
  solve();
  return 0;
}