解题思路
DP+乘法原理分析
树状数组实现查询
1.底层为a[i]
2.add(y,1)是将高度插进去
3.从1~n枚举,每次预处理出左侧大于的点数higher[i]和小于的点数lower[i]
树状数组
实现操作
只能求和
1. 快速求前缀和 $O(logn)$
2. 修改某一个数 $O(logn)$
实现原理
- 将一个区间拆为多个子区间
- 探究C数组间的关系
- 如何找到影响的父节点
- 树状数组的修改操作
- 树状数组的查询操作
查询:1~x for(int i=x;i;i-=lowbit(i)) tr[i]+=c
- 现有数组初始化
- 第一种方法(直接用函数):将原数组直接加入$O(nlogn)$
for(int i=1;i<=n;i++) add(i,a[i]);
- 第二种方式(求每个节点直接的儿子加上):$O(n)$
C++ for(int x = 1;x <= n;x ++) for(int i = x - 1;i >= x - lowbit(x) + 1;i -= lowbit(i)) tr[x] += tr[i];
- 第三种方法(定义):$O(n)$
使用前缀和,tr[i]=S[i]-S[i-lowbit(i)]
- 第一种方法(直接用函数):将原数组直接加入$O(nlogn)$
树状数组模板
int tr[N]; //所维护的数组
int lowbit(int x)
{
return x&-x;
}
// 修改某一个树
void add(int x,int c)
{
for(int i=x;i<=n;i+=lowbit(i))
tr[i]+=c;
}
//求前缀和
int sum(int x)
{
int res=0;
for(int i=x;i;i-=lowbit(i))
res+=tr[i];
return res;
}
AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=2e5+10;
int n;
int a[N];
LL tr[N];
LL higher[N];
LL lower[N];
int lowbit(int x)
{
return x&-x;
}
void add(int x,int c)
{
for(int i=x;i<=n;i+=lowbit(i))
tr[i]+=c;
}
LL sum(int x)
{
LL res=0;
for(int i=x;i;i-=lowbit(i))
res+=tr[i];
return res;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
int y=a[i];
higher[i]=sum(n)-sum(y-1);
lower[i]=sum(y-1);
add(y,1);
}
memset(tr,0,sizeof tr);
LL res1=0,res2=0;
for(int i=n;i;i--)
{
int y=a[i];
res1+=lower[i]*(sum(y-1));
res2+=higher[i]*(sum(n)-sum(y));
add(y,1);
}
cout<<res2<<" "<<res1;
return 0;
}