记录
2026-09-28 23:08:19
发布于:上海
一.盲打模板
P3374
做一个单点修改+区间查询的树状数组
树状数组的用途:
1.数列中单点修改+区间查询(最普通的用法,时间复杂度O(logn)一次)
2.数列中区间修改+单点查询(用法1的衍生,时间复杂度也是O(logn)一次)
3.求逆序对(一般不使用树状数组去做,可以忽略)
树状数组的思想
树状数组的核心思想是使用lowbit()将原本的数组拆成一块块的,用一个数字去表示一块。
二.黄题限时练习
P1083
限时时间内思路:
似乎是一个需要技巧的模拟题目。
需要完成的操作:每次操作把一段区间内的每个数都减一个特定的数,且不能有负数。
每次操作时间:大概率O(1)
正解:
读题错误?
二分+差分
过了。
很神奇,没有用前缀和与差分就过掉了。
研究一下用前缀和的做法。
哦。是这样的,这道题目年代比较古早,当时还没有1e8/s这个性能。
这道题目也是可以用前缀和&差分去完成的。
每一次输入,将a+1~b-1区间里的数全部减一,最后加上最大数值即可。
注意可能会有重复的牛的对视,此时需要判重。(感觉很难想到欸)
这里空空如也















有帮助,赞一个