求助玄关树状数组（全RE）

zzh_KM @ 2024-10-18 21:03:05

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,s,ans,a[1000010],b[1000010],c[1000010],ord[1000010];
ll lbt(ll x){ return x&-x; }
void upd(ll pos,ll x)
{
    for(;pos<s;pos+=lbt(pos))c[pos]+=x;
    return;
}
ll query(ll l,ll r)
{
    ll tmp1=0,tmp2=0;
    for(l-=1;l>0;l-=lbt(l))tmp1+=c[l];
    for(;r>0;r-=lbt(r))tmp2+=c[r];
    return tmp2-tmp1;
}
int main()
{
    //freopen("P1908_1.in","r",stdin);
    //freopen("P1908_1.ans","w",stdout);
    //cout<<"wda";
    //read(n);
    cin>>n;
    //cout<<"WDA";
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    //cout<<"daww";
    sort(a+1,a+n+1);
    s=unique(a+1,a+n+1)-a;
    //cout<<s<<" ";
    for(int i=1;i<s;i++)
        ord[a[i]]=i;
    for(int i=1;i<=n;i++)
    {
        upd(ord[b[i]],1);
        ans+=query(ord[b[i]]+1,s-1);
        //cout<<ans<<" ";
    }
    cout<<ans;
    return 0;
}

by _shining @ 2024-10-18 21:27:42

给你一个模板，对着调吧，(没见过树状数组 \texttt{RE} 的。

#include <bits/stdc++.h>
using namespace std;
int n, m, l, r;
long long ans = 0;
int a[500005], c[500005], t[500005];
int lowbit(int x)
{
    return x & (-x);
}
int ask(int x)//区间[1,x]的前缀和
{
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
void add(int x, int d)//树状数组添加
{
    while(x <= n){
        c[x] += d;
        x += lowbit(x);
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], t[i] = a[i];
    //离散化
    sort(t + 1, t + n + 1);//排序
    int len = unique(t + 1, t + n + 1) - t - 1;//去重
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(t + 1, t + len + 1, a[i]) - t;//将原数重新标号
    }
    for(int i = n; i >= 1; i--){
        ans += ask(a[i] - 1);//求出序列后方比a[i]小的数量
        add(a[i], 1);//将数字加入树状数组
    }
    cout << ans;
    return 0;
}

by StarsIntoSea_SY @ 2024-10-18 21:36:02

@zzh_KM 请问您是照着哪篇题解写的？写了一个四不像。

RE 原因：a[i] \le10^9，36 行会越界

by zzh_KM @ 2024-10-18 21:37:29

已解决

by zzh_KM @ 2024-10-18 21:38:17

@StarsIntoSea_SY 没有看题解，算是自己写的吧，这个离散化的问题太蠢了，已关

by zzh_KM @ 2024-10-18 21:38:32

@_shining 已关

by _shining @ 2024-10-19 07:07:27

@zzh_KM 建议离散化用 \texttt{STL} 中的 lower\_bound 和 \texttt{unique} 实现，这样方便很多。