DAY 3 树状数组

训练情况简介

早上：
下午：
晚上：

早上

A 题单点修改+区间查询模板题

逆序对 https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/A
利用树状数组求解，详见树状数组求解逆序对问题

B题打个标记，不一定整的出来
参考思路
具体实现是尧尧的代码
B题记得写一篇博客摘记一下：[ ]完成后打勾

下午

C 题
终于理解当初组队训练的时候遇到的这题的解法了！！！
终于明白当初姚老师说仅记下同一类型数字的右端点即可快捷求解的道理

思路来自洛谷题解叶小枫
记得写一篇博客摘记一下：[ ]完成后打勾

有时间的话可以找找当初组队训练的那题出来写一写

D 题
与C题类似，应当是无修改，只不过就像人穿衣服不一样

E 题洛谷提示树状数组？目前没有看出来和树状数组的关系(15:09)
树状数组好题？按照听力排序？那么我们每次取到的奶牛的音量的问题解决了，那么，距离怎么解决？
思路来自洛谷题解，代码自己实现的
距离利用两个树状数组实现
一个树状数组统计距离，用来统计当前位置前的奶牛的距离之和
一个树状数组用来记，方便统计当前位置前有几个奶牛的距离小于当前位置,记为t
另外统计一个距离的前缀和sum
之后即可统计ans

\[ans+=(t*p[i].x-getsum(0,p[i].x))*p[i].v;\\ ans+=(sum-getsum(0,p[i].x)-(i-1-t)*p[i].x)*p[i].v; \]

晚上

个人训练做了前四题，都是之前做过的，第五第六看了

第五题需要一个数据结构来维护？
利用两个multiset维护数组前k个最大值，什么删除，什么插入都用multiset来操作

第六题不知道怎么下手

M 题
肯定不能用暴力的双重循环
考虑树状数组，就是说，考虑两个人的话，其内的选手有几人分数满足条件比较困难
故可以考虑单独一个人，判断其左右分数同大同小的选手数，最终遍历即得解
关键就在于转换思路！！！将两个人找中间转换为找一个人的两边，而找一个人的两边可以用树状数组来解决

N 题
树状数组可做，但是必须得注意，得注意，得注意
树状数组的c[x]的下标是从1开始的，而这道题目的\(0<=x,y<=32000\)，下标为0的无法处理，所以可以在update时将下标加一，再进行判断
有点小坑呜呜

补充内容

差分版本

参考《算法竞赛进阶指南》《挑战程序设计竞赛》
利用差分数组，实现 O(log n) 的区间加、区间查询
a[1] = diff[1]
a[2] = diff[1] + diff[2]
a[m] = diff[1] + ... + diff[m]
所以 a[1] + ... + a[m]
= ∑(m-i+1)diff[i]
= (m+1)∑diff[i] - ∑idiff[i]
https://ac.nowcoder.com/acm/problem/50454
https://codeforces.com/contest/1824/problem/D

[0] 维护 ∑diff[i]
[1] 维护 ∑i*diff[i]
为了更好地利用缓存，写成 [][2] 而不是 [2][]

求权值树状数组第 k 小的数（k > 0）

这里 tree[i] 表示 i 的个数
返回最小的 x 满足 ∑i=[1..x] tree[i] >= k
思路类似倍增的查询，不断寻找 ∑<k 的数，最后 +1 就是答案
https://oi-wiki.org/ds/fenwick/#tricks

https://codeforces.com/blog/entry/61364
https://codeforces.com/problemset/problem/1404/C
todo https://codeforces.com/contest/992/problem/E
https://atcoder.jp/contests/abc287/tasks/abc287_g
二分 https://www.luogu.com.cn/problem/P4137

求逆序对的方法之一

如果 a 范围较大则需要离散化（但这样还不如直接用归并排序）
归并做法见 misc.go 中的 mergeCount
扩展 https://codeforces.com/problemset/problem/362/C
环形最小逆序对 https://www.luogu.com.cn/problem/solution/P2995
扩展：某些位置上的数待定时的逆序对的期望值 https://codeforces.com/problemset/problem/1096/F
https://codeforces.com/problemset/problem/1585/D

通过邻项交换，把数组 a 变成数组 b，需要的最小操作次数

如果无法做到，返回 -1
https://atcoder.jp/contests/arc120/tasks/arc120_c
LC1850 https://leetcode.cn/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/

给一个数组 a 和一些询问 qs，对每个询问计算 mex(a[l..r])

a[i]>=0, 1<=l<=r<=n
遍历数组 a，记录 a[i] 最后一次出现的位置 lastPos 以及上一个 a[i] 的位置 prevPos
建立一个权值树状数组，维护 lastPos[v] 的前缀最小值
树状数组维护前缀最小值的条件是每次修改只能往小改，那么从后往前做就好了
将询问离线：按照右端点排序（或分组），计算 mex。原理见代码中 query 的注释
https://www.luogu.com.cn/problem/P4137
LC2003 https://leetcode-cn.com/problems/smallest-missing-genetic-value-in-each-subtree/