2016多校训练Contest5:1012 World is Exploding

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5792

题目翻译

有一个序列 An , 求四元组的数量 ( a , b , c , d ) ,满足 abc1a<b1c<dAa<AAc>A.

题解

容斥原理。
我们统计出四元组 ( a , b , c , d ) ,满足 1a<b1c<dAa<AAc>Ad 的数量
然后减去不符合条件 abcd 的四元组数量。
因为 Aa<AAc>Ad ,所以 ab , cd 。
所以我们只需要考虑这几种重复的情况:

  1. a = c
  2. a = d
  3. b = c
  4. b =d

如此一来,我们就需要统计这些三元组 ( a , b , c )的数量在最终答案中减去

  1. Aa > Ab , Aa < Ac ( a < b & a< c )
  2. Ac > Aa , Aa < Ab ( c < a <b )
  3. Ab < Aa , Aa > Ac ( b < a< c )
  4. Ab < Aa , Ac > Aa (a > b & a > c )

对于每个数,我们用树状数组统计前面比它大/小,后面比它大/小的数量。
然后枚举Aa,算一下每个三元组的数量在最终答案中减去即可。

代码