CF1862G 题解

首先这个查询操作很迷，考虑先化简查询操作。

不难发现由于每次是加上一个逆的等差序列，因此一次操作完每个数与它的前驱之差一定会减少，因此加上等差序列的次数就等于全局每个数与它的前驱之差最大值。

又因为会排序去重，所以最后剩下来的数一定是最开始的数一路加过来的，至此我们发现答案就是全局每个数与它的前驱之差最大值加上全局最大值。

考虑怎么维护这个东西，显然可以使用 FHQ treap 维护这件事，我们需要维护子树最大差，最小值，最大值就可以合并信息，在点修时先把原来的数删掉，在插入新的数。

时间复杂度 \(O(n \log n)\)。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+114;
int n,q;
int a[maxn];
struct Node{
	int val,ls,rs,w,mx,mi,ans;
}treap[maxn];
stack<int> brush;
int tot;
int rt;
int clone(int w){
	int New;
    if(brush.size()>0) New=brush.top(),brush.pop();
    else New=++tot;
	treap[New].val=rand();
	treap[New].ls=0;
	treap[New].rs=0;
	treap[New].w=w;
	treap[New].mi=treap[New].mx=w;
	treap[New].ans=0;
	return New;
}
inline void pushup(int cur){
	treap[cur].ans=0;
	treap[cur].ans=max(treap[treap[cur].ls].ans,treap[treap[cur].rs].ans);
	if(treap[cur].ls!=0) treap[cur].ans=max(treap[cur].w-treap[treap[cur].ls].mx,treap[cur].ans);
	if(treap[cur].rs!=0) treap[cur].ans=max(treap[treap[cur].rs].mi-treap[cur].w,treap[cur].ans);
	treap[cur].mx=treap[cur].mi=treap[cur].w;
	if(treap[cur].rs!=0) treap[cur].mx=treap[treap[cur].rs].mx;
	if(treap[cur].ls!=0) treap[cur].mi=treap[treap[cur].ls].mi;
}
inline int merge(int x,int y){
    if(!x||!y) return x+y;
    if(treap[x].val<treap[y].val){
        treap[x].rs=merge(treap[x].rs,y);
        pushup(x);
        return x;
    }
    else{
        treap[y].ls=merge(x,treap[y].ls);
        pushup(y);
        return y;
    }
}
inline void split(int cur,int x,int &l,int &r) {
	if(cur==0){
		l=r=0;
		return ;
	}
	if(treap[cur].w>x){
		r=cur;
		split(treap[cur].ls,x,l,treap[cur].ls);
	}
	else{
		l=cur;
		split(treap[cur].rs,x,treap[cur].rs,r);
	}
	pushup(cur);
}
void dfs(int u){
	if(u==0) return ;
	dfs(treap[u].ls);
	cout<<treap[u].w<<' '<<treap[u].mx<<' '<<treap[u].mi<<'\n';
	dfs(treap[u].rs);
}
void insert(int w){
	int x=0,y=0,z=0;
	split(rt,w,x,z);
	y=clone(w);
	rt=merge(x,merge(y,z));
}
void erase(int w){
	int x=0,y=0,z=0;
	split(rt,w-1,x,y);
	split(y,w,y,z);
    brush.push(y);
	y=merge(treap[y].ls,treap[y].rs);
	rt=merge(x,merge(y,z));
}
void work(){
	rt=tot=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(a[i]); 
	}
	cin>>q;
	while(q--){
		int x,y;
		cin>>x>>y;
		erase(a[x]);
		a[x]=y;
		insert(a[x]);
		cout<<treap[rt].mx+treap[rt].ans<<' ';
	}
	cout<<'\n';
}
int T;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)work();
}