为啥全re了啊

溪水瑶 @ 2019-08-07 15:45:57

#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int n,a[N<<1],c[N<<1],ans;
int ask(int x)
{
    int sum=0;
    for(;x;x-=x&-x)sum+=c[x];
    return sum;
}
void add(int x,int y){
    for(;x<=N;x+=x&-x)c[x]+=y;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i;i--)
    {
        ans+=ask(a[i]-1);
        add(a[i],1);
    }
    cout<<ans<<endl;
}

by yu__xuan @ 2019-08-07 16:05:36

@溪水瑶 树状数组求逆序对不是要离散化吗？

by 溪水瑶 @ 2019-08-07 16:06:09

@yu__xuan 哦，这样的啊

by 溪水瑶 @ 2019-08-07 16:06:32

那为啥会re呀

by yu__xuan @ 2019-08-07 16:07:31

@溪水瑶 a[i]可能很大

by 溪水瑶 @ 2019-08-07 16:08:19

@yu__xuan 不是不超过10^9吗

by yu__xuan @ 2019-08-07 16:10:16

@溪水瑶 空间能开这么大吗？

by 溪水瑶 @ 2019-08-07 16:10:51

而且为啥是全都re呀。至少对那么一两个呗

by 溪水瑶 @ 2019-08-07 16:11:28

两个五十万不能的吗？？

by yu__xuan @ 2019-08-07 16:12:49

左移1相当于×2

by 溪水瑶 @ 2019-08-07 16:13:03

@yu__xuan 我改成两个五十万的数组了