巨佬帮帮我TT

P1908 逆序对

d3ac @ 2019-05-10 09:41:33

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define re register
using namespace std;
const int maxn=5e5+5;
int a[maxn],b[maxn],tree[maxn<<2],n;
long long ans;
inline int read(){
    re int x=0,f=1;re char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool cmp(int x,int y){return b[x]>b[y];}//这样排序就是把a[i]对应的就是b数组里面的第i个最大 
void add(int x)
{
    while(x<=n)
    {
        tree[x]++;
        x+=x&-x;
    }
}
int sum(int x)
{
    re int SUM=0;
    while(x)
    {
        SUM+=tree[x];
        x-=x&-x;
    }
    return SUM;
}
int main()
{
    n=read();
    for(re int i=1;i<=n;i++) b[i]=read(),a[i]=i;
    sort(a+1,a+1+n,cmp);
    for(re int i=1;i<=n;i++)
    {
        add(a[i]);
        ans+=sum(a[i]-1);//不能包括自己 
    }
    printf("%d",ans);
    return 0;
}

by d3ac @ 2019-05-10 09:41:56

这个真的找不出错


by xcxcli @ 2019-05-10 09:58:02

@ღ觊觎微凉月 树状数组也要开long long


by d3ac @ 2019-05-10 10:02:41

还是WA了TT怎么办@xzxxcx


by d3ac @ 2019-05-10 10:03:43

@xcxxcx 还是WA了TT怎么办


by BinDir0 @ 2019-05-10 10:04:44

@ღ觊觎微凉月 头像好评qwq卡莲


by d3ac @ 2019-05-10 10:06:35

@恨妹不成穹 哈哈哈哈哈哈哈qwq


by BinDir0 @ 2019-05-10 10:18:47

@ღ觊觎微凉月 我想要您头像的那个女武神qaq


by OI圈最弱小蒟蒻 @ 2019-05-10 10:38:22

@ღ觊觎微凉月 您把sum函数的返回值也改long long试下


by d3ac @ 2019-05-10 11:08:05

@OI圈最弱小蒟蒻 放弃了。。。。。


by OI圈最弱小蒟蒻 @ 2019-05-10 11:24:25

@ღ觊觎微凉月 ...


|