一些疑问

P1908 逆序对

_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分。
改成降序可不可以通过?如果可以,希望各位大佬提出解决方案;如果不可以,希望详细说明。


|