每日一个爆零小技巧

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-03-28 22:03:35

前言：

本 blog 收集我遇到的所有 bug。

csp-j当天

Dev-C++ 5.1.0 环境，如果在 CSP 考场用，不要开 -std=c++11

2022.3.28

1.平衡树为了求前驱后继临时建的节点记得删除
2.平衡树删数的时候要注意像这样 splay 之后：

int prenode = pre(val);
int nxtnode = nxt(val);
splay(prenode, 0);
splay(nxtnode, prenode);

权值为 val 的节点现在是它原来的后继 nxtnode 的左子节点，也就是 node[node[nxtnode].ch[0]]
3.平衡树每加入一个节点就要把它 splay 到根。

2022.4.17

如果要先读入一些东西，然后用 fgets 读入字符串的话，最好在 fgets 之前先 getchar 读取换行符，不然会炸。
如

int n;
char s[maxn];
cin>>n;
getchar();
fgets(s,maxn,stdin);

2022.6.8

使用主席树求解区间第 $k$ 小的时候有个地方要注意。就是如果查询的是右区间，那么这个 $k$ 要减去左区间的大小。也就是：

query(rs[l_node],rs[r_node],mid+1,r,k-count);

2022.6.10

unique 只能对排好序的数组使用
不要不小心把离散化后的区间长度错当成原来的区间长度

2022.6.11

dfs 的时候，如果要跳过某个点，不要写成 return！不要写成 return！不要写成 return！

错误示范：

void dfs2(int u,int fa)
{
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int to=edge[i].to;
		if(to==fa)return;
		dfs2(to,u);
		cf[u]+=cf[to];
	}
}

正确：

void dfs2(int u,int fa)
{
	for(int i=head[u];i;i=edge[i].nxt)
	{
		int to=edge[i].to;
		if(to==fa)continue;
		dfs2(to,u);
		cf[u]+=cf[to];
	}
}

2022.6.12

lca 的同时向上跳的部分，要注意的是要比较祖先而不是祖先的深度！
错误示范：

for(int i=17;i>=0;i--)
{
	if(dep[fa[i][a]]!=dep[fa[i][b]])
	{
		a=fa[i][a];
		b=fa[i][b];
	}
}

正确：

for(int i=17;i>=0;i--)
{
	if(fa[i][a]!=fa[i][b])
	{
		a=fa[i][a];
		b=fa[i][b];
	}
}

2022.6.13

记得局部变量要初始化（windows系统局部变量不初始化问题不大，Linux 一定会炸）

2022.6.15

第一个

线段树一定不要把左子树和右子树写混！！！
错误示范：

val[i<<1|1]=lazy[i]*get_len(i<<1);

正确：

val[i<<1|1]=lazy[i]*get_len(i<<1|1);

第二个

另外，对于一些要将区间所有数更改为 $val$ 这样的题目，打 lazy tag 的时候之前要将 lazy 数组初始化为 $val$ 取值范围以外的数，标记下放判断是否有标记的部分也要作相应的修改。
下面是一个例子：
$0 \le val \le 10^9$
此时就不能将 lazy 数组初始化为 $0$ 了，现在将其初始化为 $-1$
然后标记下放部分就变成这样：

inline void push_down(int i)
{
	if(lazy[i]==-1)return;
	lazy[i<<1]=lazy[i];
	lazy[i<<1|1]=lazy[i];\/\/标记更新
	val[i<<1]=lazy[i]*get_len(i<<1);\/\/权值数组更新
	val[i<<1|1]=lazy[i]*get_len(i<<1|1);
	lazy[i]=-1;
}

第三个

还有一个关于 C++ 基础语法的一个
定义了一个指针之后，如果它没有指向某一个变量，而且想要用它存数据，得用 new 来给它分配空间
例如：

struct Node
{
	int cnt;
};
Node* tmp;
void main()
{
	tmp= new Node();
	tmp->cnt=114514;
	cout<<tmp->cnt<<endl;
}

第四个

使用 new 分配内存的变量，不会自动初始化，需要手动添加初始化函数。

2022.7.5

写树剖的时候，记得要先 dfs 预处之后再 build 线段树

2022.7.8

线段树 Build 函数，在递归完左右子树后记得 push_up 更新非叶子节点

2022.7.10

注意：这只适用于 EK 算法

在 BFS 图的时候，要注意每找到一个当前节点能到达的节点 $to$，就要标记上 $vis[to] = 1$，而不是从队列里取出元素时标记。如果不这么做，会导致一些点已经访问过了，但是在将它们取出队列之前没有标记上，如果一些点与它们有边相连而且比它们先从队列里取出，那么会造成重复访问，导致 TLE
正确：

inline bool bfs()
{
    memset(vis,0,sizeof(vis));
    queue<int> que;
    que.push(s);
    vis[s]=1;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(vis[to])continue;
            vis[to]=1;
            que.push(to);
        }
    }
    return 0;
}

错误：

inline bool bfs()
{
    memset(vis,0,sizeof(vis));
    queue<int> que;
    que.push(s);
    vis[s]=1;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=1;
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int to=edge[i].to;
            if(vis[to])continue;
            que.push(to);
        }
    }
    return 0;
}

2022.7.11

注意 unordered_map 可以被卡到 $O(n)$
使用的时候最好使用自定义哈希函数，这篇博客会进行相关讲解

2022.7.17

不要算错空间，特别是 OI 赛制下

2022.7.27

如果想要让 priority_queue 实现小根堆，应该这样写（假设要用 T 类型）：
priority_queue<T,vector<T>,greater<T>> name

2022.8.12

局部变量记得初始化。

2022.8.14

哈希函数的模数不能只有一个，最好使用双哈希 + 不常用模数。

2022.8.16

欧拉回路相关问题，记得加当前弧优化。

2022.8.22

set 比 map 常数小得多。

2022.8.27

记得计算一下最大值可能是多少，例如如果数据最大可能是 $10^{12}$，而其中一部要计算平方，那么最好开 __int128。

vector 的博客

博客

前言：