Hangzhou Electric Zhongchao 91006 guess the weight

Guess the Weight

The question ：
The question is how to guess the weight of the hearthstone , Students who don't know can play Firestone first （bushi ）
The problem is to give us a stack of cards at the beginning , After we took the first one , You can guess whether the next one is bigger or smaller than the first one , If you're right , You can get the second card . We adopt the optimal strategy , Find the probability of winning the second card .
Just ask for probability , This problem is not very difficult , But there are operations that can be added to the deck $c$ Zhang Weiwei $a$ The card of .
Ideas ：
For each card , If we draw it first , The guessing strategy must be much larger , Or much less .
Then it can be regarded as an orderly pair （$i$,$j$）;
obviously , This sequence has a dividing line , On the left side of the dividing line, choose the one larger than him , Select the small one on the right side of the dividing line . This dividing line divides the sequence into two parts .
If order is right （$i$,$j$） In two different parts , The contribution to the answer is 2 ;
If order is right （$i$,$j$） In two identical parts , The contribution to the answer is 1 ;
If order is right （$i$,$j$） If the weight of is the same , The contribution to the answer is 0 ;
Because it is difficult to realize the positive consideration of this problem , Let's maintain in reverse .
Let's assume that the contribution of all ordered pairs is 1 , Let's add a little , Subtract the extra .
So the first hypothetical answer is $tot$*($tot$ - 1) / 2 ;

The less added part is the cross block weight , Suppose the dividing line is x, So the weight is （sum1 ~ sum x）*（sum x+1 ~ sum n）;
The extra part is caused when the weight is the same , We can maintain dynamically when we join ：
Let's say we have a The number of such weights , Joined the x The number of such weights , So the number of ordered pairs of addition is
stay a One of them is , stay x One of them is , And in x Choose two and in a Two cases are selected , Because we maintain it dynamically , Maintained values $same$ Already included a In the case of two of them , Then we just add the other two cases .

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const 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;
}