【NOI考前欢乐赛】小奇遐想

2016年6月26日1,8390
【题目背景】

撷来一缕清风飘渺

方知今日书信未到

窗外三月天霁垂柳新长枝条

风中鸟啼犹带欢笑

——《清风醉梦》

【问题描述】

小奇望着青天中的悠悠白云,开始了无限的遐想,在它的视野中,恰好有n朵高度不同的白云排成一排,他想从左到右选出四朵白云a,b,c,d,使得h_a < h_b < h_d < h_c,即看起来像是彩虹的形状!它想知道有多少种方案数。

【输入格式】

第一行包括1个整数n。

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

【输出格式】

输出一个整数表示答案。(mod 16777216)

【样例输入1】

5

1 5 3 2 4

【样例输出1】

0

【样例输入2】

4

1 2 4 3

【样例输出2】

1

【数据范围】

对于10%的数据n<=600;

对于40%的数据n<=5000;

对于100%的数据n<=200000。

这题是ctsc图腾弱化版。。。【数据结构练习】图腾

本来想给学弟出原题的,但是考虑原题太难

本题只需要求出1243个数

转化一下变成求12xx-1234

暴力n^3枚举2,1的个数预处理,43暴力

正解是树状数组。。。

处理出每个数左边/右边比它小的个数

12xx就解决了

统计1234类似的再做一次树状数组,统计sigma l[j] (a[j]<a[i] j<i)