Stay.cpp

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cerr << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

vector<int> G[500005],nG[500005],rG[500005],nrG[500005];
multiset<int> mso[500005],msi[500005];
set<pii> st;
const int root=3000;
int seg[2000005],lazy[2000005],deg[500005],diff[500005],rdiff[500005],n;

void modify(int L,int R,int l,int r,int rt,int val)
{
	if(L<=l&&R>=r)
		return lazy[rt]+=val,void();
	int m=l+r>>1;
	if(L<=m) modify(L,R,l,m,rt<<1,val);
	if(R>m) modify(L,R,m+1,r,rt<<1|1,val);
	seg[rt]=0;
	if(lazy[rt<<1]) seg[rt]+=m-l+1;
	else seg[rt]+=seg[rt<<1];
	if(lazy[rt<<1|1]) seg[rt]+=r-m;
	else seg[rt]+=seg[rt<<1|1];
}

int gv()
{
	if(lazy[1]) return 0;
	return n-seg[1];
}

void range(int a,int b,int v)
{
	if(a>=b) return;
	modify(a,b-1,1,n,1,v);
}

void mdfy(int a,int b)
{
	if(deg[a]>=root)
	{
		range(*msi[a].begin(),*mso[a].rbegin(),-1);
		msi[a].erase(msi[a].find(diff[a])),msi[a].insert(b);
		mso[a].erase(mso[a].find(diff[a])),mso[a].insert(b);
		range(*msi[a].begin(),*mso[a].rbegin(),1);
		for(int j:nG[a])
		{
			range(*msi[j].begin(),*mso[j].rbegin(),-1);
			msi[j].erase(msi[j].find(diff[a])),msi[j].insert(b);
			range(*msi[j].begin(),*mso[j].rbegin(),1);
		}
		for(int j:nrG[a])
		{
			range(*msi[j].begin(),*mso[j].rbegin(),-1);
			mso[j].erase(mso[j].find(diff[a])),mso[j].insert(b);
			range(*msi[j].begin(),*mso[j].rbegin(),1);
		}
	}
	else
	{
		for(int j:G[a])
			if(deg[j]>=root)
			{
				range(*msi[j].begin(),*mso[j].rbegin(),-1);
				msi[j].erase(msi[j].find(diff[a])),msi[j].insert(b);
				range(*msi[j].begin(),*mso[j].rbegin(),1);
			}
			else
				range(diff[a],diff[j],-1),range(b,diff[j],1);
		for(int j:rG[a])
			if(deg[j]>=root)
			{
				range(*msi[j].begin(),*mso[j].rbegin(),-1);
				mso[j].erase(mso[j].find(diff[a])),mso[j].insert(b);
				range(*msi[j].begin(),*mso[j].rbegin(),1);
			}
			else
				range(diff[j],diff[a],-1),range(diff[j],b,1);
	}
	diff[a]=b;
}

int main()
{jizz
	int m,q,a,b;
	cin >> n >> m;
	for(int i=1;i<=n;++i)
		cin >> diff[i],rdiff[diff[i]]=i;
	while(m--)
	{
		cin >> a >> b;
		if(a!=b)
			st.insert(MP(a,b));
	}
	for(auto i:st)
		G[i.F].pb(i.S),rG[i.S].pb(i.F);
	for(int i=1;i<=n;++i)
		deg[i]=G[i].size()+rG[i].size();
	for(int i=1;i<=n;++i)
		if(deg[i]>=root)
		{
			mso[i].insert(diff[i]),msi[i].insert(diff[i]);
			for(int j:G[i])
			{
				mso[i].insert(diff[j]);
				if(deg[j]>=root)
					nG[i].pb(j);
			}
			for(int j:rG[i])
			{
				msi[i].insert(diff[j]);
				if(deg[j]>=root)
					nrG[i].pb(j);
			}
			range(*msi[i].begin(),*mso[i].rbegin(),1);
		}
		else
		{
			for(int j:G[i])
				if(deg[j]<root&&i<j)
					range(diff[i],diff[j],1);
			for(int j:rG[i])
				if(deg[j]<root&&i<j)
					range(diff[j],diff[i],1);
		}
	cout << gv() << "\n";
	for(cin >> q;q--;)
		cin >> a >> b,mdfy(rdiff[a],b),mdfy(rdiff[b],a),swap(rdiff[a],rdiff[b]),cout << gv() << "\n";
}