ABC 261 F - Sorting Color Balls (reverse pair)

ABC 261 F - Sorting Color Balls(逆序对)

Regardless of color,The minimum number of times that the adjacent swaps complete the sorting is the inverse logarithm.

The proof is that the number of times the largest number is moved to the end is the reverse logarithm,Then the next largest value、And so on until the minimum value.

Consider color,Therefore, we can subtract the inverse numbers of the same color.

那么答案就是：$ans=to{t}_{reverse}-to{t}_{co{l}_i}$

We start with each colorvector存,Then run the reverse order pair.

Finally, run the whole side in reverse order.

reverse order$BIT$ 即可.

时间复杂度：$O(nlogn)$

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,x[N],c[N],tr[N];
vector<int>V[N];
long long rs;
void Ad(int i,int w){
    
	for(;i;i-=i&-i)tr[i]+=w;
}
int Qr(int i){
    
	int rs=0;
	for(;i<=n;i+=i&-i)rs+=tr[i];
	return rs;
}
int main(){
    
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
    
		scanf("%d",&c[i]);
		V[c[i]].push_back(i);
	}
	for(int i=1;i<=n;++i)scanf("%d",&x[i]);
	for(int i=1;i<=n;++i){
    
		int l=V[i].size();
		for(int o=0;o<l;++o){
    
			rs-=Qr(x[V[i][o]]+1);
			Ad(x[V[i][o]],1);
		}
		for(int o=0;o<l;++o)Ad(x[V[i][o]],-1);
	}
	for(int i=1;i<=n;++i){
    
		rs+=Qr(x[i]+1);
		Ad(x[i],1);
	}
	printf("%lld\n",rs);
	return 0; 
}