「NOI考前欢乐赛」小奇遐想

2016年6月26日4,1100
「题目背景」

撷来一缕清风飘渺

方知今日书信未到

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

风中鸟啼犹带欢笑

——《清风醉梦》

「问题描述」

小奇望着青天中的悠悠白云,开始了无限的遐想,在它的视野中,恰好有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)

 

avatar
  Subscribe  
提醒