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()炸了……此帖终结