求助 P5445 某代码一极度玄学问题
  • 板块学术版
  • 楼主Francais_Drake
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/5/24 22:19
  • 上次更新2023/10/28 00:41:01
查看原帖
求助 P5445 某代码一极度玄学问题
546086
Francais_Drake楼主2022/5/24 22:19

代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn=300010;
int n,q,u,v,i,j;
int r[maxn];
char p[maxn];
set<int> s;
set<int>::iterator it,i1,i2;
struct bit1{
    unordered_map<int,int> c;
    inline void add(int p,const int &d){
        for(;p<=n;p+=(p&-p)) c[p]+=d;
    }
    inline int query(int p){
        int ret=0;
        for(;p;p^=(p&-p)) if(c.count(p)) ret+=c[p];
        return ret;
    }
};
struct bit2{
    bit1 c[maxn];
    inline void add(int p,const int &y,const int &d){
        for(;p<=n;p+=(p&-p)) c[p].add(y,d); 
    }
    inline void rect(const int &cs,const int &ct,const int &d){
        add(cs,cs,d);
        add(cs,ct+1,-d);
        add(ct+1,cs,-d);
        add(ct+1,ct+1,d);
    }
    inline int query(int p,const int &y){
        int ret=0;
        for(;p;p^=(p&-p)) ret+=c[p].query(y);
        return ret;
    }
}M;
int main(){
    scanf("%d%d%s",&n,&q,p+1);
    for(i=1;i<=n;++i){
        if(p[i]=='0') s.insert(i);
        else r[i]=-1;
    }
    s.insert(++n);s.insert(0);
    for(j=1;j<=q;++j){
        scanf("%s%d",p,&i);
        if(p[0]=='t'){
            if(~r[i]){
                i1=i2=it=s.find(i);
                v=*(++i1)-1;u=*(--i2)+1;
                M.rect(u,i-1,j-r[i]);
                M.rect(i+1,v,j-r[v+1]);
                r[v+1]=j;r[i]=-1;s.erase(it);
            }
            else{
                M.rect(*s.lower_bound(i)+1,*s.upper_bound(i)-1,j-r[v+1]);
                r[v+1]=r[i]=j;s.insert(i);
            }
        }
        else{
            scanf("%d",&v);
            u=M.query(i,--v);
            if(!((~r[i])||(~r[v]))){
                it=s.upper_bound(i);
                if(*it>v) u+=j-r[*it]; 
            }
            printf("%d\n",u);
        }
    }
    return 0;
}

具体在 v=*(++i1)-1;u=*(--i2)+1; 一行中,我在一些时候发现了v<u 且 (++i1) 和 (--i2) 刚好玄学互换了值的情况,出错样例见下

5 50
01001
query 1 6
toggle 3
toggle 3
toggle 2
toggle 3
toggle 2
toggle 4
query 2 6
query 2 3
query 1 3
query 3 5
toggle 3
query 2 6
query 1 5
query 2 3
query 3 6
toggle 5 (这里 u=7,v=2)
toggle 1(这里 u=1,v=-1,程序此刻中止)
......

更玄学的是在修改了M.rect(*s.lower_bound(i)+1,*s.upper_bound(i)-1,j-r[v+1]);//v值由于未在操作中赋值而无意义 的错误之后就没有先前的那个错误了

p.s.怀疑是溢出,但是没有证据。

2022/5/24 22:19
加载中...