小奇遐想(树状数组)

小奇遐想

时间限制: 1 Sec  内存限制: 128 MB

题目描述

撷来一缕清风飘渺
方知今日书信未到
窗外三月天霁垂柳新长枝条
风中鸟啼犹带欢笑
——《清风醉梦》
小奇望着青天中的悠悠白云，开始了无限的遐想，在它的视野中，恰好有n朵高度不同的白云排成一排，他想从左到右选出四朵白云a，b，c，d，使得h_a<h_b<h_d<h_c，即看起来像是彩虹的形状！它想知道有多少种方案数。

输入

第一行包括1个整数n。
第二行包括n个整数，第i个正数表示h_i，保证这n个整数是n的一个全排列。

输出

输出一个整数表示答案。（mod 16777216）

样例输入

复制样例数据

5
1 5 3 2 4

样例输出

0

提示

对于10%的数据n<=600；对于40%的数据n<=5000；
对于100%的数据n<=200000。

先统计a<b<c<d与a<b<d<c的情况，再减去a<b<c<d时的情况，根据树状数组统计比变量b小的大的数。

#include<bits/stdc++.h>

typedef long long LL;
using namespace std;

const long long mod = 16777216;
LL a[200005], c1[200005], c2[200005], l[200005], r[200005];
int n;

int lowbit(int x){
	return x & (-x);
}

void add1(int x){
	while(x <= n){
		c1[x]++;
		x += lowbit(x);
	}
}

void add2(int x, int num){
	while(x <= n){
		c2[x] += num;
		x += lowbit(x);
	}
}

int sum1(int x){
	int res = 0;
	while(x){
		res += c1[x];
		x -= lowbit(x);
	}
	return res;
}

int sum2(int x){
	int res = 0;
	while(x){
		res += c2[x];
		x -= lowbit(x);
	}
	return res;
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	LL ans1 = 0, ans2 = 0;
	for (int i = 1; i <= n; i++){
		l[i] = sum1(a[i]);//左边有多少比当前小的，就有多少种选法(选完a,b)
		r[i] = n - i - (a[i] - l[i] - 1);//(选c,d)n-i表示后边最多有(n-i)中选法，减去比a[i]小的数(当前位置后边可能有比a[i]小的数，保证c,d大于a,b)
		add1(a[i]);//更新
	}
	for (int i = 1; i <= n; i++){
		ans1 = (ans1 + l[i] * (r[i] * (r[i] - 1) / 2) % mod) % mod;//(a,b)选法有l[i]种，(c,d)选法为C(r[i],2)(这里没考虑c>b,后边再减)
	}
	//cout << ans1 << endl;
	for (int i = 1; i <= n; i++){
		ans2 = (ans2 + sum2(a[i]) * r[i] % mod) % mod;
		//统计当d大于c时的数时的个数
		add2(a[i], l[i]);//更新选(a选比a[i]小的数,b=a[i])时有多少种
	}
	printf("%lld\n", ((ans1 - ans2) % mod + mod) % mod);

	return 0;
}