Chemistry Experiment Codeforces Round 247 (Div. 2) 线段树动态开点，二分

第一次写的时候还不会线段树的动态开点，写了一个是线段树但是是\(O(N^2)\)的写法，现在用动态开点武装了自己，会了正解\(O(qlog n^2)\)。首先建立一个权值线段树，但这里的权值很大，通过动态开点去建树来节省空间，对于两种操作：

1. 操作1，常见的动态开点的单点修改
2. 操作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;
		}
	}	
}