树状数组全RE求助

P1908 逆序对

BlachSnake @ 2021-03-18 19:23:43

#include<algorithm>
#include<stdio.h>
#include<ctype.h>
#define int long long
namespace io{
    int Read(){
        char c=getchar();
        int x=0,d=1;
        while(!isdigit(c)){
            if(c=='-')d=-1;
            c=getchar();
        }
        while(isdigit(c))
            x=x*10-48+c,c=getchar();
        return x*d;
    }
    void pr(int x){
        if(!x)return;
        pr(x/10);
        putchar(x%10+48);
    }
    void Print(int x){
        if(x){
            if(x<0)x=-x,putchar('-');
            pr(x);
        }
        else putchar('0');
        putchar('\n');
    }
}
using namespace io;
using std::sort;
const int N=555555;
struct node{
    int id,val;
    inline bool operator<(const node &x)const{return val<x.val;}
}a[N];
int n;
class Fenwick_Tree{
private:
    int t[N];
    #define lowbit(x) x&-x
    #define ub(x) x+=lowbit(x)
    #define db(x) x-=lowbit(x)
public:
    void Change(int x){
        while(x<=n)t[x]++,ub(x);
    }
    int Query(int x){
        int s=0;
        while(x)s+=t[x],db(x);
        return s;
    }
};
Fenwick_Tree QwQ;
signed main(){
    int s=0;
    n=Read();
    for(int i=1;i<=n;i++)a[i]=(node){Read(),i};
    sort(a+1,a+n+1);
    for(int i=n;i>0;i--)QwQ.Change(a[i].id),s+=QwQ.Query(a[i].id-1);
    Print(s);
    return 0;
}

RT,求调QwQ


by BlachSnake @ 2021-03-18 19:44:50

Read()炸了……此帖终结


|