- 技术
- 珂朵莉的数列（树状数组）
思路:对于a[L]>a[R] L<R 逆序数对所被包含的区间是左端点(1——L)到右端点（R——n）所以他的贡献是L*(n-r+1)我们用树状数组去求逆序数对，答案会爆ll用int128
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1e4+7;
const int N
=1e6+10;
const int inf
=0x7f7f7f7f;
ll
gcd(ll a
,ll b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
ll a
[N
],b
[N
];
vector
<int> vt
;
int getid(int x
)
{
return lower_bound(vt
.begin(),vt
.end(),x
)-vt
.begin()+1;
}
int lowbit(int x
)
{
return x
&-x
;
}
void add(int x
,int k
)
{
while(x
<N
)
{
b
[x
]+=k
;
x
+=lowbit(x
);
}
}
ll
sum(int x
)
{
ll ans
=0;
while(x
>0)
{
ans
+=b
[x
];
x
-=lowbit(x
);
}
return ans
;
}
void print(__int128 x
)
{
if(x
<10)
{
putchar(x
%10+'0');
return ;
}
print(x
/10);
putchar(x
%10+'0');
}
int main()
{
int n
;
cin
>>n
;
for(int i
=1;i
<=n
;i
++){
cin
>>a
[i
];
vt
.push_back(a
[i
]);
}
sort(vt
.begin(),vt
.end());
vt
.erase(unique(vt
.begin(),vt
.end()),vt
.end());
__int128 ans
=0;
for(ll i
=1;i
<=n
;i
++)
{
int pos
=getid(a
[i
]);
ans
+=(ll
)(sum(N
-1)-sum(pos
))*(n
-i
+1);
add(pos
,i
);
}
print(ans
);
return 0;
}
Processed:
0.010, SQL:
9
