这是代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,INF=1e9+5;
const double eps=1e-4;
struct node
{
	int lc,rc,cnt;
	ll sum;
}t[N*32];
int n,m,tot=1;
ll a[N];
void up(int rt)
{
	t[rt].cnt=t[t[rt].lc].cnt+t[t[rt].rc].cnt;
	t[rt].sum=t[t[rt].lc].sum+t[t[rt].rc].sum;
}
void add(int rt,int l,int r,ll x,int cnt)
{
	if(l==r)
	{
		t[rt].cnt+=cnt;
		t[rt].sum=t[rt].cnt*x;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		if(!t[rt].lc) t[rt].lc=++tot;
		add(t[rt].lc,l,mid,x,cnt);
	} 
	else 
	{
		if(!t[rt].rc) t[rt].rc=++tot;
		add(t[rt].rc,mid+1,r,x,cnt);
	}
	up(rt);
}
int query_cnt(int rt,int l,int r,int L,int R)
{
	if(!rt) return 0;
	if(L<=l&&r<=R) return t[rt].cnt;
	int mid=(l+r)>>1;
	int ans=0;
	if(L<=m) ans+=query_cnt(t[rt].lc,l,mid,L,R);
	if(R>m) ans+=query_cnt(t[rt].rc,mid+1,r,L,R);
	return ans;
}
ll query_sum(int rt,int l,int r,int L,int R)
{
	if(!rt) return 0;
	if(L<=l&&r<=R) return t[rt].sum;
	int mid=(l+r)>>1;
	ll ans=0;
	if(L<=m) ans+=query_sum(t[rt].lc,l,mid,L,R);
	if(R>m) ans+=query_sum(t[rt].rc,mid+1,r,L,R);
	return ans;
}
int turn(double x)
{
	ll f=ceil(x);
	return f>INF?INF:f;
}
int check(double mid,double v)
{
	ll cnt=query_cnt(1,1,INF,0,turn(mid));
	ll sum=query_sum(1,1,INF,0,turn(mid));
	return cnt*mid-sum>=v;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i],add(1,0,INF,a[i],1);
	while(m--)
	{
		ll op,x,y;
		scanf("%lld",&op);
		if(op==1)
		{
			scanf("%lld%lld",&x,&y);
			add(1,0,INF,a[x],-1);
			a[x]=y;
			add(1,0,INF,a[x],1);
		}
		else 
		{
			scanf("%lld",&x);
			double l=0,r=1e15,ans,mid;
			while(fabs(r-l)>eps)
			{
				mid=(l+r)/2;
				if(check(mid,x)) ans=mid,r=mid;
				else l=mid;
			}
			printf("%.5lf\n",ans);
		}
	}
	return 0;
}