救命
查看原帖
救命
594257
sad_desert楼主2022/7/31 15:19
#include<iostream>
#include<algorithm>
using namespace std;
struct ppp{
	string m;
	int b;
}a[100009],b[100009];
inline string read(){
	char c=getchar();
	string a="";
	while(c!=' '&&c!='\n'){
		a+=c;
		c=getchar();
	}
	return a;
}
bool cmp(ppp a,ppp b){
	return a.m<b.m;
}
long long c[100000],ans,n,L,R,mid;
void msort(int l,int e){
    if(l>=e)  
		return;
    long long mid=(l+e)/2,i=l,j=mid+1,k=l;
    msort(l,mid);
	msort(mid+1,e);
    while(i<=mid&&j<=e){
   		if(b[i].b<=b[j].b)
    		c[k++]=b[i++].b;
    	else{
    		c[k++]=b[j++].b;
			ans+=mid-i+1;
		}
	}
    while(i<=mid)
    	c[k++]=b[i++].b ;
    while(j<=e)
    	c[k++]=b[j++].b ;
    for(int t=l;t<=e;t++)
    	b[t].b=c[t];
}
int main(){
	cin>>n;
	char ppppp=getchar();
	for(int i=1;i<=n;i++){
		a[i].m=read();
		a[i].b=i;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		b[i].m=read();
		L=0,R=n;
		while(L<R-1){
			mid=(L+R)/2;
			if(a[mid].m>b[i].m){
				R=mid;
			}else{
				L=mid;
			}
		}
		b[i].b=a[R].b;
	}
//	for(int i=1;i<=n;i++)
	//	cout<<b[i].b<<endl;
	msort(1,n);
	cout<<ans;
}
2022/7/31 15:19
加载中...