80分求调
查看原帖
80分求调
893608
cx2021ghj楼主2024/10/12 16:48
#include<bits/stdc++.h>
#define mod 99999997
#define int long long
using namespace std;
struct ghj{
	int val,id;
};
ghj a[200009],b[20009];
int tree[200009],n,q[200009],ans;
bool cmp(const ghj&a,const ghj&b){
	return a.val<b.val;
}
int lowbit(int x){
	return x & -x;
}
void update(int x){
	while(x<=n){
		tree[x]++;
		tree[x]%=mod;
		x+=lowbit(x);
	}
}
int query(int x){
	int res=0;
	while(x>0){
		res+=tree[x];
		res%=mod;
		x-=lowbit(x);
	}
	return res%mod;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i].val,a[i].id=i;
	for(int i=1;i<=n;i++) cin>>b[i].val,b[i].id=i;
	sort(a+1,a+1+n,cmp);
	sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;i++) q[a[i].id]=b[i].id;
	for(int i=n;i>=1;i--){ 
		update(q[i]); 
		ans=(ans+query(q[i]-1))%mod; 
	} 
	cout<<ans%mod; 
}
2024/10/12 16:48
加载中...