树状数组作用:
1.快速求前缀和O(log n)
2.修改某一个数O(log n)
lowbit:
int lowbit(int x)
{
return x&-x;
}
查询:
for(int i=x;i;i-=lowbit(i)) sum+=tr[i];
更改:
for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
对于本题:
思路:
1.分成n类,每类可以以每个点为界限,找左边比自己大的*右边比自己大的,累加求的 V 的值。
2.y1∼yn
是 1 到 n 的一个排列,即y的取值是在[1,n]且每一个y不重复。
3.将y的值看成 tr数组的下标,因此求出来的sum[x]值,就是从小于x数个数。
4.注意long long
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long LL;
const int N= 2*1e5+10;
int n;
int a[N],great[N],lower[N],tr[N];
int lowbit(int x)
{
return x&-x;
}
int sum(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
res+=tr[i];
return res;
}
void add(int x)
{
for(int i=x;i<=n;i+=lowbit(i))
tr[i]++;
return;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
great[i]=sum(n)-sum(a[i]); //看值在a[i]~n,一共有多少个数
lower[i]=sum(a[i]); //看值在1~a[i],一共有多少个数
add(a[i]);
}
memset(tr,0,sizeof tr);
LL resv=0,resM=0;
for(int i=n;i>0;i--)
{
resv+=great[i]*1LL*(sum(n)-sum(a[i]));
resM+=lower[i]*1LL*(sum(a[i]));
add(a[i]);
}
cout<<resv<<" "<<resM<<endl;
}
写字好好看呀
哈哈哈哈
有点认真
这字也太好看了⑧
hh
题解又细(详细,字还好看,不赞过意不去了
hh,谢谢
为什么输入的时候就插入add(a[i])
而是边求边插入,我感觉我还是好晕。
lowbit是捞逼的意思吗,
没想到我的名字会出现在大佬的代码里大佬,您您您别谦虚了
图赞一个
hh,谢谢
大佬图层怎么做的,用的什么软件啊
画图软件