【bzoj1145】[CTSC2008]图腾totem

2014年12月2日2,4791

Description

在完成了古越州圆盘密码的研究之后,考古学家小布来到了南美大陆的西部。相传很久以前在这片土地上生活着两个部落,一个部落崇拜闪电,另一个部落崇拜高山,他们分别用闪电和山峰的形状作为各自部落的图腾。小布的团队在山洞里发现了一幅巨大的壁画,壁画上被标记出了N个点,经测量发现这N个点的水平位置和竖直位置是两两不同的。小布认为这幅壁画所包含的信息仅与这N个点的相对位置有关,因此不妨设坐标分别为(1, y1) , (2, y2), …, (n, yn),其中y1~yn是1~N的一个排列。小布的团队打算研究在这幅壁画中包含着多少个图腾,其中闪电图腾的定义图示如下(图腾的形式只与4个纵坐标值的相对大小排列顺序有关):

崇拜高山的部落有两个氏族,因而山峰图腾有如下两种形式,左边为A类,右边为B类(同样,图腾的形式也都只与4个纵坐标值的大小排列顺序有关):

小布的团队希望知道,这N个点中两个部落图腾数目的差值。因此在本题中,你需要帮助小布的团队编写一个程序,计算闪电图腾数目减去山峰图腾数目的值,由于该值可能绝对值较大,本题中只需输出该值对16777216的余数(注意余数必为正值,例如-1对16777216的余数为16777215)。

Input

第一行包含一个整数N,为点的数目。接下来一行包含N个整数,分别为y1, y2, …, yn。保证y1, y2, …, yn是1~N的一个排列。

Output

仅包含一个数,表示闪电图腾数目与山峰图腾数目的差值对16777216的余数。

Sample Input

【样例输入一】
5
1 5 3 2 4
【样例输入二】
4
1 2 4 3

Sample Output

【样例输出一】
0
【样例输出二】
16777215

HINT

样例一中共有1个闪电图腾(1324)和1个B类山峰图腾(1532)。样例二中仅有一个A类山峰图腾(1243),故差值为-1,答案为16777215。
【数据规模】对于10%的数据,N ≤ 600;对于40%的数据,N ≤ 5000;对于100%的数据,N ≤ 200000。

题解

这个令我蛋疼了大半天

到现在都没看懂clj神犇说的14XX求法什么意思

所以我参照了下seter的博客

以下如有错误请大家指正。。。

 

要求的是f[1324]-f[1243]-f[1432]

f[1324]-f[1243]-f[1432]

=(f[1x2x]-f[1423])-(f[12xx]-f[1234])-(f[14xx]-f[1423])

=f[1x2x]+f[1234]+f[13xx]-f[1xxx]

 

先求出l[i],r[i]表示在i的左/右,比a[i]小的个数

可以先用树状数组求l[i],则r[i]=(a[i]-l[i]-1)

———————————————————————————————————

f[1xxx]

枚举(1)的位置i,则i右边比i大的数有n-i-r[i],设为t

则xxx的方案数为t*(t-1)*(t-2)/6

———————————————————————————————————

f[1234]

枚举(3)的位置i,则(4)的个数有n-i-r[i]

12的对数为sigma(l[j]) (a[j]<a[i],j<=i)

两式相乘法

———————————————————————————————————

f[1x2x]

枚举(2)的位置i,则(2)左边的【数字对】(a[x],a[y])(a[x]<a[i],y任意)有l[i]*(i-1)个

但只有a[y]>a[i],且y>x的合法

多算的有两部分,一部分是a[y]<a[i],y>x,另一部分y<x

第一部分l[i]*(l[i]-1)/2,第二部分为sigma j (a[j]<a[i])

———————————————————————————————————

f[13xx]

枚举(3)的位置i,(3)的右侧要是(2)(4)或者(4)(2)

(4)的个数n-i-r[i]

则【数字对】(a[x],a[y])(a[x]<a[i],x<i,a[y]<a[i])有l[i]*(a[i]-1)个

但只有a[x]<a[y],y>i的合法

也多算了两部分,一部分是x<y<i,形如123,另一部分是a[x]<a[y],y<x,形如213

第一部分l[i]*(l[i]-1)/2 第二部分sigma a[j] (a[j]<a[i])

大概这样吧

 

 

  • 9570768792016年1月12日 下午8:21 回复

    f[13xx]:
    多算的2部分应该是ax<ay&&yay?学长貌似没有讨论ax>ay&&y>i的情况?

    #1