codeforces 61 E. Enemy is weak (离散化+线段树求逆序三元组)

题目链接
题意:给出n个数,求满足 i<j<k且a[i]>a[j]>a[k]的三元组有多少个。

思路:对于这种要求三个数满足条件的题目,老司机的经验是考虑中间那个数,这道题也不例外。

我们枚举j,通过求两次逆序对求出对于每个a[j],满足a[i]>a[j]的i的个数,以及满足a[j]>a[k]的个数。

两个个数的乘积就是j作为中间数满足的三元组的个数,这样把所有的j累加就是答案。

其他的就是,要离散化,以及最后答案可能会爆long long?

1A,好爽啊哈哈哈。

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz