树状数组:修改某个数;求前缀和
- 将第i个数加上k
- 输出区间[i,j]内每个数的和
每个区间C[R]=[R-lowbit(R)+1.R]
通过父节点找子节点:x-1,然后在x最后一个1之后所有的0都会变成1,这些连续的若干个1,每个1都会对应一个儿子,每次去掉一个1找到一个儿子,去k次可以找到k个儿子。
通过子节点找父节点:P=x+lowbit(x)。每一次修改完一个子节点,要修改他的父节点,再修改父节点的父节点....
修改:for(i=x;i<=n;i+=lowbit(i)) tr[i]+=c
查询:求1~x的和 for(i=x;i;i-=lowbit(i)) tr[i]-=c
其中,tr[i]表示以i结尾,长度为lowbit(i)的区间
#include <iostream>
#include <cstring>
using namespace std;
const int N=200010;
typedef long long ll;
int n,a[N],tr[N];
int high[N],low[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;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
//从做开始统计,此时(sum(n)-sum(y))为每个位置左边比第i个数y大的数的个数
for(int i=1;i<=n;i++)
{
int y=a[i];
//high[i]为从y+1到n的点中的方案数
high[i]=sum(n)-sum(y);
low[i]=sum(y-1);
add(y,1);
}
memset(tr,0,sizeof tr);
ll res1=0,res2=0;
//从右开始统计,此时(sum(n)-sum(y))为每个位置右边比第i个数y大的数的个数
for(int i=n;i;i--)
{
int y=a[i];
//每次res1加上右边比t大的数
res1 += high[i]*(ll)(sum(n)-sum(y));
res2 += low[i]*(ll)(sum(y-1));
add(y, 1);
}
cout<<res1<<" "<<res2;
return 0;
}