一些疑问
查看原帖
一些疑问
917775
_buzhidao_楼主2024/3/23 20:20

照着题解的第一份代码抄的。。。

#include<bits/stdc++.h>
using namespace std;
#define lb(x) (x&-x)
typedef long long ll;
template<typename T>inline void read(T &x){
	x=0;int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=f;
}
ll n,tmp,w[500005],t[500005],ans;
struct node{
	ll va;int idx;
} s[500005];
bool cmp(node x,node y){
	if(x.va==y.va) return x.idx<y.idx;
	return x.va<y.va;//1
}
void upd(int idx,ll val){
	for(;idx<=n;idx+=lb(idx)) t[idx]+=val;
}
ll query(int r){
	ll res=0;
	for(;r>0;r-=lb(r)) res+=t[r];
	return res;
}
int main(){
	read(n);
	for(int i=1;i<=n;++i) read(tmp),s[i].va=tmp,s[i].idx=i;
	sort(s+1,s+n+1,cmp);
	for(int i=1;i<=n;++i) w[s[i].idx]=i;
	for(int i=1;i<=n;++i){
		upd(w[i],1);
		ans+=i-query(w[i]);//2
	}cout<<ans;
	return 0;
}

想着如果排序时值用降序应该能过,于是把1处改成了 > 并将2处改成 query(w[i]),0分。
再把2处改成 query(w[i])-1,样例过,30分。
改成降序可不可以通过?如果可以,希望各位大佬提出解决方案;如果不可以,希望详细说明。

2024/3/23 20:20
加载中...