第一次写的时候还不会线段树的动态开点，写了一个是线段树但是是\(O(N^2)\)的写法，现在用动态开点武装了自己，会了正解\(O(qlog n^2)\)。首先建立一个权值线段树，但这里的权值很大，通过动态开点去建树来节省空间，对于两种操作：
- 操作1，常见的动态开点的单点修改
- 操作2，二分答案，然后在线段树上二分，假设二分的答案是\(ans\)，找到线段树上所有小于\(\leq ans\)的值\(S\)和数量\(SIZE\),判断\(SIZE \times ans - S \geq v\)是否成立
更多细节见代码（直接copy板子，有点丑）
#define int long long
const int N = 1e5 + 10;
struct segtree
{
int l, r, sz, s;
}seg[N * 30];
int n, m, tot = 1, a[N], rlim = 1e10;
void update(int &id)
{
seg[id].s = seg[seg[id].l].s + seg[seg[id].r].s;
seg[id].sz = seg[seg[id].l].sz + seg[seg[id].r].sz;
}
void change(int &id, int l, int r, int pos, int val)
{
if(!id)
id = ++tot;
if(l == r)
{
seg[id].s += l * val;
seg[id].sz += val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid)
change(seg[id].l, l, mid, pos, val);
else
change(seg[id].r, mid + 1, r, pos, val);
update(id);
}
long double query(int id, int l, int r, long double qr)
{
if(!id)
return 0;
if(r <= qr)
{
return qr * seg[id].sz - seg[id].s;
}
int mid = (l + r) >> 1;
long double ans = 0;
if(qr <= mid)
ans = ans + query(seg[id].l, l, mid, qr);
else if(qr > mid)
ans = ans + query(seg[id].l, l, mid, qr) + query(seg[id].r, mid + 1, r, qr);
return ans;
}
bool check(double x, int v)
{
int root = 1;
long double ans = query(root, 0, rlim, x);
if(ans >= v)
return true;
else
return false;
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
int root = 1;
change(root, 0, rlim, a[i], 1);
}
while(m--)
{
int opt; cin>>opt;
if(opt == 1)
{
int pos, x, root = 1; cin>>pos>>x;
change(root, 0, rlim, a[pos], -1);
a[pos] = x;
change(root, 0, rlim, a[pos], 1);
}
else
{
int v; cin>>v;
long double l = 0, r = 1e16;
while(r - l > 1e-6)
{
long double mid = (l + r) / 2.0;
if(check(mid, v)) r = mid;
else l = mid;
}
cout<<l<<endl;
}
}
}