题目大意

给出一个长度为 nn 的序列，要求支持两种操作：1、单点修改。2、如果从 nn 个数中选出一些数，给他们一共加上 kk，求加完后这些数中最大值的最小值（只是假设，并不是真的要加上）。

思路

第一种操作很简单，我们重点考虑一下第二种。

什么情况下最优呢？显然，应该是选出来的这些数在加完之后值一样的时候，而且我们应该尽量多选一些数，这样平均下来才会尽量小。

也就是说，假设最后选出来的这些数在一共加上 kk 之后的值都为 bb，那我们要选的数就是所有小于等于 bb 的，但这样会很麻烦，因为随着选数方案的改变，bb 也会随之而变，所以我们可以换种思路。

我们随便选一个数 tt 出来，以它作为标准，把所有小于等于它的数都选出来，然后先把小于它的数累加到等于它，然后再一起累加。

相当于是这样。

以第四个数为标准，先把其他小于它的数加到和它一样。

然后再一起累加。

这样，选出来的作为标准的这个数 tt 就很关键了，显然它不能太大，不然其他的数还没有加到和它一样就已经把 kk 用完了，但它也不能太小，因为有可能存在一个数 xx，一开始的时候，xx 是大于 tt 的，但在最后一起累加的时候，它又小于累加后得到的数了，这样就会存在浪费，那我们要怎么找出这个不大不小刚刚好的 tt 呢？

不难发现，tt 是可以二分的，具体来说，我们按照刚刚那个办法，先随便找一个数作为 tt，如果其他小于它的数没法全部累加到和它一样，就说明这个数太大了，反之，如果可以，就说明这个数也许是正确答案，我们就可以继续往大的去找。

那么问题又来了，显然要求出所有小于等于它的数能否累加到和它一样，我们就需要知道这些数的数量和总和，显然如果暴力查找单次询问是 O(nlog⁡n)O(n\log n) 的，所以有没有一种数据结构之类的东西能快速维护这两个值呢？

平衡树啊！

我们可以直接把二分的过程放到平衡树上去，显然平衡树是可以很好的维护我们需要的这两个值的，这样单次询问复杂度就降到了 O(log⁡n)O(\log n)，轻松过掉 10510^5。

啊对了，这里有一个坑点，由于我们需要知道的是所有小于等于 tt 的数的总和和数量，所以光统计这个点的左儿子是不够的，还要考虑到它祖先的左儿子，不过这个可以在递归的过程中累加，如果是往右儿子走，我们就把当前这个点及它左儿子这颗子树中的信息累加到一个变量里，在计算时，把这个变量的值也塞到一块进行计算就行了。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r); i <= i##end; i++)
#define per(i, r, l) for(int i = (r), i##end = (l); i >= i##end; i--)
#define debug(x) cerr<<#x<<" = "<<x
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N = 1e5+10, mod = 20060209;
const double inf = 1e16;
int n, m, rt, sed, tot, son[N<<1][2], siz[N<<1], num[N<<1], rnd[N<<1];
ll a[N], val[N<<1], sum[N<<1];//这里采用常数小码量也小的 Treap
inline int rd()
{
	return sed = 114514ll*sed%mod*1919810%mod;
}
inline void push_up(int p)
{
	siz[p] = siz[son[p][0]]+siz[son[p][1]]+num[p];
	sum[p] = sum[son[p][0]]+sum[son[p][1]]+val[p]*num[p];
}
inline void spin(int &p, int s)//板子
{
	int t = son[p][s];
	son[p][s] = son[t][s^1];
	son[t][s^1] = p;
	push_up(p);
	push_up(t);
	p = t;
}
void ins(int &p, ll k)//板子
{
	if(!p)
	{
		p = ++tot;
		rnd[p] = rd();
		siz[p] = num[p] = 1;
		val[p] = sum[p] = k;
		return;
	}
	if(val[p] == k)
	{
		num[p]++;
		siz[p]++;
		sum[p] += k;
		return;
	}
	int t = (val[p] < k);
	ins(son[p][t], k);
	if(rnd[son[p][t]] > rnd[p])
		spin(p, t);
	push_up(p);
}
void del(int &p, ll k)//板子
{
	if(!p)
		return;
	if(val[p] == k)
	{
		if(num[p] > 1)
		{
			num[p]--;
			siz[p]--;
			sum[p] -= k;
			return;
		}
		if(!son[p][0] && !son[p][1])
			p = 0;
		else if(son[p][0] && !son[p][1])
		{
			spin(p, 0);
			del(son[p][1], k);
		}
		else if(!son[p][0] && son[p][1])
		{
			spin(p, 1);
			del(son[p][0], k);
		}
		else
		{
			int t = (rnd[son[p][0]] < rnd[son[p][1]]);
			spin(p, t);
			del(son[p][t^1], k);
		}
		push_up(p);
		return;
	}
	int t = (val[p] < k);
	del(son[p][t], k);
	if(rnd[son[p][t]] > rnd[p])
		spin(p, t);
	push_up(p);
}
double query(int p, ll k, ll s1, int s2)//s1 和 s2 记录祖先的左子树的信息
{
	if(!p)
		return inf;
	double t = (s1+sum[p]-sum[son[p][1]]+k)*1.0/(s2+siz[p]-siz[son[p][1]]);//计算给所有小于等于当前数一共加上 k 以后最小的值，也就是上面的图三的结果
	if(t > val[p])//往右儿子递归
		return min(query(son[p][1], k, s1+sum[p]-sum[son[p][1]], s2+siz[p]-siz[son[p][1]]), t);
	else
		return query(son[p][0], k, s1, s2);
}
int main()
{
	sed = time(0)%mod;
	scanf("%d%d", &n, &m);
	rep(i, 1, n)
		scanf("%d", &a[i]), ins(rt, a[i]);
	rep(i, 1, m)
	{
		int op, p;
		ll v;
		scanf("%d", &op);
		if(op == 1)
		{
			scanf("%d%lld", &p, &v);
			del(rt, a[p]);
			ins(rt, v);
			a[p] = v;
		}
		else
		{
			scanf("%lld", &v);
			printf("%.5lf\n", query(rt, v, 0, 0));
		}
	}
	return 0;
}