权值线段树25pts求条

AlexandreLea @ 2024-01-25 15:28:09

#include <bits/stdc++.h>
using namespace std;
int n,a[2510],val[800010],ch[800010][2],rt,totut,ans;
void modify(int &u,int ul,int ur,int p,int k){
    if(u==0) u=++totut;
    if(ul==ur) return val[u]+=k,void();
    int um=ul+(ur-ul)/2;
    if(p<=um) modify(ch[u][0],ul,um,p,k);
    else modify(ch[u][1],um+1,ur,p,k);
    val[u]=val[ch[u][0]]+val[ch[u][1]];
}
int query(int u,int ul,int ur,int ql,int qr){
    if(u==0) return 0;
    if(ql<=ul&&ur<=qr) return val[u];
    int ans=0,um=ul+(ur-ul)/2;
    if(ql<=um) ans+=query(ch[u][0],ul,um,ql,qr);
    if(um<qr) ans+=query(ch[u][1],um+1,ur,ql,qr);
    return ans;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i){
        ans+=query(rt,1,1e9,a[i]+1,1e9);
        modify(rt,1,1e9,a[i],1);
    }
    cout<<ans<<endl;
    return 0;
}

by AlexandreLea @ 2024-01-25 15:36:57

现在50pts，MLE：

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,a[500010],val[7000010],ch[7000010][2],rt,totut,ans;
void modify(int &u,int ul,int ur,int p,int k){
    if(u==0) u=++totut;
    if(ul==ur) return val[u]+=k,void();
    int um=ul+(ur-ul)/2;
    if(p<=um) modify(ch[u][0],ul,um,p,k);
    else modify(ch[u][1],um+1,ur,p,k);
    val[u]=val[ch[u][0]]+val[ch[u][1]];
}
int query(int u,int ul,int ur,int ql,int qr){
    if(u==0) return 0;
    if(ql<=ul&&ur<=qr) return val[u];
    int ans=0,um=ul+(ur-ul)/2;
    if(ql<=um) ans+=query(ch[u][0],ul,um,ql,qr);
    if(um<qr) ans+=query(ch[u][1],um+1,ur,ql,qr);
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n;++i){
        ans+=query(rt,1,1e9,a[i]+1,1e9);
        modify(rt,1,1e9,a[i],1);
    }
    cout<<ans<<endl;
    return 0;
}

by ScaredQiu @ 2024-01-25 17:56:47

@Jasminoides query 写错了。

by AlexandreLea @ 2024-01-25 21:29:05

@ScaredQiu /thx

by qzmoot @ 2024-05-03 16:04:22

@Jasminoides 好好好，你是真无聊

by AlexandreLea @ 2024-05-03 18:22:35

@qzmoot 别召唤我我死了

by qzmoot @ 2024-05-03 18:25:21

@Jasminoides 不！！那你怎么还上洛谷