树状数组差分模板

$$\color{aqua}{csp2019 rp++} $$

树状数组的差分和普通差分没有区别;

用$now$记录上一个数是什么,直接输入之后减掉就可以了,例如$a-now$

这样做省去了许多栈空间.差分的好处是可以快速求出被修改后的一个数列中的某一个数

$luogu$的题目$(树状数组2)$是区间增加,所以就先$add(x,k)$之后再$add(y+1,-k)$

线段树的动态开点和合并模版(维护区间最大值)

今天看了蓝书上的这个模版,感觉就像打开了新世界的大门
自己多加了一点注解,为了能让自己永远理解且不忘掉qwq

食物链

题目链接:https://www.luogu.org/problem/P2024

这道题第一眼拿到以为用两个数组维护敌人和同类就好了 于是完美地拿到了10分
然后仔细一看发现想到要用三个数组维护,但是十分麻烦,于是厚颜无耻地直奔题解QAQ
看了luogu一位大佬的思路之后终于将这个题AC了
其实只用一个数组f[i],i表示本身,i2表示猎物,i3表示天敌

ST chart template

ST表学习

就像蓝书上所写:ST表是倍增的产物.
首先什么是ST表呢?
就是解决RMQ问题的时间复杂度在O(1)的算法
首先开一个f[i][j]数组表示[i,i+2^j-1]区间内最大的数
递推边界为f[i][0]=a[i];
然后再二分2^j,分别查找[i,i+2^(j-1)-1]和[i+2^(j-1),i+2^j-1]两个区间内的最大值并取两个最大值,这两个最大值中最大的那一个就是[i,i+2^j-1]区间内最大的数
递推主体代码:

1
2
3
for (int j=1; j<=log2(n)+1; j++)
for (int i=1; i+(1<<j)-1<=n; i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);

团伙-并查集

题目描述:https://www.luogu.org/problem/P1892

并查集真的很好的数据结构呢;
团伙这个题只需要开enm数组储存自己的敌人的组先再合并即可.
R6新干员很期待,但是还是没出新枪,UBI在干嘛??????
附上昨日凌晨沙雕UBI图,R6:我疯起来连自己都Block 23333
沙雕

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×