前言

我不想调试!!!!

就是这样,本文诞生了

update 2019.9.24:本文原来叫”数据结构调试经验贴”,但当我在调 NOIP2016换教室这一DP自闭之后,我决定把本文的经验收集范围拓展到全体算法上

通用问题

空间和事件复杂度

记得用(double)sizeof(f)/(1024*1024)来计算空间消耗,还有一定记得计算时间复杂度,考试的时候不要忘了!不然MLE和TLE等着您嘞

本地测试爆栈

windows的栈空间很小,不像Linux

所有有时候会出现明明下标没有越界,但是报错的情况

将-Wl,--stack=SIZE这条语句加入dev编译选项中的调试命令中就可以强制开大占空间

比如要开到64MB,那么就写-Wl,--stack=67108864,因为64∗1024∗1024=67108864

debug调试信息

建议在debug调试部分写一个注释,这样的话就可以快速寻找debug信息从而避免错误输出调试信息了

数组大小

谨慎的计算数组大小,以免发生RE的情况

特别是在图论中边表大小的计算(特指分层图),一旦算小了就很惨的

DP中也是一样,会出现一些玄学情况

取模问题

x%p的取值范围是[0,p-1],而非[0,p]
如果一个小于0的值x,我们想要把它取模为正数,那么应该$x=(M+x \ mod \ M) \ mod \ M$,即首先就要对x取模再加M

关于多组数据及反复使用同一算法

一定记得初始化

逻辑问题

关于并列结构和选择结构

2019.10.8日在打树链剖分换根模板的时候:

inline void updateson(int u,ll w){
	if(root==u){
		update(1,seg[0],1,seg[0],1,w);
		return;//here
	}
	int LCA=lca(u,root);
	if(LCA!=u){
		update(seg[u],seg[u]+siz[u]-1,1,seg[0],1,w);
		return;//here,too
	}
	int x=find(u,root);
	update(1,seg[0],1,seg[0],1,w);
	update(seg[x],seg[x]+siz[x]-1,1,seg[0],1,-w);
}

两处标注出来的return没有写,本来当一个if里面的东西执行完后就应该返回,但由于没有打,导致了最后重复累加

这个问题原来在线段树里面也有犯过,但是没有引起注意

数据结构

线段树

分治鲁棒性

在分治的时候,有可能输入的左边界和右边界不严格满足$l<=r$,因此应该加上

if(l>r)return;

来加强鲁棒性

但这还没完,因为当函数值是int或long long时,return后面应该需要跟上一个值,而这个值不能够直接写成0,而要按照题目需求来决定返回极大值还是极小值

update函数

没有在update函数里面pushdown和pushup
update的时候lazy标记是累加的而非赋值:

void update(int l,int r,int nl,int nr,int rt,ll w){
	if(l<=nl&&nr<=r){
		lazy[rt]+=w;//不能写成lazy[rt]=w;
		sum[rt]+=(nr-nl+1)*w;
		return;
	}
	pushdown(nl,nr,rt);
	int mid=(nl+nr)>>1;
	if(mid>=l)update(l,r,nl,mid,rt<<1,w);
	if(mid<r)update(l,r,mid+1,nr,rt<<1|1,w);
	pushup(rt);
}

数组大小

数组没有开够,记得要开4倍大小

精度问题

一般来讲数据都会特别鬼畜啊,记得开longlong
特别注意有没有精度转化,即int相乘后面转longlong时可能在中间爆掉:

sum[rt]+=(long long)num*(nr-nl+1);//一定要转化精度

关于二分值mid

int mid=(nl+nr)>>1;//不是(l+r)>>1,这点很容易错!

关于返回值

这是一个很sb的错误,query函数没有写

return res;

这个问题编译选项开-WALL就可以避免

splay(手写版)

1.关于插入极大和极小值这个技巧

一定要插入足够大和小的值，否则会出一些玄学错误，一定要能多大就多大
比如这个情况

2.关于rotate函数的不同写法

rotate函数理论上来说有不同的写法，但是原则就是一定要把那四个点的父子关系和相关信息维护正确
比如：在维护x的父子关系时，要确定y是x的哪个儿子，理论上可以通过：
1.原来x相对于y的位置关系
2.x的被影响的那个子节点相对于x的位置关系
两种方式来判断
这时问题来了，如果x没有子节点呢，这时x的子节点就是0（空都是0），那么这样就没有办法正确的更新父子关系，所以以后还是用前一种方法吧

3.关于insert函数

A

if(_p)tree[_p].son[_w>tree[_p].w]=_cur;

这一句特别容易被打掉！！！！！
如果不打的话，新插入的这个点的父节点就没法和这个点相连了

B

int _cur=root,_p=0;
while(_cur&&tree[_cur].w!=_w)
{
	_p=_cur;
	_cur=tree[_cur].son[_w>tree[_cur].w];
}

在寻找值为w的点时，while循环里面的判断条件是当前所在的点不为空！

这和find函数中的即将到达的点不为空需要区别

4.关于找第k大函数

while(1){
        if(tree[Lson(cur)].siz>=k)
            cur=Lson(cur);
        else if(tree[cur].cnt+tree[Lson(cur)].siz>=k){
            Splay(cur);
            return tree[cur].w;
        }
        else if(tree[cur].cnt+tree[Lson(cur)].siz<k){
        	k-=tree[cur].cnt+tree[Lson(cur)].siz;//
        	cur=Rson(cur);
		}
    }

注意第3个else if里面的两句话的顺序不可以换！
虽然很显然，但是在没有高度专注的情况下总是会出现这些神奇的情况

5.关于删点函数

记清楚步骤：先旋前驱到root，再旋后继到其前驱的下面
不能把后继旋到根上去了

6.关于找排名函数

在大部分定义里面，数m的排名为小于m的数的个数+1，不能忘记+1！

7.关于函数的返回值

有些函数返回值可以是某个点的值，也可以是某个点的编号
但是如果返回值，就不可以得到编号，若返回编号，却可以得到值
如果不做强行规定，在构建代码的时候会出现RE的风险
因此，规定如下：

_pos:返回_x的位置关系:0/1
update:void
rotate:void
splay:void
insert:void
find:void/int(int=>返回编号，不可返回值！)
findkth:int(返回编号)
pre:int(返回编号)
bac:int(返回编号)
del:void
getrank:int=>返回某个数的排名

8.关于宏的使用

由于结构体的特点，用结构体方式构建的Splay必然会显得比较冗杂，语句偏长容易积累bug且不容易调试，因此推荐以下宏定义：

#define f(x) tree[x].fa
#define Lson(x) tree[x].son[0]
#define Rson(x) tree[x].son[1]
#define ADX_son(x,w) tree[x].son[tree[x].w<w]
//按大小的儿子~~

splay(vector版)

关于lowerbound函数和upperbound函数

其一记住这两个函数的含义:返回第一个大于等于x的位置;返回第一个大于x的位置.显然,这两个函数的区别就是在等于二字上面

其二记住两个函数返回的是内存中的地址,而非其他的什么东西.因此要得到在数组中的位置的时候应该要减去数组的开始地址

关于排名

看定义!记得排名加一

关于vector的存储顺序

vector以0开始存,因此vector调用下标的时候如果直接输入排名一定记得减一

树链剖分

剖分后的区间

剖分后的区间为[1,seg[0]],最好不要写成[1,n]

也就是

buildtree(1,seg[0],1);//not buildtree(1,n,1)

dfs1

dfs1中,遍历到每一个点的时候记得要把这个点的4个值赋初值,不要图便宜把这一步省去,不然死的很惨

点权转边权

统计路径和的时候,由于不会统计两个点lca的权值,所有在且仅在最后一次线段树查找的时候才会把下标位移

关于重链加速

记得每次统计完数据后要把u节点向上跳到top的fa
记得当两个点还没有相遇的时候要让他们一直向上跳:

while(top[u]!=top[v]){//这里是是写while而不是写if!
 	if(dep[top[u]]<dep[top[v]])swap(u,v);
	res+=query(seg[top[u]],seg[u],1,seg[0],1);
	u=fa[top[u]];
}

关于建树时点权

有时候会在建树的时候误把点权w[rev[l]]写成w[l],也就是忘记了映射回去

两个dfs

在两个dfs之间一定要记得把根的信息做好

DP

1.初始化

初始化不当会导致多种玄学错误

常见的问题:

没有初始化:

惨案一:NOIP2016换教室 ,没有吧所有的数组初始化为极大值,从而让非法状态的权值变成了0,然后导致非法状态更新了其他合法状态导致答案偏小

惨案二:acwing 298. 围栏 ,单调队列优化DP,每次循环i的时候单调队列没有清空导致WA3组

2.背包问题

背包问题的初始化

如果是要求刚好填满,数组初始值应该赋一个极小值,只把合法的状态初始值赋为0,这样的话才能够保证更新的是刚好装满

如果要求不需要填满,那就可以只赋0就行

状态压缩

关于状态压缩DP，要注意二进制位的方向，数组从低位到高位到底是从二进制的低位到高位还是高位到低位
状态压缩dp中要特别注意0基准和1基准的差异性

图论

关于常用变量

ui,vi很容易打混淆,特别是在Floyd算法中

关于建图

有时候输入的时候会有重边,重边会需要特殊处理(如在Floyd里面就需要取min值等)
建图的时候注意是建双向边还是单向边
关于加边函数addl:

inline void addl(int u,int v){
	edge[cnt].e=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt++;//记得cnt要自加!
}