抽象错误集锦

本文收录自己犯过的一些离谱错误，用来引以为戒。

1. (Acwing 121)离散化之后混用下标和离散化的数值

   ll tx=lower_bound(x,x+rx,i+mid-1)-x,ty=lower_bound(y,y+ry,j+mid-1)-y;
   if(x[tx]>i+mid||tx>=rx)tx--;
   if(y[ty]>j+mid||ty>=ry)ty--;
   ll ans=sum[tx][ty]-(i!=0?sum[i-1][ty]:0)-(j!=0?sum[tx][j-1]:0)+(i!=0&&j!=0?sum[i-1][j-1]:0);
   if(ans>=c){
   	res=true;
   	goto out_of_loop;
   }
   CPP

   正确写法：

   ll tx=lower_bound(x,x+rx,x[i]+mid-1)-x,ty=lower_bound(y,y+ry,y[j]+mid-1)-y;
   if(x[tx]>x[i]+mid-1||tx>=rx)tx--;
   if(y[ty]>y[j]+mid-1||ty>=ry)ty--;
   ll ans=sum[tx][ty]-(i!=0?sum[i-1][ty]:0)-(j!=0?sum[tx][j-1]:0)+(i!=0&&j!=0?sum[i-1][j-1]:0);
   if(ans>=c){
       res=true;
       goto out_of_loop;
   }
   
   CPP

   其中 i,j 是下标， x[i],y[j] 是离散化之后的数。
2. (AT_abc356_d)组合数求法。 错误示范：

   ll c(ll p,ll n){
   	if(n==0)return 0;
       ll res=1;
       for(ll i=1;i<=p;i++){
           res=(res*i)%Mod;
       }
       for(ll i=n;i>=n-p;i--){
           res=(res*i)%Mod;
       }
       return res;
   }
   CPP

   槽点有点多。
   首先，，因此即便 ， 也非零。其次，下半部分的阶乘应当时乘上乘法逆元，而不是乘上 。第三， 有 个数。正确示范：

   ll c(ll p,ll n){
       ll res=1;
       for(ll i=1;i<=p;i++){
           res=(res*niyuan[i])%Mod;
       }
       for(ll i=n;i>n-p;i--){
           res=(res*i)%Mod;
       }
       return res;
   }
   CPP

3. (Acwing220)线性筛等需要多个循环变量时分清每个变量是做什么的。

   void prime_prework(){
       memset(min_prime_factor,0,sizeof min_prime_factor);
       for(ll i=2;i<=inp;i++){
           if(min_prime_factor[i]==0){
               phi[i]=i-1;
               min_prime_factor[i]=i;
               primes[n]=i;
               n++;
           }
           sum_prefix[i]=sum_prefix[i-1]+phi[i];
           for(ll j=0;j<n&&primes[i]<=min_prime_factor[j]/*此处下标i,j反了*/&&i*primes[j]<=inp;j++){
               phi[i*primes[j]]=phi[i]*(i%primes[j]==0?primes[j]:(primes[j]-1));
               min_prime_factor[i*primes[j]]=primes[j];
           }
       }
   }
   CPP

   正确示范：

   void prime_prework(){
   	memset(min_prime_factor,0,sizeof min_prime_factor);
   	for(ll i=2;i<=inp;i++){
   		if(min_prime_factor[i]==0){
   			phi[i]=i-1;
   			min_prime_factor[i]=i;
   			primes[n]=i;
   			n++;
   		}
   		sum_prefix[i]=sum_prefix[i-1]+phi[i];
   		for(ll j=0;j<n&&primes[j]<=min_prime_factor[i]&&i*primes[j]<=inp;j++){
   			phi[i*primes[j]]=phi[i]*(i%primes[j]==0?primes[j]:(primes[j]-1));
   			min_prime_factor[i*primes[j]]=primes[j];
   		}
   	}
   }
   CPP

4. (AcWing258)想得太复杂了。看完题目以为要用一大堆推理分析，调了好久都没想出来。后来发现暴力就能过。（实际上不是没注意到数据范围，而是以为这道题目时限比较松）结论就是：当一个思路不太好实现时，建议换一个思路。
5. (Luogu P4198)开 long double 要开全！！

   ll cal(ll p,ll h){/**/} // <-- ll h 应为 long double h
   CPP

   正确示范：

   ll cal(ll p,long double h){/**/}
   CPP

6. (Luogu P4556)检查特殊下标（比如 ）有没有特判。（可以用 fsanitize 查查ub）
7. (Luogu P4556)还是那题，倍增法LCA记得特判第一步就移动到相同的点上的可能。
8. (Luogu P4556)又是那题，还是倍增法LCA,检查开的数组的大小，记住 。
9. (Luogu P6225)写树状数组时记得不要把 和 搞混了。虽然很离谱但是我已经连续两次把 中的 写成 了。
10. (Luogu P6619)还是树状数组，写 pos-=lowbit(pos) 的时候不要把 lowbit 漏掉。
11. (Luogu P6619)倍增的时候不要直接把算出来的 当作 。听起来很离谱，但是我确实这么干了。还有记得更新各个变量。
12. (Luogu P3834)可持久化权值线段树到叶子节点的时候记得把旧的数值复制进来。
13. (Luogu P7453)记得取模！！！
14. (Luogu P7453)区间操作记得更新路径上的节点的值！！
15. (Luogu P4170)递归dp如果不确定调用次数记得写记忆化！！！
16. (Luogu网校 T483205)一边 range-for 一边插入节点会出问题。
17. (Luogu网校 T483205) std::unordered_map<__int128,__int128> 会出问题，因为 __int128 没有默认的 hash 函数。（改为 long long 即可）
18. (Luogu网校 T483205)手写邻接表+hash 忘记更新下标。 错误示范：

    i128 query(ll i){
        i128 h=((i%M)*P)%M;
        ll ind=head[h];
        while (ind!=-1){
            if(ht[ind].num==i){
                return ht[ind].val; 
            }
        }
        return 0;
    }
    
    CPP

    正确示范：

    i128 query(ll i){
        i128 h=((i%M)*P)%M;
        ll ind=head[h];
        while (ind!=-1){
            if(ht[ind].num==i){
                return ht[ind].val; 
            }
            ind=ht[ind].nxt; //<-- 这行少了
        }
        return 0;
    }
    CPP

19. (Luogu网校 T486366)多测慎用 memset()，以及不需要频繁取模。

    while(t--){
        memset(s,0,sizeof s); //<-- 这一行
        memset(order,0,sizeof order); //<-- 和这一行
        /*
        由于这两个数组是 1e7 级别的
        数据保证所有测试点 n 的总和为 1e7
        所以当 n 的规模远小于 1e7是
        总共的测试点组数可能会来到
        1e3 甚至 1e4。
        而这两个语句在每个测试点都会重复memset一边 1e7 的数组
        因此导致 TLE。
        */
        //sth else
        for(ll i=0;i<n-k+1;i++){
            ans+=((i+1)*(order[i]+1))%(ll)(1e9+7); //<-- 这里的取模是多余的，因为下一行已经取过一次摸了，而且并不会爆精度。多出来的一次取模导致常数变大 TLE
            ans%=(ll)1e9+7;
        }
    }
    CPP

    正确示范：

    while(t--){
    	//sth else
    	s[n+1]=s[n]=0;// 最终程序最大只会访问到 n，因此只把这两个赋值就可以了。（前面的有输入）
    	//sth else
        for(ll i=0;i<n-k+1;i++){
            ans+=((i+1)*(order[i]+1))%(ll)(1e9+7); // <-- 去掉多余的取模操作
            ans%=(ll)1e9+7;
        }
    	//output...
    }
    CPP

20. (Luogu P6033)这道题时间复杂度卡的很紧。有的时候构造函数可以省略。

    struct node{
    	ull val;
        ull times;
    	node(){
            val=times=0; //<-- 此处构造函数会在声明时调用。由于数组过大(1.5e7)导致调用是会有约 50ms 的常数增加（此题时限 500ms，卡的很紧）
    	}
    };
    struct Queue{
    	node data[(int)1.5e7+100];
        //sth
    	//在队列的push函数中已经有了对于node相关成员的修改。因此无需初始化。
    }
    CPP

    正确示范：

    struct node{
    	ull val;
        ull times;
    	// <-- 删去了构造函数
    };
    struct Queue{
    	node data[(int)1.5e7+100];
        //sth
    }
    CPP

21. (Luogu P4513)线段树的 x<=mid 不要写成 mid<=x。

    void modify(ll p,ll x,ll v){
    	//sth
    	if(mid<=x){ //<-- 应为 x<=mid
    		modify(lc(p),x,v);
    	}
    	//sth
    }
    CPP

22. (Luogu网校 T489100)写线性筛的时候需要注意各种边界问题。（以及复制代码的时候把变量名盖全）
23. (Luogu网校 T491913)Floyd 算法。需要注意不能枚举通过一条边到达 的点和从 开始通过一条边可以到达的点。具体看代码。

    for(ll i=0;i<m;i++){
    	ll s,t,v;
    	cin>>s>>t>>v;
    	G1[s].push_back({v,t});
    	G2[t].push_back({v,s});
    }
    //do sth
    for(ll i=1;i<=n;i++){
        for(auto s:G2[arr[i].ind]){ //<-- 这两处有误
            for(auto t:G1[arr[i].ind]){ //<--
    			//do sth
            }
        }
    }
    CPP

    正确写法：

    for(ll i=0;i<m;i++){
    	ll s,t,v;
    	cin>>s>>t>>v;
    	G1[s].push_back({v,t});
    	G2[t].push_back({v,s});
    }
    //do sth
    for(ll i=1;i<=n;i++){
    	for(ll s=1;s<=n;s++){
    		for(ll t=1;t<=n;t++){
    			//do sth
    		}
    	}
    }
    CPP

24. (校内模拟)复制粘贴：其一

    template<ll T>
    struct modint{
        ll val;
        modint(){
            val=0;
        }
        modint(ll x){
            val=x%T;
        }
        bool operator==(const modint<T>& b)const{
            return val==b.val;
        }
        modint<T> operator+(const modint<T> &b)const{
            return modint<T>(val+b.val);
        }
        modint<T> operator+=(const modint<T> &b){
            val=(val+b.val)%T;
            return *this;
        }
        modint<T> operator*(const modint<T> &b)const{
            return modint<T>(val+b.val); //<-- 注意这里
        }
        modint<T> operator*=(const modint<T> &b){
            val=(val*b.val)%T;
            return *this;
        }
        modint<T> operator-(const modint<T> &b)const{
            return modint<T>(val-b.val+((val-b.val<0)?T:0));
        }
        modint<T> operator-=(const modint<T> &b){
            val=(val-b.val)%T;
            if(val<0)val+=T;
            return *this;
        }
    };
    CPP

25. (同上)复制粘贴：其二

    ll l=1,r=sz;
    while (l<r) {
        ll mid=(l+r)>>1;
        if(rotate(m, mid)==rotate(m, mid)){ // <-- 恒等
            l=mid+1;
        }
        else {
            r=mid;
        }
    }
    CPP

26. (没想到吧，还是一道题)字符串hash没有预处理 pow 数组（甚至已经声明过了
27. (一样)二维 hash 写错数组

    for(ll i=1;i<=n*2;i++){
        for (ll j=1; j<=m*2; j++) {
            G[i][j].a=(H[i-1][j].a*P1)+H[i][j].a;
            G[i][j].b=(H[i-1][j].b*P2)+H[i][j].b; //<-- 右侧 H[i-1][j] 应为 G[i-1][j]
        }
    }
    CPP

28. (P9149) 死循环：其一

    while (h < v.size() && i == v[h].r) {
    	ll t = bi.query(v[h].r) - bi.query(v[h].l - 1);
    	if (t > d) {
    		continue; //<-- 注意 h 并不会更新，导致死循环
    	}
    	ll rest_w = w - nums - t, rest_d = d - t;
    	ans += C(rest_d, rest_w);
    	h++;
    }
    CPP

29. (P3527)无限递归：其一

    void add(ull l, ull r, ull val) {
        if (r < l) {
            add(1, m, val);
            add(r + 1, l - 1, -val);
        } else {
            add(l, val);
            add(r + 1, -val);
        }
        return;
    }
    CPP

    考虑 l==3&&r==2 的情况，add(r + 1, l - 1, -val); 递归后仍然 r<l。
30. (P3810)使用之前记录下来的下标访问元素的时候要原数组是否更改。

    solve(0, total - 1); // 这个函数是cdq分治，里边要重新排序，之前记录的下标会失效
    for (ll i = 0; i < n; i++) {
        cnt[ans[i]] += arr[i].times;
    }
    CPP

    解决：

    solve(0, total - 1);
    sort(arr, arr + total, [](const e &a, const e &b) {return a.i<b.i;});// <-- 重新排个序就好了
    for (ll i = 0; i < n; i++) {
        cnt[ans[i]] += arr[i].times;
    }
    CPP

    补上提交记录或许更容易理解：不排序，排序
31. (CSP-S 2024 T2)局部变量记得初始化！！！！！ 挂分写法：

    void solve() {
    	bit b;
    	//do sth
    }
    CPP

    正确写法：

    void solve() {
        bit b;
        b.clear();
        //do sth
    }
    CPP

    。 是因为还有一个地方写挂了。
32. (AT_abc280_f) 带权并查集：合并时根节点分不清，没有计算出正确的权值（注释里是正确的写法）

    void m(ll x, ll y, ll dis) {
        ll rx = fi(x), ry = fi(y);
        if (rx != ry) {
            //ll r_dis=-f[x].dis+dis+f[y].dis;
            //注意这行，计算出正确的dis值
            f[rx].fa = ry;
            //f[rx].dis = r_dis;
            f[rx].dis=dis;
            f[rx].inf |= f[ry].inf;
    		//f[ry].inf|=f[rx].inf;
    		return;
        }
    }
    
    CPP

33. (CF1691F)运算符优先级，乘法比加法先：

    void dfs(ll x) {
    	//do sth
    	ans += modular<MOD>(n) * C(k, n) - totalc;
        //ans += modular<MOD>(n) * (C(k, n) - totalc);
        //就这个问题调了好久。
        return;
    }
    CPP

34. (P4155)断环成链后，如果需要排序，区间长度记得 。

    for (ll i = 0; i < n; i++) {
        cin >> r[i].l >> r[i].r;
        if (r[i].r < r[i].l) {
            r[i].r += m;
        }
        r[i + n] = r[i];
        r[i + n].r += m, r[i + n].l += m;
        r[i].i = i;
    }
    sort(r, r + n, [](const range &a, const range &b) { return a.l < b.l; });
    CPP

    应改为：

    for (ll i = 0; i < n; i++) {
        cin >> r[i].l >> r[i].r;
        if (r[i].r < r[i].l) {
            r[i].r += m;
        }
        r[i + n] = r[i];
        r[i + n].r += m, r[i + n].l += m;
        r[i].i = i;
    }
    sort(r, r + n * 2,
        [](const range &a, const range &b) { return a.l < b.l; });
    CPP

35. (P3065)拓扑排序是连边是通向的结点的入读加一。

    if (t[cur].c[to_int(c)] && c != x) {
        G[to_int(x)].push_back(to_int(c));
        inc_deg[to_int(x)]++; // --> 改为：inc_deg[to_int(c)]++;
    }
    CPP

36. (CF888G)tire数搞清楚位运算。

    for (int i = p; i >= 0; i--) {
        int b = val & (1 << i);//应该改为：int b = (v >> i) & 1;
        //这样并没有清楚后面的位，因此不能仅靠 1 来判断。
        if (b == 1) {
            //do stj
        }
        else {
    	    //do sth
        }
    }
    CPP

37. (CF888G)不要随便霍霍内存。

    const int N = 2e5 + 5;
    struct node {
    	//...
        vector<int> val;
    	//...
    };
    node t[33 * N];
    CPP

    01-trie 的一个卡内存的技巧：将原数组排序，然后在每个结点记录最左边的数和最右边的数。01-trie 感觉有点像一颗特化的平衡树，每个结点实际上代表了一个区间。
38. (CF1824D) std::vector 在 push_back 或其他修改操作后其原来的迭代器会失效，引用也会失效。 这样写也不行：

    struct node;
    vector<node> v;
    struct node{
    	ll data;
    	void f(){
    		//do sth with v;
    		v.push_back(data);
    		//...
    	}
    }
    //...
    v[i].f();
    CPP

    因为 push_back 后原本这个 v[i] 也失效了。
39. (CF1824D) 线段树下传标记的函数调用不要放在新建子节点的 if 的括号里。

    void spread(ll p) {
    	ll mid = (arr[p].l + arr[p].r) >> 1;
        if (arr[p].lc == -1) {
            arr[p].lc = arr.size();
            arr.push_back(node(arr[p].l, mid));
            //if (arr[p].t != -INF) set(arr[p].lc, arr[p].t);//而不是这里
        }
        if (arr[p].t != -INF) set(arr[p].lc, arr[p].t);//这里
        if (arr[p].rc == -1) {
            arr[p].rc = arr.size();
            arr.push_back(node(mid + 1, arr[p].r));
            //if (arr[p].t != -INF) set(arr[p].rc, arr[p].t); //而不是这里
        }
        if (arr[p].t != -INF) set(arr[p].rc, arr[p].t); //这里
        arr[p].t = -INF;
    }
    CPP

40. (校内模拟) 浮点数运算一定要先乘再除。先除成一个极小的数下溢之后再做被除数会变成 inf，先乘再除就没这个问题。
41. (P4281) dfs 方法预处理 lca 的 fa 数组时记得先预处理在递归。 错误示范：

    void dfs(ll x) {
        vis[x] = true;
        for (auto k : G[x]) {
            if (!vis[k]) {
                dfs(k);
            }
            else {
                fa[x][0] = k;
                depth[x] = depth[k] + 1;
            }
        }
        for (ll i = 1; i < 20; i++) {
            fa[x][i] = fa[fa[x][i - 1]][i - 1];
        }
        return;
    }
    CPP

    正确示范：

    void dfs(ll x) {
        vis[x] = true;
        for (auto k : G[x]) {
            if (vis[k]) {
                fa[x][0] = k;
                depth[x] = depth[k] + 1;
            }
        }
        for (ll i = 1; i < 20; i++) {
            fa[x][i] = fa[fa[x][i - 1]][i - 1];
        }
        for (auto k : G[x]) {
            if (!vis[k]) {
                dfs(k);
            }
        }
        return;
    }
    CPP

42. (P6845) 线段树下传标记的时候要合并标记而不是覆盖标记。

    void add(ll p, ll val) {
    	//给 p 结点对应的区间加上 val.
        node &cur = t[p];
        cur.maxe.val += val;
        cur.mine.val += val;
        cur.max_halfe_l.val -= val;
        cur.max_halfe_r.val -= val;
        cur.tag += val; //<--应为： cur.tag += val;
    }
    CPP