_buzhidao_ @ 2024-03-23 20:20:11
照着题解的第一份代码抄的。。。
#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分。
改成降序可不可以通过?如果可以,希望各位大佬提出解决方案;如果不可以,希望详细说明。