求助
查看原帖
求助
370037
_farawaystar_楼主2022/11/17 11:46
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define N 200005
#define int long long
using namespace std;
int n,m,val[N],e[N],ans,sum;
struct node{
	int tx,x,v;
}a[N];
struct tree{
	int num,val;
}tr[N*4];
bool cmp(node x1,node x2){
	return x1.tx<x2.tx;
}
bool cmp2(node x1,node x2){
	return x1.v<x2.v;
}
void add(int l,int r,int x,int val){
	if(l==r){
		tr[x].val+=e[val];
		tr[x].num++;
		return;
	}
	int mid=(l+r)>>1;
	if(val<=mid)add(l,mid,x*2,val);
	else add(mid+1,r,x*2+1,val);
	tr[x].val=tr[x*2].val+tr[x*2+1].val;
	tr[x].num=tr[x*2].num+tr[x*2+1].num;
}
int ask(int l,int r,int x,int val,int val2){
	if(l==r)return val2*tr[x].num-tr[x].val;
	int mid=(l+r)>>1;
	if(val<=mid)return ask(l,mid,x*2,val,val2);
	return ask(mid+1,r,x*2+1,val,val2)+val2*tr[x*2].num-tr[x*2].val;
}
signed main(){
//	freopen("1.in","r",stdin); 
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i].tx);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i].v);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(a[i].tx==a[i-1].tx)a[i].x=a[i-1].x;
		else a[i].x=++sum;
		e[a[i].x]=a[i].tx;
	}
	sort(a+1,a+n+1,cmp2);
	for(int i=1;i<=n;i++){
		ans+=ask(1,sum,1,a[i].x,a[i].tx); 
		add(1,sum,1,a[i].x);
	}
	cout<<ans<<endl;
	return 0;
}

简单线段树,求调,3个样例都过了QAQ

谢谢大佬们了快调哭了

补充:可能只有数据很大的时候会挂

2022/11/17 11:46
加载中...