Submission #5021272

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned ui;
typedef unsigned long long ul;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef pair<bool, bool> pbb;
typedef vector<int> vi;
#define pb push_back
#define fi first
#define se second
#define mid ((l + r) >> 1)
#define ls (i << 1)
#define rs (i << 1 | 1)
#define enum(i, j, k) for(int i = j; i <= (k); i ++)
#define open(i, j, k) for(int i = j; i <  (k); i ++)
#define dec(i, j, k)  for(int i = j; i >= (k); i --)
#define ae(x) for(node *p = h[x]; p; p = p->nxt)
#define fill(x, k) memset(x, k, sizeof x)
#define copy(x, y) memcpy(x, y, sizeof x)
#define fio(x) freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);
template <class T> bool chkmin(T &x, T y)
{ return y < x ? (x = y , true) : false; }
template <class T> bool chkmax(T &x, T y)
{ return y > x ? (x = y , true) : false; }
void __init()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(16);
    srand(time(0) ^ ui(ul(new char)));
}
/* default code ends here */
const int maxn = 2e5 + 10;
int n, m, ans;
int a[maxn];
map<int, int> mp;
void add(int x)
{
	auto it = mp.find(x);
	if(it != mp.end())
	{
		auto it2 = -- mp.lower_bound(x);
		if((*it).fi - (*it2).fi <= (*it).se)
			ans ++;
		(*it).se ++;
	}
	else
	{
		auto it2 = mp.upper_bound(x), it3 = it2 --;
		int d = (*it3).fi - (*it2).fi - (*it3).se;
		if(d < 0) ans += d;
		d = (*it3).fi - x - (*it3).se;
		if(d < 0) ans -= d;
		d = x - (*it2).fi - 1;
		if(d < 0) ans -= d;
		mp[x] = 1;
	}
}
void del(int x)
{
	auto it = mp.find(x);
	if((*it).se != 1)
	{
		auto it2 = -- mp.lower_bound(x);
		if((*it).fi - (*it2).fi < (*it).se)
			ans --;
		(*it).se --;
	}
	else
	{
		mp.erase(it);
		auto it2 = mp.upper_bound(x), it3 = it2 --;
		int d = (*it3).fi - x - (*it3).se;
		if(d < 0) ans += d;
		d = x - (*it2).fi - 1;
		if(d < 0) ans += d;
		d = (*it3).fi - (*it2).fi - (*it3).se;
		if(d < 0) ans -= d;
	}
}
int main()
{
	__init();
	cin >> n >> m;
	mp[0] = 1;
	mp[n + 1] = 1;
	enum(i, 1, n)
		cin >> a[i];
	enum(i, 1, n)
		add(a[i]);
	int x, y;
	while(m --)
	{
		cin >> x >> y;
		del(a[x]);
		a[x] = y;
		add(a[x]);
		cout << ans << '\n';
	}
	return 0;
}

Submission Info

Judge Result