AcWing241. 楼兰图腾

在完成了分配任务之后,西部314来到了楼兰古城的西部。

相传很久以前这片土地上(比楼兰古城还早)生活着两个部落,一个部落崇拜尖刀(‘V’),一个部落崇拜铁锹(‘∧’),他们分别用V和∧的形状来代表各自部落的图腾。

西部314在楼兰古城的下面发现了一幅巨大的壁画,壁画上被标记出了N个点,经测量发现这N个点的水平位置和竖直位置是两两不同的。

西部314认为这幅壁画所包含的信息与这N个点的相对位置有关,因此不妨设坐标分别为 ( 1 , y 1 ) , ( 2 , y 2 ) , … , ( n , y n ) (1,y_{1}),(2,y_{2}),…,(n,y_{n}) (1,y1),(2,y2),,(n,yn),其中 y 1   y n y_{1}~y_{n} y1 yn是1到n的一个排列。

西部314打算研究这幅壁画中包含着多少个图腾。

如果三个点 ( i , y i ) , ( j , y j ) , ( k , y k ) (i,y_{i}),(j,y_{j}),(k,y_{k}) (i,yi),(j,yj),(k,yk)满足 1 ≤ i < j < k ≤ n 1≤i<j<k≤n 1i<j<kn y i > y j , y j < y k y_{i}>y_{j},y_{j}<y_k yi>yj,yj<yk则称这三个点构成V图腾;

如果三个点 ( i , y i ) , ( j , y j ) , ( k , y k ) (i,y_{i}),(j,y_{j}),(k,y_{k}) (i,yi),(j,yj),(k,yk)满足 1 ≤ i < j < k ≤ n 1≤i<j<k≤n 1i<j<kn y i < y j , y j > y k y_{i}<y_{j},y_{j}>y_{k} yi<yj,yj>yk则称这三个点构成∧图腾;

西部314想知道,这n个点中两个部落图腾的数目。

因此,你需要编写一个程序来求出V的个数和∧的个数。

输入格式

第一行一个数n。

第二行是n个数,分别代表 y 1 , y 2 , … , y n y_{1},y_{2},…,y_{n} y1y2,,yn

输出格式

两个数,中间用空格隔开,依次为V的个数和∧的个数。

数据范围

对于所有数据, n ≤ 200000 n≤200000 n200000,且输出答案不会超过int64。
y 1 ∼ y n y_{1}∼y_{n} y1yn 是 1 到 n 的一个排列。

代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<algorithm>
#include<vector>
#include<utility>
#include<deque>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define mod 1000000007
#define endl '\n'
#define eps 1e-6
inline int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a; }
inline int lowbit(int x) {
    return x & -x; }


using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 200010;

int n, a[N], tr[N];
int greate[N], lower[N];


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)scanf("%d", &a[i]); //初始化原数组

	for (int i = 1;i <= n;++i) {
     //从左到右
		int y = a[i];
		greate[i] = sum(n) - sum(y);  //y左边比y大的数
		lower[i] = sum(y - 1); //y左边比y小的数
		add(y, 1); //在当前位置插入1
	}
	memset(tr, 0, sizeof tr);
	LL res1 = 0, res2 = 0;
	for (int i = n;i;--i) {
    //从右到左
		int y = a[i]; 
		res1 += greate[i] * (LL)(sum(n) - sum(y)); // y右边比y大的数
		res2 += lower[i] * (LL)(sum(y - 1)); // y右边比y小的数
		add(y, 1); //当前位置插入1
	}

	cout << res1 << " " << res2 << endl; //输出答案

	return 0;
}