P4769-[noi2018] bubble sort [combinatorics, tree array]

On the subject

Topic link :https://www.luogu.com.cn/problem/P4769

---

The main idea of the topic

There is a bubble sort algorithm

 Input ： A length of  n  Permutation  p[1...n]
 Output ：p  The result after sorting .
for i = 1 to n do
	for j = 1 to n - 1 do
		if(p[j] > p[j + 1])
			 In exchange for  p[j]  And  p[j + 1]  Value 

Then give an arrangement $a$, Find the order greater than in all dictionaries $a$ Permutation $p$ The number of bubble sort exchanges in is exactly ${\sum }_{i=1}^n|i-p_i|$ Number of permutations of .

$1\le n\le 6\times 10^5,\sum n\le 2\times 10^6$

---

Their thinking

It is found that the legal arrangement condition is that the longest descending subsequence does not exceed $2$.

Then let's not consider what the lexicographic order constraint does , We set up $f_{i,1/2}$ Indicates that the current descending subsequence length is $1/2$ The biggest one at the end of the middle .

that $f_{i,1}$ It is the largest number in the world , Then if we fill in the numbers from front to back , So if $\le f_{i,2}$ Is there anything in the number of , It's definitely not legal , therefore $f_{i,2}$ It must be smaller than all the figures that have not been filled in at present , There is no need to consider .

set up $g_{i,j}$ It means that there are still $i$ The number is not filled in , among $f_{i,1}$ Greater than $j$ Number , So there are $g_{i,j}$ Can be transferred to $g_{i-1,j-1}$（ Fill in the bottom ） and $g_{i-1,k}(k\ge j)$（ Fill in $j$ above ）.

We consider quickly finding each $g$, The reverse is $g_{i,j}$ Transferred to the $g_{i+1,j+1}$ and $g_{i+1,j}$.

We maintain a $h_{i,j}=g_{i,i-j}$, So every shift is $h_{i,j}$ Transferred to the $h_{i,k}(j\le k\le i)$

This transfer is very much like the Cartland number , You can go down or right each time , But not beyond the diagonal .

So move to position $(n,m)(m\le n)$ The number of schemes is $\left(\genfrac{}{}{0ex}{}{n+m}{m}\right)-\left(\genfrac{}{}{0ex}{}{n+m}{m-1}\right)$.

Then it enumerates the first position beyond the dictionary order , So the previous scheme is fixed , The remaining number can be calculated from the tree array , Then use the combination number to find the answer .

Time complexity ：$O(n\log n)$

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define lowbit(x) (x&-x) 
using namespace std;
const ll N=6e5*2,P=998244353;
ll T,n,t[N],a[N],fac[N],inv[N],ans;
ll C(ll n,ll m)
{
    if(m<0)return 0;return fac[n]*inv[m]%P*inv[n-m]%P;}
void Change(ll x,ll val){
    
	while(x<=n){
    
		t[x]+=val;
		x+=lowbit(x);
	}
	return;
}
ll Ask(ll x){
    
	ll ans=0;
	while(x){
    
		ans+=t[x];
		x-=lowbit(x);
	}
	return ans;
}
ll F(ll n,ll m){
    
	m=n-1-m;if(!m)return 0;m--;
	return (C(n+m,m)-C(n+m,m-1)+P)%P;
}
signed main()
{
    
// freopen("inverse3.in","r",stdin);
	fac[0]=inv[0]=inv[1]=1;
	for(ll i=2;i<N;i++)inv[i]=P-inv[P%i]*(P/i)%P;
	for(ll i=1;i<N;i++)fac[i]=fac[i-1]*i%P,inv[i]=inv[i-1]*inv[i]%P;
	scanf("%lld",&T);
	while(T--){
    
		scanf("%lld",&n);ans=0;
		for(ll i=1;i<=n;i++)
			scanf("%lld",&a[i]),Change(a[i],1);
		for(ll i=1,mx=0;i<=n;i++){
    
			Change(a[i],-1);mx=max(mx,a[i]);
			(ans+=F(n-i+1,Ask(mx)))%=P;
			if(a[i]<mx&&Ask(a[i]))
				break;
		}
		for(int i=1;i<=n;i++)t[i]=0;
		printf("%lld\n",ans);
	}
	return 0; 
}