#include<bits/stdc++.h>
using namespace std;
const int N=2e5+9,M=N*200;
int root[N];
int cnt;
int ls[M],rs[M],val[M],lz[M];
void pushup(int p)
{
	val[p]=min(val[ls[p]],val[rs[p]]);
}
void pushdown(int p)
{
	if(!lz[p])
	return;
	if(!ls[p])
	ls[p]=++cnt;
	if(!rs[p])
	rs[p]=++cnt;
	val[ls[p]]+=lz[p];
	lz[ls[p]]+=lz[p];
	val[rs[p]]+=lz[p];
	lz[rs[p]]+=lz[p];
	lz[p]=0;
}
void update(int &p,int l,int r,int L,int R,int k)
{
	if(!p)
	p=++cnt;
	if(L<=l&&r<=R)
	{
		val[p]+=k;
		lz[p]+=k;
		return;
	}
	int mid=(l+r)/2;
	pushdown(p);
	if(L<=mid)
	update(ls[p],l,mid,L,R,k);
	if(R>mid)
	update(rs[p],mid+1,r,L,R,k);
	pushup(p);
}
int n;
int gtl(int p,int l,int r,int L,int R)
{
	if(L>R)
	return 0;
	int mid=(l+r)/2;
	if(L<=l&&r<=R)
	{
		if(val[p])
		return 0;
		if(!p||l==r)
		return r;
		pushdown(p);
		if(!val[rs[p]])
		return gtl(rs[p],mid+1,r,L,R);
		else
		return gtl(ls[p],l,mid,L,R);
	}
	pushdown(p);
	if(R>mid)
	{
		int d=gtl(rs[p],mid+1,r,L,R);
		if(d)
		return d;
	}
	return gtl(ls[p],l,mid,L,R);
}
int gtr(int p,int l,int r,int L,int R)
{
	int mid=(l+r)/2;
	if(L<=l&&r<=R)
	{
		if(val[p])
		return n;
		if(!p||l==r)
		return l;
		pushdown(p);
		if(!val[ls[p]])
		return gtr(ls[p],l,mid,L,R);
		else
		return gtr(rs[p],mid+1,r,L,R);
	}
	pushdown(p);
	if(L<=mid)
	{
		int d=gtr(ls[p],l,mid,L,R);
		if(d!=n)
		return d;
	}
	return gtr(rs[p],mid+1,r,L,R);
}
set<int>lf[N],rf[N];
struct xdt
{
	struct Node
	{
		int val,l,r;
	}d[N<<2];
	void pushup(int p)
	{
		d[p].val=d[p<<1].val+d[p<<1|1].val;
		int k=min(d[p<<1].l,d[p<<1|1].r);
		d[p].val+=k;
		d[p].r=d[p<<1].r+d[p<<1|1].r-k;
		d[p].l=d[p<<1|1].l+d[p<<1].l-k;
	}
	void update(int p,int l,int r,int x,int k)
	{
		if(l==r)
		{
			if(k==0)
			d[p]={0,0,0};
			if(k==1)
			d[p]={0,1,0};
			if(k==-1)
			d[p]={0,0,1};
			return;
		}
		int mid=(l+r)/2;
		if(x<=mid)
		update(p<<1,l,mid,x,k);
		else
		update(p<<1|1,mid+1,r,x,k);
		pushup(p);
	}
}T;
int ans;
void addl(int col,int x)
{
	if(rf[col].lower_bound(x)!=rf[col].end())
	{
		int y=*rf[col].lower_bound(x);
		update(root[col],1,n,x,y-1,1);
		rf[col].erase(y);
		T.update(1,1,n,y,0);
		ans++;
		return;
	}
	int l=gtl(root[col],1,n,1,x-1)+1;
	if(l==x)
	{
		lf[col].insert(x);
		T.update(1,1,n,x,1);
		return;
	}
	update(root[col],1,n,l,x-1,-1);
	lf[col].insert(l);
	T.update(1,1,n,l,1);
}
void addr(int col,int x)
{
	if(lf[col].lower_bound(x)!=lf[col].begin())
	{
		int y=*--lf[col].lower_bound(x);
		update(root[col],1,n,y,x-1,1);
		lf[col].erase(y);
		T.update(1,1,n,y,0);
		ans++;
		return;
	}
	int r=gtr(root[col],1,n,x,n);
	if(r==x)
	{
		rf[col].insert(x);
		T.update(1,1,n,x,-1);
		return;
	}
	update(root[col],1,n,x+1,r,-1);
	rf[col].insert(r);
	T.update(1,1,n,r,-1);
}
void del(int col,int x)
{
	if(lf[col].find(x)!=lf[col].end())
	{
		lf[col].erase(x);
		T.update(1,1,n,x,0);
		return;
	}
	int r=gtr(root[col],1,n,x,n);
	update(root[col],1,n,x,r-1,-1);
	ans--;
	addr(col,r);
}
void der(int col,int x)
{
	if(rf[col].find(x)!=rf[col].end())
	{
		rf[col].erase(x);
		T.update(1,1,n,x,0);
		return;
	}
	int l=gtl(root[col],1,n,1,x-1)+1;
	update(root[col],1,n,l,x-1,-1);
	ans--;
	addl(col,l);
}
int q;
int a[N],b[N],p[N];
mt19937 rd(time(0));
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=1;i<=n;i++)
	cin>>b[i];
	for(int i=1;i<=n;i++)
	p[i]=i;
	shuffle(p+1,p+n+1,rd);
	for(int i=1;i<=n;i++)
	{
		if(b[p[i]]==0)
		addl(a[p[i]],p[i]);
		else
		addr(a[p[i]],p[i]);
	}
	cout<<ans+T.d[1].val<<'\n';
	while(q--)
	{
		int x,w,t;
		cin>>x>>w>>t;
		if(b[x]==0)
		del(a[x],x);
		else
		der(a[x],x);
		a[x]=w;
		b[x]=t;
		if(b[x]==0)
		addl(a[x],x);
		else
		addr(a[x],x);
		cout<<ans+T.d[1].val<<'\n';
	}
	return 0;
}
/*
11 1
1 0 0 1 1 1 0 0 0 0 1
1 2 1 1 1 2 1 1 2 2 2
2 0 2

*/