// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=200005;
int a[maxn],b[maxn],n,zsy,Root[maxn],cnt,ans=0;
namespace seg1{
	int t[maxn<<2],mn[maxn<<2],leaf[maxn];
	void build(int o,int l,int r){ if(l==r)return leaf[l]=o,void(); int mid=(l+r)>>1; build(o<<1,l,mid),build(o<<1|1,mid+1,r); }
	inline void add(int pos,int val){
		int o=leaf[pos]; t[o]+=val,mn[o]+=val,o>>=1;
		for(;o;o>>=1)t[o]+=val,mn[o]=min(mn[o<<1],mn[o<<1|1]+t[o<<1]);
	}
	inline int query(){ return cnt+mn[1]; }
}
namespace seg{
	int tot,ls[maxn<<6],rs[maxn<<6],t[maxn<<6],tag[maxn<<6];
	void update(int &o,int l,int r,int ql,int qr,int val){
		if(ql>qr)return;
		if(!o)o=++tot;
		if(ql<=l&&qr>=r)return t[o]+=val,tag[o]+=val,void();
		int mid=(l+r)>>1;
		if(ql<=mid)update(ls[o],l,mid,ql,qr,val);
		if(qr>mid)update(rs[o],mid+1,r,ql,qr,val);
		t[o]=tag[o]+min(t[ls[o]],t[rs[o]]);
	}
	int find1(int o,int l,int r,int k){
		if(l==r)return l;
		int mid=(l+r)>>1; k-=tag[o];
		return (t[rs[o]]<=k)?find1(rs[o],mid+1,r,k):find1(ls[o],l,mid,k);
	}
	int find2(int o,int l,int r,int k){
		if(l==r)return l;
		int mid=(l+r)>>1; k-=tag[o];
		return (t[ls[o]]<k)?find2(ls[o],l,mid,k):find2(rs[o],mid+1,r,k);
	}
}
set<int>sl[maxn],sr[maxn];
void insert_Left(int col,int pos){
	auto it=sr[col].lower_bound(pos);
	if(it!=sr[col].end()){
		const int x=*it; sr[pos].erase(x);
		seg::update(Root[col],0,n,pos,x-1,1),seg1::add(x,1),--cnt,++ans;
	} else{
		seg::update(Root[col],0,n,pos,n,1);
		const int x=seg::find1(Root[col],0,n,0)+1;
		seg::update(Root[col],0,n,x,n,-1),sl[col].insert(x),seg1::add(x,1);
	}
}
void insert_Right(int col,int pos){
	auto it=sl[col].upper_bound(pos);
	if(it!=sl[col].begin()){
		const int x=*--it; sl[pos].erase(x);
		seg::update(Root[col],0,n,x,pos-1,1),seg1::add(x,-1),++ans;
	} else{
		seg::update(Root[col],0,n,pos,n,-1);
		const int x=seg::find2(Root[col],0,n,0);
		seg::update(Root[col],0,n,x,n,1),sr[col].insert(x),seg1::add(x,-1),++cnt;	
	}
}
void solve(){
	cin>>n>>zsy,seg1::build(1,0,n);
	F(i,1,n)cin>>a[i];
	F(i,1,n)cin>>b[i];
	F(i,1,n)if(!b[i])insert_Left(a[i],i); else insert_Right(a[i],i);
	cout<<ans+seg1::query()<<'\n';
	F(__,1,zsy){
		int pos,x,y; cin>>pos>>x>>y;
		if(!b[pos])insert_Right(a[pos],pos); else insert_Left(a[pos],pos);
		--ans,a[pos]=x,b[pos]=y;
		if(!b[pos])insert_Left(a[pos],pos); else insert_Right(a[pos],pos);
		cout<<ans+seg1::query()<<'\n';
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int zsy=1;
	F(____,1,zsy)solve();
}