CF1862G(multiset集合)

CF1862G(multiset集合)

题意：
一个数组n可以进行如下操作：
先对数组排序，对 $[a_1,a_2,a_3,…,a_n] +[n,n-1,n-2,…,1] $ ,然后去重;重复该操作直至元素变为1，对数组k次询问，每次询问x,k,将 $a_x=k$ ，计算进行若干次操作后数组最后一个数
思路：
考虑对一个确定的数组操作，每次操作会使 $ a_{i-1} 和 a_{i} $的差值减1，当两者相等时消除一个，每次操作 $a_n+1$ ，且最后一个树必定包含 $a_n$ ，所以最后的数为 $ a_{max} +b_{max} $,b为相邻的差值，所以考虑维护每次两个数的最大值，用multiset维护，每次删除差值用extract(如果有多个相同的值只会删一个),删除a元素要删除该节点

void solve(){
	int n;
	cin>>n;
	vector<int> a(n);
	for(int i=0;i<n;i++)cin>>a[i];
	multiset<int> s,d{0};
	auto add=[&](int x){
		auto it=s.insert(x);
		auto r=next(it);
		if(it!=s.begin())d.insert(x-*prev(it));
		if(r!=s.end())d.insert(*r-x);
		if(it!=s.begin()&&r!=s.end()){
			d.extract(*r-*prev(it));
		}
	};
	auto del=[&](int x){
		auto it=s.find(x);
		auto r=next(it);
		if(it!=s.begin())d.extract(x-*prev(it));
		if(r!=s.end())d.extract(*r-x);
		if(it!=s.begin()&&r!=s.end()){
			d.insert(*r-*prev(it));
		}
		s.erase(it);
	};
	for(int i=0;i<n;i++)add(a[i]);
	int q;
	cin>>q;
	while(q--){
		int x,y;
		cin>>x>>y;
		x--;
		del(a[x]);
		a[x]=y;
		add(a[x]);
		cout<<*s.rbegin()+*d.rbegin()<<" ";
	}
	cout<<"\n";
}