2023-08-25 15:09:42
start writing:2023.8.25 14:15
事情的起因又是邪恶的 yqt ...
为什么每次跟他都会遇到奇怪的事情
注——这只是一个对在劳累却有趣的 OI 生涯中遇到的插曲的记录,不是专业人士,对内容的研究也只是浅尝辄止,学个经验看个乐子就好了。
结论
省流:如果你用一个指针指向 vector 中一个元素,然后再对 vector 进行一些操作,有可能导致指针指向错误地址,因为在对 vector 进行操作时,vector 中数据的地址可能会发生改变。
起因
yqt 让我用线段树打一个 sb 题,反正就是区间修改,单点查询,只不过值域范围变成了 \(N \le 10^7\) 而已,操作数还是可做的。我就说树状数组直接秒。他非要我写线段树,我说写个离散也没事啊,他又说别人都没有离散就过了(要求真多),然后我就打了一个动态开点线段树,一开始交因为数组不够大,RE 了很多点,然后调了一下也就过了。
经过
这个时候,我想到“是不是可以写一个动态数组维护呢?懒得算数组大小了。”,然后就魔改成了这样:
\(Problem\ Code\)
#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
return x*f;
}
struct tree{
int v,l=-1,r=-1;
};
int n,m,tot=-1,rt=-1;
vector<tree>tr;
inline void pushdown(int root){
if(tr[root].l<=0)tr.push_back({0,-1,-1}),tr[root].l=++tot;
if(tr[root].r<=0)tr.push_back({0,-1,-1}),tr[root].r=++tot;
tr[tr[root].l].v+=tr[root].v;
tr[tr[root].r].v+=tr[root].v;
tr[root].v=0;
return;
}
void update(int &root,int l,int r,int x,int y,int v){
if(root<0)tr.push_back({0,-1,-1}),root=++tot;
if(x<=l&&r<=y)return tr[root].v+=v,void();
pushdown(root);
if(mid>=x)update(tr[root].l,l,mid,x,y,v);
if(mid<y)update(tr[root].r,mid+1,r,x,y,v);
}
int query(int &root,int l,int r,int x){
if(root<0)tr.push_back({0,-1,-1}),root=++tot;
if(l==r)return tr[root].v;
pushdown(root);
if(mid>=x)return query(tr[root].l,l,mid,x);
else return query(tr[root].r,mid+1,r,x);
}
int main(){
n=read(),m=read();
while(m--){
int opt=read(),l=read();
if(opt&1){
printf("%d\n",query(rt,1,n,l));
}else{
int r=read();
update(rt,1,n,l,r,1);
}
}
}
乍眼一看确实一点毛病没有,仔细看也没有啥问题,因为我就是把数组换成 vector 了而已。然后就莫名其妙的样例都过不去到处 RE,我把 vector<tree>tr
改成 vector<tree>tr(100000)
才勉强能过样例,交上去还是 RE 一片。
为啥呢?
在这个相对复杂的代码里面调试了很久还是找不到什么问题,只是在调试的过程中经常会出现其他变量挺正常的,但是就 root
压根没有值的现象,长这个样:
然后我想,既然是vector 的问题,那是不是就不能边 push_back
边查询刚加入的值呢?做了个实验,发现可以非常正常的运行。既然这个代码太麻烦了,那就稍微简化一下吧?于是我写了以下代码(为了观赏,删去了一些无用代码):
\(Test\ Code\)
#include<bits/stdc++.h>
using namespace std;
struct tree{int v,l,r;};
inline tree New(){
tree p;
p.v=0,p.l=-1,p.r=-1;
return p;
}
int tot=-1,rt=-1;
vector<tree>f;
void update(int &root){
if(root<0)root=++tot,f.push_back(New());
if(f.size()<=10)update(f[root].l);
}
int main(){
tot=-1,rt=-1;
update(rt);
for(int i=0;i<=10;i++){
printf("%d\n",f[i].l);
}
}
果不其然,就简单到这种程度了还是会 RE。
加入了几个监视变量,我把所有调试按钮打开,一个一个的看过去,只看见这个 root
非常不听话,一开始挺正常的赋值,进入第二三层就变成了一些很奇怪的值 503
,-17891602
,514
等,到第三层结束去第四层,直接跟之前一样压根就不显示值了。
这个时候 yqt 的一点点用处就出来了,他说肯定是你这个 &
取地址有问题啊,我刚想反驳他,突然想到,是唉,如果地址指向错了,那也不差不多就是 RE 了吗??
尾声
我立马搜索:
发现:
我的天哪,这人出现的问题居然跟我出奇的一致,那就相信他好了。
我这时又给监视加了一个 &f[0].l
看在修改过程中地址有没有改变,然后就出现了下面一幕:
然后就不出所料的 RE 了。
大概是 vector 为了新加内容,申请空间的时候,地址发生了一些不大但很关键的变化,反映到程序上就是直接访问到错误地址导致 Segmentation fault。仔细看不难发现我这里展示的 &f[0].l
是先变化了一点点,然后又变回去了,不管怎样,只要变了,出事就很正常了。
所以下次用 STL 还是不要这么想当然了吧~也给我提供了一个调试新思路。
end writing 2023.8.25 14:52