Guess the weight

原题链接

题意：你现在有一个技能，先从牌堆里面摸一张牌，然后可以知道这张牌的大小，然后摸第二张，猜其大小，只能猜大或者小，不能猜等，猜对了才可以获得第二张牌。你是知道牌堆里面牌的情况的，但是牌堆每次都会被人打乱。那么现在初始有 $n$ 张牌，各大小为 $x_i$ ，然后有 $m$ 次操作，有两种操作，第一种为往牌堆里加 $v$ 张大小为 $x$ 的牌。第二种问你现在在最优策略下，使用技能获得第二张牌的概率是多少，用最简分数表示。

对于某个权值为 $x$ 的牌，我们设其起小的牌有 $g$ 个，比其大的有 $h$ 个。那么根据牌堆的中位数 $mid$ ，我们可以确定边界，设其为 $b$ （ $mid$ 不一定等于 $b$ ），即 $[min,b]$ 中 $g\le h$ ， $[b+1,max]$ 中 $g>h$ ，即我们可以把所有元素为 $L$ 组和 $R$ 组两个分组。那么最优策略是显然的，当抽到的第一张牌 $x\le b$ ，我就猜大，否则猜小，其实 $x=b$ 的情况无论猜大猜小都一样了，因为获胜概率是一样的。

那么牌堆中位数在权值线段树上二分就可以找到，现在问题是我们如何计算答案。这里可以考虑反向计算，因为想过正向计算以后会发现稍微有点麻烦。那么我们就考虑每种抽牌组合去考虑概率。那么既然是反向计算，自然是失败的概率，首先，分母显然，因为是考虑所有抽牌组合，自然就是 $n\ast (n-1)$ 。主要还是计算分子，如何才算失败呢，假设我第一张牌抽到 $x$ ，我要失败就一定首先拿到了同分组的牌 $y$ ，如果同在 $L$ 组，即 $x\ge y$ ，同在 $R$ 组则 $x\le y$ 。我们只要计算出所有这样的 $(x,y)$ 即可，也就是分别算 $L$ 组和 $R$ 组的 $(x,y)$ 个数， 两个小组其实也就是两个区间，我们就想动态维护区间 $(x,y)$ 个数，发现是可行的。

可能有hxd看不懂标程里面为什么一个元素的时候算 $(x,y)$ 数量是 $cnt[i]\times cnt[i]$ 而不是 $cnt[i]\times (cnt[i]-1)$ ，实际上他这是为了防止出现计算出现负数，发生不合理的情况，后面他又减去了多算的情况。下面这份代码里面就直接进行了无重复的计算。

#include <bits/stdc++.h>
#define lson rt<<1
#define rson (rt<<1)|1
#define down 0
#define up 200001
#define root 1
#define P pair<int, ll>using namespace std;typedef long long ll;const int N = 2e5 + 10;int n, m, a[N], cnt[N];P tree[N << 2];void push_up(int rt) {tree[rt].first = tree[lson].first + tree[rson].first;tree[rt].second = tree[lson].second + tree[rson].second + 1ll * tree[lson].first * tree[rson].first;
}void build(int rt, int l, int r) {if (l == r) {tree[rt].first = cnt[l];if (cnt[l] > 1) tree[rt].second = 1ll * cnt[l] * (cnt[l] - 1);else tree[rt].second = 0;return ;}int mid = l + r >> 1;build(lson, l, mid);build(rson, mid + 1, r);push_up(rt);
}void update(int rt, int l, int r, int x, int v) {if (l == r) {tree[rt].first += v;if (tree[rt].first > 1) tree[rt].second = 1ll * tree[rt].first * (tree[rt].first - 1);else tree[rt].second = 0;return ;}int mid = l + r >> 1;if (x <= mid) update(lson, l, mid, x, v);else update(rson, mid + 1, r, x, v);push_up(rt);
}P query(int rt, int l, int r, int L, int R) {if (L <= l && r <= R) {return tree[rt];}int mid = l + r >> 1, x = 0, y = 0;ll z = 0, w = 0;if (mid >= L) {P tmp = query(lson, l, mid, L, R);x += tmp.first; z += tmp.second;}if (mid < R) {P tmp  = query(rson, mid + 1, r, L, R);y += tmp.first; w += tmp.second;}return {x + y, z + w + 1ll * x * y};
}int Mid(int rt, int l, int r, int k) {if (l == r) return l;int mid = l + r >> 1;if (k <= tree[lson].first) return Mid(lson, l, mid, k);else return Mid(rson, mid + 1, r, k - tree[lson].first);
}int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint T;scanf("%d", &T);while(T--) {scanf("%d%d", &n, &m);memset(cnt, 0, sizeof cnt);for (int i = 1, x; i <= n; ++i) {scanf("%d", &x);cnt[x]++;}build(root, down, up);while(m--) {int op, v, x;scanf("%d", &op);if (op == 2) {int mid = Mid(root, down, up, (n + 1) / 2);int l = query(root, down, up, down, mid - 1).first;int r = n - l - cnt[mid];ll p, q = 1ll * n * (n - 1), d;if (l <= r) {p = query(root, down, up, down, mid).second + query(root, down, up, mid + 1, up).second;}else {p = query(root, down, up, down, mid - 1).second + query(root, down, up, mid, up).second;}p = q - p;d = __gcd(p, q);printf("%lld/%lld\n", p / d, q / d);}else {scanf("%d%d", &v, &x);update(root, down, up, x, v);n += v;cnt[x] += v;}}}
}