描述
在完成了分配任务之后，西部314来到了楼兰古城的西部。相传很久以前这片土地上(比楼兰古城还早)生活着两个部落，一个部落崇拜尖刀(‘V’)，一个部落崇拜铁锹(‘∧’)，他们分别用V和∧的形状来代表各自部落的图腾。
西部314在楼兰古城的下面发现了一幅巨大的壁画，壁画上被标记出了N个点，经测量发现这N个点的水平位置和竖直位置是两两不同的。西部314认为这幅壁画所包含的信息与这N个点的相对位置有关，因此不妨设坐标分别为(1,y1),(2,y2),…,(n,yn),其中y1~yn是1到n的一个排列。
西部314打算研究这幅壁画中包含着多少个图腾，其中V图腾的定义如下（注意：图腾的形式只和这三个纵坐标的相对大小排列顺序有关）1<=i<j<k<=n且yi>yj,yj<yk;
而崇拜∧的部落的图腾被定义为1<=i<j<k<=n且yi<yj,yj>yk;
西部314想知道，这n个点中两个部落图腾的数目。因此，你需要编写一个程序来求出V的个数和∧的个数。
输入格式
第一行一个数n
第二行是n个数，分别代表y1，y2……yn
输出格式
两个数
中间用空格隔开
依次为V的个数和∧的个数
样例输入
5
1 5 3 2 4
样例输出
3 4
数据范围与约定
- 10%的数据 n<=600
40%的数据 n<=5000
100%的数据 n<=200000，答案不超过int64
题解：1、倒序扫描序列 a，利用树状数组求出每个 a[i] 后边有几个数比它大，记为 r[i]；2、正序扫描序列 a，利用树状数组求出每个 a[i] 前边有几个数比它大，记为 l[i]。依次枚举每个点作为中间点，以该点为中心的 “ V” 字图腾个数显然是 r[i] * l[i]。同理可得 “ ^ ”字图腾的个数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
const int maxn = 200000+7;
ll a[maxn], n;
ll c[maxn];
ll r[maxn], l[maxn];
void init(){memset(c, 0, sizeof c);memset(r, 0, sizeof r);memset(l, 0, sizeof l);
}
ll lowbit(ll x){return x&-x;
}
ll get_sum(ll x){ll sum = 0;while(x){sum += c[x];x -= lowbit(x);}return sum;
}
void add(ll x, int val){while(x <= n){c[x] += val;x += lowbit(x);}
}
int main()
{scanf("%lld", &n);for(ll i = 1; i <= n; i++){scanf("%lld", &a[i]);}ll ansv = 0, ansn = 0;init();for(ll i = 1; i <= n; i++) {l[i] += get_sum(a[i]-1);add(a[i], 1);}memset(c, 0, sizeof c);for(ll i = n; i >= 1; i--){r[i] += get_sum(a[i]-1);add(a[i], 1);}for(ll i = 1; i <= n; i++)ansn += l[i]*r[i];init();for(ll i = 1; i <= n; i++) {l[i] += (i - 1 - get_sum(a[i]-1));add(a[i], 1);}memset(c, 0, sizeof c);for(ll i = n; i >= 1; i--){r[i] += ((n - i) - get_sum(a[i] - 1));add(a[i], 1);}for(ll i = 1; i <= n; i++)ansv += l[i]*r[i];printf("%lld %lld\n", ansv, ansn);return 0;
}