2022 Henan Mengxin League game (3): Henan University B - reverse pair count

B - Count in reverse order

solution : First , For a permutation , If the interval is reversed , The number in reverse order is equal to all the plants in the area
Logarithm minus the current reverse logarithm , That is, the original positive sequence pair becomes the reverse sequence pair , Original inverse
Sequence pairs become positive sequence pairs . If for each position, record its inverse to all subsequent positions
This problem can be solved by pairing the numbers in sequence , Consider from $[l,r]\to [l,r+1]$ The number of reverse pairs increases
Add interval $[l,r]$ Middle ratio $a_r+1$ The number of , So you can make statistics in advance for each
Location , To each position in front of him, how many numbers are bigger than him , Directly after statistics
Calculate the reverse order pair .

• Time complexity $O(n^2)$

Of course, you can also use a tree array to count reverse pairs , You can pass this question well .

• Time complexity approximation $O(n^2)$

#include<cstdio>
#include<cstring>

const int N = 6010;
int a[N],tr[N],f[N][N],g[N][N];
int n;

inline int lowbit(int x)
{
    
	return x&-x;
}

inline void add(int x,int y)
{
    
	for(int i=x;i<=n;i+=lowbit(i))
		tr[i]+=y;
}

inline int query(int x)
{
    
	int res=0;
	for(int i=x;i>0;i-=lowbit(i))
		res+=tr[i];
	return res;
}

int main()
{
    
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
	{
    
		for(int j=i;j<=n;j++)
		{
    
			f[i][j]=f[i][j-1]+query(n)-query(a[j]-1);
			g[i][j]=g[i][j-1]+query(a[j]);
			add(a[j],1);
		}
		memset(tr,0,sizeof tr);
	}
	
	int q;scanf("%d",&q);
	while(q--)
	{
    
		int l,r;scanf("%d%d",&l,&r);
		printf("%d\n",f[1][n]-f[l][r]+g[l][r]);
	}
	return 0;
}