离散化10分求助
查看原帖
离散化10分求助
320449
forest114514楼主2023/8/1 15:42

为什么lower_bound不行呀?

//蒟蒻一枚
#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-x))
#define int long long 
using namespace std;
typedef long long LL;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch&15),ch=getchar();
	return x*f;
}
const int N=1e5+10;
int n,mod=1e8-3;
struct stick{
	int a,b;
}ll[N];
bool cmp(stick A,stick B){return A.b<B.b;}
bool cmp2(int a,int b){return a<b;}
int cl[N],cntl,f[N];
LL ans=0;
void update(int u,int k){while(u<=n)f[u]+=k,u+=lowbit(u);}
LL query(int u){
	LL res=0;
	while(u)res+=f[u],u-=lowbit(u);
	return res;
}
signed main(){
	//ios::sync_with_stdio(false);
	n=read();
	for(int i=1;i<=n;++i) ll[i].a=read();
	for(int i=1;i<=n;++i) ll[i].b=read();
	sort(ll+1,ll+1+n,cmp);
	for(int i=1;i<=n;i++) cl[i]=ll[i].a;
	sort(cl+1,cl+1+n,cmp2);
	for(int i=n;i>=1;--i){
		int u=lower_bound(cl+1,cl+1+n,ll[i].a)-cl;
		ans=(ans+query(u-1))%mod;
		update(u,1);
	}
	printf("%lld\n",ans);
	return 0;
}

样例能过,有没有大佬能解答一下为啥?

2023/8/1 15:42
加载中...