# [XSY2669] simple combinatorial mathematics of merging and sorting tree array

## Title Description

There is an array of length n=2k, and you want to merge and sort this array. But when the length is 2, there is a 12 probability to exchange two numbers (that is, there is a 12 probability to return the wrong result). There are two operations

1: exchange two numbers

2: ask the probability that a position after sorting is equal to a number.

k≤16,q≤105

## Title Solution

This sort is a little strange. Two numbers a, B (a < b) may be ab or ba after ranking.

It is observed that a b will rank normally, and a in ba will always follow b, so a can be regarded as b+0.5.

In this way, some numbers will be determined. Some numbers are one of two.

Use two tree arrays to maintain the small number and the large number no more than x number. Each query can be scrambled with combination number.

Time complexity: O((n+q)logn)

## Code

```#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void sort(int &a,int &b)
{
if(a>b)
swap(a,b);
}
void open(const char *s)
{
#ifndef ONLINE_JUDGE
char str[100];
sprintf(str,"%s.in",s);
freopen(str,"r",stdin);
sprintf(str,"%s.out",s);
freopen(str,"w",stdout);
#endif
}
int rd()
{
int s=0,c;
while((c=getchar())<'0'||c>'9');
do
{
s=s*10+c-'0';
}
while((c=getchar())>='0'&&c<='9');
return s;
}
void put(int x)
{
if(!x)
{
putchar('0');
return;
}
static int c[20];
int t=0;
while(x)
{
c[++t]=x%10;
x/=10;
}
while(t)
putchar(c[t--]+'0');
}
int upmin(int &a,int b)
{
if(b<a)
{
a=b;
return 1;
}
return 0;
}
int upmax(int &a,int b)
{
if(b>a)
{
a=b;
return 1;
}
return 0;
}
const ll p=1000000007;
ll fp(ll a,ll b)
{
ll s=1;
for(;b;b>>=1,a=a*a%p)
if(b&1)
s=s*a%p;
return s;
}
int n,a[100010];
int c1[200010];
int c2[200010];
{
for(;x<=2*n;x+=x&-x)
c[x]+=v;
}
int sum(int *c,int x)
{
int s=0;
for(;x;x-=x&-x)
s+=c[x];
return s;
}
int a1[100010];
int a2[100010];
int o(int x)
{
return ((x-1)^1)+1;
}
{
int y=o(x);
if(a[x]>a[y])
{
a1[x]=a2[x]=2*a[x]-1;
}
else
{
a1[x]=2*a[x]-1;
a2[x]=2*a[y];
}
}
ll inv[100010];
ll fac[100010];
ll ifac[100010];
ll c(int x,int y)
{
if(x<y)
return 0;
if(y<0)
return 0;
return fac[x]*ifac[y]%p*ifac[x-y]%p;
}
ll query(int x,int y,int b=0)
{
ll ans=1;
x--;
y--;
int s1=sum(c2,y);
int s2=sum(c1,y)-s1;
if(b)
s2--;
ans=ans*c(s2,x-s1)%p*fp(inv[2],s2)%p;
return ans;
}
int main()
{
open("c");
scanf("%d",&n);
int i;
inv[0]=inv[1]=fac[0]=fac[1]=ifac[0]=ifac[1]=1;
for(i=2;i<=n;i++)
{
inv[i]=-p/i*inv[p%i]%p;
fac[i]=fac[i-1]*i%p;
ifac[i]=ifac[i-1]*inv[i]%p;
}
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
int q;
scanf("%d",&q);
int op,x,y;
for(i=1;i<=q;i++)
{
scanf("%d%d%d",&op,&x,&y);
if(op==1)
{
swap(a[x],a[y]);
}
else
{
ll ans;
if(a1[x]==a2[x])
ans=query(y,a1[x]);
else
ans=(query(y,a1[x])+query(y,a2[x],1))*inv[2]%p;
ans=(ans+p)%p;
printf("%lld\n",ans);
}
}
return 0;
}```

Posted on Sun, 03 May 2020 17:06:29 -0700 by eroticheretic