题目传送门：冒泡排序

写在前面

学完线段树后的练习题，听了老师评讲才做出来，于是写一篇题解报告巩固温习。本题解报告会详细的写出推导过程乃至部分分的获得办法，但依旧需要认真梳理逻辑。

题意描述

给定一个序列，进行 $q$ 次修改，每次修改后从前往后冒泡，求把序列排序成升序的次数（冒泡完成后要还原数组）。

题解

算法一

暴力模拟，复杂度拉满了是 $O(n^3)$，如果写点优化应该能过子任务一。反正我没过，T 了两个点。

算法二

我们模拟一下冒泡的过程，比如这里有个数列 $a:4,2,3,5,1$，一次冒泡后变成了：$2,3,4,1,5$。我们发现 $2,3,1$ 前面比它们小的数都减少了一个。进行一次冒泡，数列变成了 $2,3,1,4,5$。$1$ 前面比它小的数减少了一个。我们一直冒泡下去，直到每个数前面的数都严格不大于它。

所以我们可以得到规律，设 $f_i$ 为 $a_i$ 前面比 $a_i$ 小的数的个数，其实一次冒泡就是让所有 $f_i-1$，因为一次冒泡我们只会把一个大于 $a_i$ 的数移到 $a_i$ 后面。那很显然，$ans=\max_{i=1}^{n}f_i$。

于是我们可以树套树来维护，用权值线段树维护 $f_i$，用普通线段树维护 $\max f_i$。

复杂度 $O(n\log_2^2n)$，可以通过子任务 $1\sim3$。

但因为我太弱了，没学过树套树，所以不会这个部分分。

算法三，正解

设 $g_i$ 为第 $1\sim i$ 内 $\le a_i$ 的数，显然存在 $f_i=i-g_i$。然而，如果存在两个数使得 $i<j,a_i\geq a_j$，则一定有 $f_i<f_j$。为什么呢？因为 $i<j$ 所以 $a_i$ 在 $a_j$ 后面，被减去的数更少。又因为 $a_i\geq a_j$，所以比 $a_i$ 小的数一定严格不小于比 $a_j$ 小的数，也就是 $g_i\geq g_j$，减去的数更多。综上，如果存在两个数使得 $i<j,a_i\geq a_j$，则一定有 $f_i<f_j$。

所以如果我们把 $g_i$ 的定义改成整个数组内 $\le a_i$ 的数，其实答案是不变的。这又是为什么呢？ 考虑这样改变定义后对 $f_i$ 的影响：这样更改后，如果 $a_i$ 后面有比 $a_i$ 小的数 $a_j$，那么 $g_i$ 会增大，$f_i$ 会变小。但又因为 $i<j,a_i\geq a_j$，根据上面的证明可知，$f_i\le f_j$，所以本来 $f_i$ 就不会变成答案了，现在变小了肯定还是不可能。反之，如果没有 $a_i\geq a_j$，那么 $a_i$ 可能成为答案，但这样定义修改后是不会对这个 $f_i$ 产生影响的。如此证明完毕。于是我们可以用权值线段树实现，同时维护至于内数的个数，以及 $\max f_i$。复杂度降低到 $O(n\log_2n)$。

救命究竟是怎样的大佬能想出这样的解法啊！

代码实现

说实话我觉得此题代码写起来还是很有难度的，当然不排除是因为我太弱了的问题。这里详细解释一下代码的一些实现问题。

离散化

首先值域是从 $1\sim 10^9$，所以要建立权值线段树需要离散化。$a$ 是原数组，$q$ 是询问数组（我把询问离线下来了）。$b$ 是离散化数组。不过要注意一下，如果两个元素值相同，相对位置关系不会改变。所以离散化的时候就要同是记录 $val$ 和 $id$，然后 sort 的时候也注意一下。

cin>>n>>m;
for(int i=1;i<=n;i++){
	cin>>a[i].val;
	a[i].id=i;
	b[++cnt]=a[i];
}
for(int i=1;i<=m;i++){
	cin>>q[i].id>>q[i].val;//把id号元素修改为val
	q[i].id++;//原编号从0开始，我把它们修改成从1开始，所以id++
	b[++cnt]=q[i];//离线询问 
}
build(1,1,cnt);//建立空树
sort(b+1,b+1+cnt,cmp);//离散化 

维护线段树

update_change & update_add

线段树维护两个元素：$maxx,sum$，$maxx$ 表示 $l\sim r$ 内的 $\max f_i$，$sum$ 表示 $l\sim r$ 内有多少个数。于是我们需要分别写两个函数维护：update_change 是插入、删除元素后进行修改，update_add 则修改 $maxx$。

void update_change(int p,int x,int d){//对应题目的修改操作 
	if(tr[p].l==tr[p].r){
		if(d!=-INF) tr[p].sum=1;//对应加入 
		else tr[p].sum=0;//对应删除 
		tr[p].maxx=d;
		return;
	}
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(x<=mid) update_change(p<<1,x,d);
	else update_change(p<<1|1,x,d);
	push_up(p);
}

void update_add(int p,int l,int r,int d){//对应修改后对maxx的更新 
	if(l>r) return;
	if(l<=tr[p].l&&tr[p].r<=r){
		f(p,d);//修改 
		return;
	}
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(l<=mid) update_add(p<<1,l,r,d);
	if(mid<r) update_add(p<<1|1,l,r,d);
	push_up(p);
}

query

首先建一棵空树，然后把 $a$ 离散化后的映射值插入树内。假设第 $i$ 个元素的映射值为 $x$，插入之后，我们首先在对应位置的 $sum\gets sum+1$。然后考虑维护 $maxx$：跟上文一样，$g_i$ 表示 $\le x$ 的数，我们还需要函数 $query$ 查询一个元素的排名。

int query(int p,int x){//查询一个数的排名 
	if(tr[p].l==tr[p].r) return tr[p].sum;
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(x<=mid) return query(p<<1,x);
	else return tr[p<<1].sum+query(p<<1|1,x);
}

插入 $a$ 中元素

值得注意的是，因为元素有重复的，所以我们在求 $g_i$ 的时候，应该求 $x-1$ 的排名，然后 $+1$，而不是直接 $query(x)$。

然后根据 $f_i=i-g_i=i-query(x-1)-1$ 修改对应位置的 $maxx$。接着我们又发现，如果在 $x$ 的位置插入了一个数，那么后面所有数的 $g_i$ 都会加一，$f_i$ 则减一。

for(int i=1;i<=n;i++){//插入a中元素
	int x=lower_bound(b+1,b+1+cnt,a[i])-b;//查找映射值 
	int y=query(1,x-1);//查找映射值前一位的排名，因为有重复的值	 
	update_change(1,x,i-y-1);//在x的位置加上1，g(x)=i-y-1
	update_add(1,x+1,cnt,-1);//x上的数多了一个，表明g(x+1)~g(cnt)都+1，于是f对应-1 
	c[a[i].id]=x;//把a映射值复制给c 
}

此外我们用 $c$ 数组存一下映射值，方便以后的修改操作。

修改

主要分为两步：删除原来的数与插入新的数。具体操作看代码吧，注释写的超详细了。

for(int i=1;i<=m;i++){//查询 
	update_change(1,c[q[i].id],-INF);//把要更改的元素移除，利用c找到映射值，然后在值域线段树上修改为0 
	update_add(1,c[q[i].id]+1,cnt,1);//从该映射值往后到cnt的fi+1，因为这个值被移除了 
	int x=lower_bound(b+1,b+1+cnt,q[i])-b;//要修改成为哪个映射值
	c[q[i].id]=x;//把对应id的数修改为新的映射值 
	int y=query(1,x-1);//查找映射值前一位的排名
	update_change(1,x,q[i].id-y-1);//同上
	update_add(1,x+1,cnt,-1);//同上 
	cout<<tr[1].maxx<<'\n';
}

AC code

#include<bits/stdc++.h>
#define INF 0x7fffffff 
using namespace std;
const int N=5e5+5;
struct NODE{
	int id,val;
	bool operator < (const NODE &a) const{
		if(a.val!=val) return val<a.val;//权值为第一关键字 
		return id<a.id;//顺序为第二关键字 
	}
}a[N],q[N],b[N<<1];
struct TREE{
	int maxx,sum,lz;
	//maxx是f也就是答案，sum记录值域内的数的个数，lz懒标记 
	int l,r;
}tr[N<<3];
int n,m,cnt,c[N<<1];
void push_up(int p){
	tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
	tr[p].maxx=max(tr[p<<1].maxx,tr[p<<1|1].maxx);
}
void f(int p,int d){//给f_max打懒标记 
	if(tr[p].maxx==-INF) return;
	tr[p].lz+=d;
	tr[p].maxx+=d;
}
void push_down(int p){
	if(tr[p].lz){
		f(p<<1,tr[p].lz);
		f(p<<1|1,tr[p].lz);
		tr[p].lz=0;
	}
}
void build(int p,int l,int r){//建空的权值线段树 
	tr[p].l=l; tr[p].r=r;
	if(l==r){
		tr[p].maxx=-INF;
		tr[p].sum=0;
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p);
}
void update_change(int p,int x,int d){//对应题目的修改操作 
	if(tr[p].l==tr[p].r){
		if(d!=-INF) tr[p].sum=1;//对应加入 
		else tr[p].sum=0;//对应删除 
		tr[p].maxx=d;
		return;
	}
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(x<=mid) update_change(p<<1,x,d);
	else update_change(p<<1|1,x,d);
	push_up(p);
}
void update_add(int p,int l,int r,int d){//对应修改后对maxx的更新 
	if(l>r) return;
	if(l<=tr[p].l&&tr[p].r<=r){
		f(p,d);//修改 
		return;
	}
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(l<=mid) update_add(p<<1,l,r,d);
	if(mid<r) update_add(p<<1|1,l,r,d);
	push_up(p);
}
int query(int p,int x){//查询一个数的排名 
	if(tr[p].l==tr[p].r) return tr[p].sum;
	push_down(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(x<=mid) return query(p<<1,x);
	else return tr[p<<1].sum+query(p<<1|1,x);
}
bool cmp(NODE a1,NODE a2){ 
	if(a1.val!=a2.val) return a1.val<a2.val;
	return a1.id<a2.id;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].val;
		a[i].id=i;
		b[++cnt]=a[i];
	}
	for(int i=1;i<=m;i++){
		cin>>q[i].id>>q[i].val;//把id号元素修改为val
		q[i].id++;
		b[++cnt]=q[i];//离线询问 
	}
	build(1,1,cnt);
	sort(b+1,b+1+cnt,cmp);//离散化 
	for(int i=1;i<=n;i++){//建树 
		int x=lower_bound(b+1,b+1+cnt,a[i])-b;//查找映射值 
		int y=query(1,x-1);//查找映射值前一位的排名，因为有重复的值	 
		update_change(1,x,i-y-1);//在x的位置加上1，g(x)=i-y-1
		update_add(1,x+1,cnt,-1);//x上的数多了一个，表明g(x+1)~g(cnt)都+1，于是f对应-1 
		c[a[i].id]=x;//把a映射值复制给c 
	}
	for(int i=1;i<=m;i++){//查询 
		update_change(1,c[q[i].id],-INF);//把要更改的元素移除，利用c找到映射值，然后在值域线段树上修改为0 
		update_add(1,c[q[i].id]+1,cnt,1);//从该映射值往后到cnt的fi+1，因为这个值被移除了 
		int x=lower_bound(b+1,b+1+cnt,q[i])-b;//要修改成为哪个映射值
		c[q[i].id]=x;//把对应id的数修改为新的映射值 
		int y=query(1,x-1);//查找映射值前一位的排名
		update_change(1,x,q[i].id-y-1);//同上
		update_add(1,x+1,cnt,-1);//同上 
		cout<<tr[1].maxx<<'\n';
	}
	return 0;
}

写在后面

此题就我而言还是觉得是比较难的紫题了，主要难点是对 $f_i=i-g_i$ 的推导与推广，正如另一篇题解所说，“对于这种求极值的题，我们可以不用盯着最优决策考虑，适当放宽条件，既可以保证取极值的正确性，又可以保证代码的码量较小，有点类似于不等式放缩。还是需要灵活地思维。”

此外也需要对线段树的一定理解，推一手我线段树的复习总结博客：线段树复习小结。

码字不易，求过审，求点赞！