Guess the Weight
题意：
题目就是炉石的猜重量啦，不知道的同学可以先去玩炉石（bushi ）
题目就是初始给我们一堆牌，我们抽了第一张了之后，可以猜下一张是比第一张大还是小，如果猜对了，就可以获得第二张牌。我们采取最优策略，求能抽中第二张牌的概率。
只求概率的话，这道题就不是很难了，但是还有操作是可以往牌堆中加入 c c c张权值为 a a a的牌。
思路：
对于每一张牌，如果我们第一张抽它的话，猜的策略肯定是大的多的，或者少的多的。
那么可以看做一个有序对（ i i i， j j j）；
显然，这个序列有一个分界线，在这个分界线的左边选择比他大的，在这个分界线右边地选择小的。这个分界线把序列分成了两个部分。
如果有序对（ i i i， j j j）在两个不同的部分内，对答案的贡献是 2 ；
如果有序对（ i i i， j j j）在两个相同的部分内，对答案的贡献是 1 ；
如果有序对（ i i i， j j j）的权值相同的话，对答案的贡献是 0 ；
因为这道题正向考虑很难实现，那我们反向来维护。
先假设所有有序对的贡献都是 1 ，我们再加上少加的，再减去多加的。
那么首先假设的答案就是 t o t tot tot*( t o t tot tot - 1) / 2 ；
少加的部分就是跨块的权值，假设分界线是 x,那么权值就是 （sum1 ~ sum x）*（sum x+1 ~ sum n）;
多加的部分呢就是取权值相同的时候造成的，我们可以在加入的时候动态维护：
假设当前已经有了 a 个这样权值的数，加入了 x 个这样权值的数 ，那么多加的有序对数目呢就是
在a中选了一个，在x中选了一个，以及在x中选了两个和在a中选了两个的情况，因为我们是动态维护了，维护的值中 s a m e same same已经包含了 a中选两个的情况，那么我们只要把另外两中情况加上即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long longconst int maxn=100010,INF=1e9;
const ll mod=1e9+7;
ll qp(ll n,ll m){
ll ans=1;while(m){
if(m%2==1)ans=ans*n%mod;n=n*n%mod;m/=2;}return ans;
}
int n,m;
int t[800060];
ll tot=0;
ll same;
int sum[200010];
void build(int p,int l,int r){
t[p]=0;if(l==r)return;int mid=l+r>>1;build(2*p,l,mid);build(2*p+1,mid+1,r);
}
void update(int p,int l,int r,int x,int w){
t[p]+=w; if(l==r){
return;}int mid=l+r>>1;if(x<=mid)update(2*p,l,mid,x,w);else update(2*p+1,mid+1,r,x,w);
}
int query(int p,int l,int r,int x,int y){
if(l>r)return 0;if(x<=l&&r<=y)return t[p];int mid=l+r>>1;int ans=0;if(x<=mid)ans+=query(2*p,l,mid,x,y);if(mid<y)ans+=query(2*p+1,mid+1,r,x,y);return ans;
}
int main(){
int T;scanf("%d",&T);while(T--){
scanf("%d%d",&n,&m);same=0;memset(sum,0,sizeof sum);build(1,1,200000);tot=n;for(int i=1;i<=n;i++){
int a;scanf("%d",&a);update(1,1,200000,a,1);same+=sum[a];sum[a]++;}for(int i=1;i<=m;i++){
int x,w,op;scanf("%d",&op);if(op==1){
scanf("%d%d",&x,&w);update(1,1,200000,w,x);same+=1LL*sum[w]*x+x*(x-1)/2;sum[w]+=x;tot+=x;}else{
ll p1=tot*(tot-1)/2,p2=tot*(tot-1);int l=1,r=200000;while(l<r){
int mid=l+r+1>>1;int ans1=query(1,1,200000,1,mid-1);int ans2=query(1,1,200000,mid+1,200000);if(ans1<=ans2)l=mid;else r=mid-1;}p1+=1LL*query(1,1,200000,1,l)*query(1,1,200000,l+1,200000);p1-=same;ll g=__gcd(p1,p2);p1/=g;p2/=g;printf("%lld/%lld\n",p1,p2);}}}return 0;
}