#include <bits/stdc++.h>

using namespace std;

const int N = 4e5 + 5;

int n, m, a[N], b[N], c1[1 << 20], c2[1 << 20];

void pushup(int k) {
    c1[k] = c1[k << 1], c2[k] = c2[k << 1 | 1];
    if (c2[k << 1] > c1[k << 1 | 1]) c2[k] += c2[k << 1] - c1[k << 1 | 1];
    else c1[k] += c1[k << 1 | 1] - c2[k << 1];
}

void build(int k, int l, int r) {
    if (l == r) {
        if (b[k] == 0) c2[k] = 1;
        else c1[k] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
    pushup(k);
}

void modify(int k, int l, int r, int x, int y) {
    if (l == r) {
        c1[k] = c2[k] = 0;
        if (y == -1) c2[k] = 1;
        else if (y == 1) c1[k] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) modify(k << 1, l, mid, x, y);
    else modify(k << 1 | 1, mid + 1, r, x, y);
    pushup(k);
}

struct Info {
    int s, ls, rs, lm, rm;
} p[N << 6];

Info operator + (Info x, Info y) {
    Info res;
    res.s = x.s + y.s;
    res.lm = max(x.lm, x.s + y.lm);
    res.rm = max(y.rm, -y.s + x.rm);
    return res;
}

int rt[N], tot;

void Modify(int &k, int l, int r, int x, int y) {
    if (!k) k = ++tot;
    if (l == r) {
        p[k].s = y;
        p[k].lm = max(y, 0);
        p[k].rm = max(-y, 0);
        return;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) Modify(p[k].ls, l, mid, x, y);
    else Modify(p[k].rs, mid + 1, r, x, y);
    int tl = p[k].ls, tr = p[k].rs;
    p[k] = p[p[k].ls] + p[p[k].rs];
    p[k].ls = tl, p[k].rs = tr;
}

Info Query(int k, int l, int r, int x, int y) {
    if (!k || l > y || r < x) return p[0];
    if (l >= x && r <= y) return p[k];
    int mid = (l + r) >> 1;
    return Query(p[k].ls, l, mid, x, y) + Query(p[k].rs, mid + 1, r, x, y);
}

vector< pair<int, int> > glo;
vector< array<int, 3> > pnt;

void dfs(int k, int l, int r, int x, int y) {
    if (!k || l > y || r < x) return;
    if (l >= x && r <= y) {
        pnt.push_back({k, l, r});
        return;
    }
    int mid = (l + r) >> 1;
    dfs(p[k].ls, l, mid, x, y), dfs(p[k].rs, mid + 1, r, x, y);
}

int getLst(int k, int l, int r, int v) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (p[k].rs && p[p[k].rs].rm >= v) return getLst(p[k].rs, mid + 1, r, v);
    return getLst(p[k].ls, l, mid, v - p[p[k].rs].s);
}

int findLst(int k, int l, int r, int y, int val) {
    pnt.clear(), dfs(k, 1, n, 1, y), reverse(pnt.begin(), pnt.end());
    for (auto [_p, _q, _r] : pnt) {
        if (p[_p].rm >= val) return getLst(_p, _q, _r, val);
        val -= p[_p].s;
    }
    return -1;
}

int getNxt(int k, int l, int r, int v) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (p[k].ls && p[p[k].ls].lm >= v) return getNxt(p[k].ls, l, mid, v);
    return getNxt(p[k].rs, mid + 1, r, v + p[p[k].ls].s);
}

int findNxt(int k, int l, int r, int x, int val) {
    pnt.clear(), dfs(k, 1, n, x, n);
    for (auto [_p, _q, _r] : pnt) {
        if (p[_p].lm >= val) return getNxt(_p, _q, _r, val);
        val -= p[_p].s;
    }
    return -1;
}

void test(int x) {
    Info L = Query(rt[a[x]], 1, n, 1, x - 1), R = Query(rt[a[x]], 1, n, x + 1, n);
    if (b[x] == 0) {
        if (R.lm != 0) {
            glo.push_back({x, 1});
            if (L.rm >= R.lm) {
                glo.push_back({findLst(rt[a[x]], 1, n, x - 1, R.lm), 0});
            } else {
                glo.push_back({findNxt(rt[a[x]], 1, n, x + 1, L.rm + 1), 1});
            }
        } else {
            glo.push_back({x, 0});
        }
    } else {
        if (L.rm != 0) {
            glo.push_back({x, 1});
            if (R.lm >= L.rm) {
                glo.push_back({findNxt(rt[a[x]], 1, n, x + 1, L.rm), 0});
            } else {
                glo.push_back({findLst(rt[a[x]], 1, n, x - 1, R.lm + 1), 1});
            }
        } else {
            glo.push_back({x, 0});
        }
    }
}

void erase(int x) {
    Modify(rt[a[x]], 1, n, x, 0);
    glo.clear(), test(x);
    for (auto [x, y] : glo) modify(1, 1, n, x, (y != 0 ? (b[x] == 0 ? -1 : 1) : 0));
}

void insert(int x) {
    glo.clear(), test(x);
    Modify(rt[a[x]], 1, n, x, b[x] == 0 ? -1 : 1);
    for (auto [x, y] : glo) modify(1, 1, n, x, (y != 0 ? 0 : (b[x] == 0 ? -1 : 1)));
}

signed main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
    build(1, 1, n);
    for (int i = 1; i <= n; ++i) insert(i);
    printf("%d\n", (n - c1[1] - c2[1]) / 2);
    while (m--) {
        int p, q, r; scanf("%d%d%d", &p, &q, &r);
        erase(p);
        a[p] = q, b[p] = r;
        insert(p);
        printf("%d\n", (n - c1[1] - c2[1]) / 2);
    }
    return 0;
}