fyjjjj

树状数组

动态规划(6) 字符串(1) 平衡树(1) 背包(2) 递归(1)

/ 注册

全部文章 / 树状数组（共4篇）

楼兰图腾

题目链接题意很清晰，抽象一下的话就是求每个数左边和右边比它小的数能组成几个'v'型序列，每个数左边和右边比它大的数能组成几个'^'型序，利用树状数组正向和反向求一边这个数左边比它小(大)和右边比它小(大)的数，然后按照排列组合求出每个数可以得到几个'V'和 ' ^ '即可，跟求逆序对差不多 #in...

2020-10-23

0 501

take

题目链接文字转载于题意:有n个盒子，每个盒子中有p[i]的概率有d[i]大小的钻石，初始有大小为0的钻石，每遇到一个比自己当前大的钻石就要进行交换，求交换的期望。题解:对于每个钻石进行讨论，这个钻石进行交换的可能性是前面所有比这个大的钻石都不产生且这个钻石产生的概率，那么根据d从大到小进行排序...

2020-10-22

0 530

Tree Recovery 树状数组区间修改和求和

题目链接下面的题解转于传送门对于想要学习区间修改和单点输出的同学们可以去看这篇文章传送门假设数组a是原数组，b是a的差分数组，由前缀和的定义，我们求前n个元素的和，即详细过程如下：a1 + a2 + ... + an = b1 + (b1 + b2) + ....+ (b1 + b2 ...

2020-10-21

1 628

珂朵莉的数列

题目链接参考博客这里先给出 __int128和利用vector的unqiue 配合erase 去重__int128 , vector的unqiue 配合erase 去重刚开始看这个题，就是简单的求逆序对所产生的贡献，对于一个逆序对 [i , j]他们所产生的贡献是 l * (n - j)个，...

2020-10-21

0 454