20200810 T2 dispatch money

Title Description

Give a length of $n$ Permutation $a_i$, Divide it into several paragraphs , Each segment is divided into $X$ The price of , After the division, the segment needs to be sorted , The cost is the number of inverse pairs of intervals . Find the minimum total cost .

$n\le 300000,1\le X\le 10^9$

time limit 5s.

Topic analysis

violence $O(n^2)$ DP：$f_i=f_j+inversion\_pair(j+1,i)$

Experienced OI Players can immediately guess the monotony of the decision , The proof is simple , The larger the interval, the faster the cost function grows , When in $i$ At the decision point $k$ Than the decision point $j$ Bad time （$k<j$）, stay $i^{\prime }>i$ It must be inferior to the latter .

However, the binary maintenance stack requires online calculation of the number of interval reverse pairs , This is a $n\sqrt{n}$ The problem of , You need to take a ride $\log$,300000 Obviously I can't run .

The divide and conquer method can be similar to that of Mo team , Use a tree array to maintain how many numbers are less than $x$, Add... When the decision point moves / Delete the front end of the section / Back end point , According to the process of divide and conquer, we can see that the number of times such an interval moves is $O(n\log n)$ Grade .

But divide and conquer should be based on the interval of decision points $f$ All known , So we need to put another one on the outer layer cdq Divide and conquer .
The sum $O(n{\log }^{3}n)$, But the constant is very small .

If you want to write strictly , It is a little troublesome to undo each time , After the actual test, it is not as fast as directly using the writing method similar to Mo's team , That is, if the current interval is not consistent with the query interval, move , Very easy to write .

Code：

#include<bits/stdc++.h>
#define maxn 300005
#define LL long long
using namespace std;
const LL inf = 0x3f3f3f3f3f3f3f3fll;
int n,X,a[maxn];
LL f[maxn];
int arr[maxn];
void upd(int i,int v){
    for(;i<=n;i+=i&-i) arr[i]+=v;}
int qsum(int i){
    int s=0;for(;i;i-=i&-i) s+=arr[i];return s;}
LL ask(int x,int y){
    
	static int l=1,r=0; static LL inver=0;
	while(l>x) l--,inver+=qsum(a[l]),upd(a[l],1);
	while(r<y) r++,inver+=r-l-qsum(a[r]),upd(a[r],1);
	while(l<x) upd(a[l],-1),inver-=qsum(a[l]),l++;
	while(r>y) upd(a[r],-1),inver-=r-l-qsum(a[r]),r--;
	return inver;
}
void solve2(int l,int r,int ql,int qr){
    
	if(ql>qr) return;
	int mid=(ql+qr)>>1,p=-1; LL mn=inf,tmp;
	for(int i=l;i<=r&&i<mid;i++)
		if((tmp=f[i]+ask(i+1,mid))<mn) mn=tmp,p=i;
	f[mid]=min(f[mid],mn+X);
	solve2(l,p,ql,mid-1),solve2(p,r,mid+1,qr);
}
void solve1(int l,int r){
    
	if(l==r) return;
	int mid=(l+r)>>1;
	solve1(l,mid);
	solve2(l,mid,mid+1,r);
	solve1(mid+1,r);
}
int main()
{
    
	freopen("dispatch.in","r",stdin);
	freopen("dispatch.out","w",stdout);
	scanf("%d%d",&n,&X);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=inf;
	solve1(0,n);
	printf("%lld\n",f[n]);
}

If you want to get stuck, you can try to upd The function is written as ++ and --, And in the cycle of finding the decision point, judge whether to follow the cycle or reverse the cycle according to the endpoint position .

There are also optimizations in solve1 The interval is smaller than the block size $S$ Sometimes violent , Length of pretreatment interval $\le S$ The reverse logarithm of , This one can $O(nS)$ Preprocessing , $w_{i,j}=w_{i,j-1}+w_{i+1,j}-w_{i+1,j-1}+[a_i>a_j]$

Expand

$O(n\sqrt{n})$ Find the number of inverse pairs of intervals .

Offline approach ：
Mo team , Consider moving endpoints without using a tree array , Instead, change the query range to be less than $x$ The number of . First run, Mo team , Get all this $O(n\sqrt{n})$ A asked .
The difference is to query a prefix less than $x$ The number of , Block the range , It is equivalent to a block prefix and an intra block prefix , Scan from front to back , After adding one number at a time $O(\sqrt{n})$ modify , The query is $O(1)$ Of .

Online practice ：
See WerKeyTom_FTD The blog of
The general idea is to preprocess the intra block contribution , Inter block contribution , When it is necessary to calculate the contribution between two cells, find the sorted situation in the interval through the pre ordered array in the block , And then merge .

The complexity of time and space is $O(n\sqrt{n})$ Of .