Submission #2211421

---

Source Code Expand

#include <bits/stdc++.h>
#include <climits>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define srep(i, begin, end) for (__typeof(end) i = begin; i != end; i++)
#define si(x) int x = scanInt();
#define sll(x) LL x = scanLong();
#define sci(x) int x; scanf("%d", &x);
#define scll(x) LL x; scanf("%lld", &x);
#define pi(x) printf("%d ", x)
#define pll(x) printf("%lld ", x)
#define ps(x) printf("%s", x)
#define nl printf("\n")
#define clr(a) memset(a, 0, sizeof(a))
#define PB push_back
#define MP make_pair
using namespace std;
typedef unsigned int UI; // 32 bit integer
typedef long int LI; // 32 bit integer
typedef unsigned long int ULI; // 32 bit unsigned integer
typedef long long int LL; // 64 bit integer
typedef unsigned long long int  ULL; // 64 bit unsigned integer
typedef long double LD;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
LL mod = 1e9+7;

/* Fast I/O */
inline int scanInt() {
	int n = 0;
	char ch = getchar();
	int sign = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-')	sign = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		n = (n<<1)+(n<<3)+(int)(ch-'0');
		ch = getchar();
	}
	return n*sign;
}

inline LL scanLong() {
	LL n = 0;
	char ch = getchar();
	LL sign = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-')	sign = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		n = (n<<1)+(n<<3)+(LL)(ch-'0');
		ch = getchar();
	}
	return n*sign;
}

const LL MAXN = 2e5+10;	
LL arr[MAXN], cnt[MAXN], present[MAXN];

int main() {
	sll(n); sll(m);
	rep(i, 0, n) {
		arr[i] = scanLong();
		cnt[arr[i]]++;
	}
	rep(i, 1, n+1) {
		LL low = max(0ll, i - cnt[i]);
		rep(j, low, i)	present[j]++;
	}
	LL ans = 0;
	rep(i, 0, n-1)	if(!present[i])	ans++;
	rep(i, 0, m) {
		sll(x); sll(y); x--;
		if(y != arr[x]) {
			if(y > cnt[y]) {
				if(present[y-cnt[y]-1] == 0)	ans--;
				present[y-cnt[y]-1]++;
			}
			if(arr[x] >= cnt[arr[x]]) {
				if(present[arr[x]-cnt[arr[x]]] == 1)	ans++;
				present[arr[x]-cnt[arr[x]]]--;
			}
			cnt[arr[x]]--;
			cnt[y]++;
			arr[x] = y;
		}
		pll(ans); nl;
	}
}

Submission Info

Judge Result