题目描述
AcWing 241.楼兰图腾 https://www.acwing.com/problem/content/description/243/
解题思路
线段树+桶标记
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
int n;
int a[200010];
int tree[200010];//树状数组
int small[200010];//前i个数中比a[i]小的有多少个
int big[200010];//前i个数中比a[i]大的有多少个
//计算x的二进制表示中100...后缀是多少
int lowbit(int x)
{
return x & (-x);
}
//计算tree[1]...tree[x]的和
int add(int x)
{
int sum = 0;
while (x > 0)
{
sum += tree[x];
x -= lowbit(x);
}
return sum;
}
//tree[x]及其父结点都+1, 代表x出现一次
void ask(int x)
{
while (x <= n)
{
tree[x] += 1;
x += lowbit(x);
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
//正向
for (int i = 1; i <= n; i++)
{
ask(a[i]); //在tree中标记a[i]
small[i] = add(a[i] - 1); //a[1]...a[i-1]中比a[i]小的数有多少个
big[i] = add(n) - add(a[i]);//a[1]...a[i-1]中比a[i]大的数有多少个
}
memset(tree, 0, sizeof(tree)); //tree清空
long long A = 0, V = 0;
for (int i = n; i >= 1; i--) //逆向
{
ask(a[i]); //在tree中标记a[i]
A += 1ll * small[i] * add(a[i] - 1); //small[i] * a[n]...a[i+1]中比a[i]小的数有多少个
V += 1ll * big[i] * (add(n) - add(a[i])); //big[i] * a[n]...a[i+1]中比a[i]大的数有多少个
}
cout << V << ' ' << A << endl;
return 0;
}