2024-11-05-solution-p9596

一眼题。

由于是冒泡排序，所以我还是能比较自然的联想到排名。考虑每一轮每个数都会像最终的位置靠近一格，所以答案就是 $\max i-rank_i$。直接权值线段树随便维护维护就行了吧。

// Problem: P9596 [JOI Open 2018] 冒泡排序 2
// URL: https://www.luogu.com.cn/problem/P9596
// Writer: WRuperD
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 5e5 + 10;

set <int> st[MAX * 2];
int s[MAX * 10], tag[MAX * 10], s2[MAX * 10];
int ls[MAX * 10], rs[MAX * 10];

int lsh[MAX * 2];

void pushdown(int x, int l, int r){
	if(!tag[x])	return ;
	if(ls[x] and s2[ls[x]])	s[ls[x]] -= tag[x], s2[ls[x]] += tag[x], tag[ls[x]] += tag[x];
	if(rs[x] and s2[rs[x]])	s[rs[x]] -= tag[x], s2[rs[x]] += tag[x], tag[rs[x]] += tag[x];
	tag[x] = 0;
}

int psz;

void add(int l, int r, int pos, int val, int val2, int &x){
	if(!x)	x = ++psz;
	tag[x] = 0;
	if(l == r){
		s[x] = val - val2;
		s2[x] = val2;
		return ;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid)	add(l, mid, pos, val, val2, ls[x]);
	else add(mid + 1, r, pos, val, val2, rs[x]);
	s[x] = max(s[ls[x]], s[rs[x]]);
	s2[x] = max(s2[ls[x]], s2[rs[x]]);
}

void add2(int l, int r, int dl, int dr, int val, int &x){
	if(dl > dr)	return ;
	if(!x or !s2[x])	return ;
	if(dl <= l and r <= dr){
		s[x] -= val;
		s2[x] += val;
		tag[x] += val;
		return ;
	}
	pushdown(x, l, r);
	int mid = (l + r) >> 1;
	if(dl <= mid)	add2(l, mid, dl, dr, val, ls[x]);
	if(dr > mid)	add2(mid + 1, r, dl, dr, val, rs[x]);
	s[x] = max(s[ls[x]], s[rs[x]]);
	s2[x] = max(s2[ls[x]], s2[rs[x]]);
}

int getrk(int l, int r, int pos, int x){
	if(!x or !s2[x])	return 0;
	if(l == r)	return s2[x];
	if(r <= pos)	return s2[x];
	pushdown(x, l, r);
	int mid = (l + r) >> 1, ans = 0;	
	if(pos > mid)	ans = max(s2[ls[x]], getrk(mid + 1, r, pos, rs[x]));
	else ans = getrk(l, mid, pos, ls[x]);
	return ans;
}

void del(int l, int r, int pos, int val, int &x){
	if(l == r){
		s[x] = 0;
		s2[x]--;
		st[l].erase(val);
		if(st[l].begin() == st[l].end()){
			s2[x] = 0;
			return ;
		}
		auto u2 = st[l].end();
		u2--;
		s[x] = *u2 - s2[x];
		return ;
	}
	int mid = (l + r) >> 1;
	pushdown(x, l, r);
	if(pos <= mid)	del(l, mid, pos, val, ls[x]);
	else del(mid + 1, r, pos, val, rs[x]);
	s[x] = max(s[ls[x]], s[rs[x]]);
	s2[x] = max(s2[ls[x]], s2[rs[x]]);
	return ;
}

void upd(int l, int r, int pos, int val, int newrk, int &x){
	if(!x)	x = ++psz;
	if(l == r){
		s[x] = 0;
		st[l].insert(val);
		s2[x] = newrk;
		auto u2 = st[l].end();
		u2--;
		s[x] = *u2 - s2[x];
		return ;
	}
	int mid = (l + r) >> 1;
	pushdown(x, l, r);
	if(pos <= mid)	upd(l, mid, pos, val, newrk, ls[x]);
	else upd(mid + 1, r, pos, val, newrk, rs[x]);
	s[x] = max(s[ls[x]], s[rs[x]]);
	s2[x] = max(s2[ls[x]], s2[rs[x]]);
	return ;
}

int a[MAX];
pair <int, int> b[MAX];

struct qry{
	int x, y;
}; qry q2[MAX];

void solve(){
	int n = read(), q = read();
	int mm;
	for(int i = 1; i <= n; i++){
		a[i] = read();
		lsh[++mm] = a[i];
		// st[a[i]].insert(i);
		b[i].first = a[i], b[i].second = i;
	}
	sort(b + 1, b + n + 1);
	b[n + 1].first = inf;
	int rt = 0;
	
	// write(s[rt]), endl;
	for(int i = 1; i <= q; i++){
		q2[i].x = read(), q2[i].y = read();
		lsh[++mm] = q2[i].y;
	}
	sort(lsh + 1, lsh + mm + 1);
	int m = unique(lsh + 1, lsh + mm + 1) - lsh - 1;
	for(int i = 1; i <= n; i++){
		a[i] = lower_bound(lsh + 1, lsh + m + 1, a[i]) - lsh;
		st[a[i]].insert(i);
	}
	for(int i = 1; i <= n; i++){
		if(b[i].first != b[i + 1].first){
			add(1, m, lower_bound(lsh + 1, lsh + m + 1, b[i].first) - lsh, b[i].second, i, rt);
		}
	}
	int lim = m;
	
	for(int i = 1; i <= q; i++){
		int x = q2[i].x + 1, y = q2[i].y;
		y = lower_bound(lsh + 1, lsh + m + 1, y) - lsh;
		del(1, lim, a[x], x, rt);
		add2(1, lim, a[x] + 1, lim, -1, rt);
		// write(s[rt]), put();
		int rk1 = getrk(1, lim, y, rt) + 1;
		// write(rk1), put();
		a[x] = y;
		upd(1, lim, a[x], x, rk1, rt);
		add2 (1, lim, a[x] + 1, lim, 1, rt);
		write(s[rt]), endl;
	}	
}

signed main(){
	// freopen("sort.in", "r", stdin);
	// freopen("sort.out", "w", stdout);
	int t = 1;
	while(t--)	solve();
	return 0;
}