hihocoder 1926
程序员文章站
2022-06-16 11:06:19
...
我对公式的理解就是,当i<j且a[i]>a[j]时,会出现一对逆序对,i和j分别向左右延伸,根据乘法原理,ans的贡献就是图片那个,剩下的就是树状数组求逆序对了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<cmath>
#include<map>
#include<string>
#include<queue>
#include<stack>
#include<bitset>
#include<list>
#include<set>
#include<utility>
#include<iomanip>
#define IO ios::sync_with_stdio(false)
#define eps 1e-7
#define int long long
using namespace std;
int c[100000+5],n,a[100000+5],ans;
void add(int x,int y)
{
for(;x<=n;x+=x&-x)
{
c[x]+=y;
}
}
int ask(int x)
{
int ans=0;
for(;x;x-=x&-x)
{
ans+=c[x];
}
return ans;
}
signed main()
{
IO;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=n;i>=1;i--)
{
int x=ask(a[i]-1);
ans+=i*x;
add(a[i],n-i+1);
}
cout<<ans;
}
上一篇: 也许需要高手才能解决,关于抓取
下一篇: 数组中的逆序对(思路与实现)
推荐阅读
-
K Seq HihoCoder - 1046 || BZOJ4504 k个串
-
HihoCoder#1279 : Rikka with Sequence(dp 枚举子集 二进制 神仙题)
-
HihoCoder#1509 : 异或排序(二进制)
-
CSUFT 个人赛(2) C题(POJ - 1316) D题(HDU - 2076) G题(HihoCoder - 1740) H题(HDU - 5640)
-
hihocoder1032最长回文子串 [Manacher]
-
HihoCoder - 1142 三分·三分求极值
-
HihoCoder#1513 : 小Hi的烦恼(五维数点 bitset 分块)
-
hihocoder 1926
-
hihocoder#1476 : 矩形计数
-
HihoCoder-1174拓扑排序