Splay类封装究极玄学现象,求解答

P3391 【模板】文艺平衡树

MichaelWong @ 2023-05-11 19:36:05

应该有人看见我霸屏的提交了吧……

有一个很离谱的问题,求解答,谢谢大家!

就是这个代码:

  #include<bits/stdc++.h>
  #define ll long long
  const int N=1e5+5;
  int n,m;
  class Splay {
      int fa[N],ch[N][2],cnt[N],size[N],lazy[N],root;

      inline void pushup(int p) {size[p]=size[ch[p][0]]+size[ch[p][1]]+cnt[p];}
      inline bool getson(int p) {return ch[fa[p]][1]==p;}
      inline void init(int p,int x=0,int f=0) {
          cnt[p]=size[p]=1,ch[p][0]=ch[p][1]=0,val[p]=x,fa[p]=f;
          if(f) ch[f][x>val[f]]=p;
      }
      inline void pushdown(int p) {
          if(!lazy[p]) return; std::swap(ch[p][0],ch[p][1]);
          if(ch[p][0]) lazy[ch[p][0]]^=1;
          if(ch[p][1]) lazy[ch[p][1]]^=1;
          lazy[p]=0;
      }
      inline void rotate(int p) {
          int f=fa[p],g=fa[f],r=getson(p);
          pushdown(f),pushdown(p);
          if(f!=root) pushdown(g),ch[g][getson(f)]=p;
          ch[f][r]=ch[p][r^1],ch[p][r^1]=f,fa[f]=p,fa[p]=g;
          if(ch[f][r]) fa[ch[f][r]]=f;
          pushup(f),pushup(p);
      }
      inline void splay(int p,const int to=0) {
          for(;fa[p]!=to;rotate(p)) if(fa[fa[p]]!=to) rotate(getson(fa[p])==getson(p)?fa[p]:p);
          if(!to) root=p;
      }
      inline void build(int l,int r,int f=0) {
          if(r<l) return;
          int mid=(l+r)>>1;
          if(!root) root=mid;
          init(mid,mid-1,f);
          if(l==r) return;
          build(l,mid-1,mid),build(mid+1,r,mid),pushup(mid);
      }

  public:
      int val[N];
      Splay(const int n=0) {build(1,n+2);}
      inline int kth(int k) {
          int p=root; pushdown(p);
          while(1) {
              if(k>size[ch[p][0]]+cnt[p]) k-=size[ch[p][0]]+cnt[p],p=ch[p][1],pushdown(p);
              else if(k>size[ch[p][0]]) return splay(p),p;
              else p=ch[p][0],pushdown(p);
          }
      }
      inline void reverse(int l,int r) {
          int pre=kth(l-1),nxt=kth(r+1);
          splay(pre),splay(nxt,pre); 
          lazy[ch[nxt][0]]^=1;
      }
      inline void print(signed char c=-1,int p=0) {
          if(!p) p=root; pushdown(p);
          if(ch[p][0]) print(-1,ch[p][0]);
          if(p!=1 && p!=n+2) std::cout<<val[p]<<" ";
          if(ch[p][1]) print(-1,ch[p][1]);
          if(c!=-1) std::cout<<c;
      }
  };
  int main() {
      std::ios::sync_with_stdio(0);
      std::cin.tie(0);std::cout.tie(0);
      std::cin>>n>>m;
      Splay s {n};
      for(int i=1;i<=m;++i) {
          int l,r;
          std::cin>>l>>r;
          s.reverse(l+1,r+1);
      }
      s.print('\n');
      return 0;
  }

这么写是对的,把 publicval[N] 放进 private 里面,单独写:

int fa[N],ch[N][2],cnt[N],size[N],lazy[N],root;
int val[N];

也是对的,但是如果写成:

int fa[N],ch[N][2],cnt[N],val[N],size[N],lazy[N],root;

就 WA 后三个点

为什么!为什么!为什么!

求解答!


by __er @ 2023-05-11 19:39:00

@MichaelWong 事实上我用了您 WA 后三个点的写法交了一发过了


by MichaelWong @ 2023-05-11 19:40:19

怀疑过是赋初值,在构造函数里加了 memset(val,0,sizeof val) 还是不行,但是给 val[N] 的声明换个位置就对了

之前还交过一个对的,把 init 函数里的 ch[p][0]=ch[p][1]=0 改成 ch[p][0]=ch[p][1] 就对了

现在 C++ 这么玄学了吗???


by MichaelWong @ 2023-05-11 19:41:08

@__er 啊,可是我交了三次都没对?好玄学


by Tibrella @ 2023-05-11 19:41:42

越界了吧


by MichaelWong @ 2023-05-11 19:44:11

@Tibrella 把 1e5+5 改成 2e5+7,过了

感谢!但是,为什么会越界呢?又为什么没有 RE 呢?


by catandcode @ 2023-05-11 19:46:36

@MichaelWong 把你的范围改成了1.01e5 T了。


by MichaelWong @ 2023-05-11 19:46:56

@catandcode


by Tibrella @ 2023-05-11 19:53:34

@MichaelWong 因为数组相当于指针,访问 f[n] 就相当于访问 *(f+n),而 C++ 对数组越界检查并不严格...如果那个地址正好存着一个数字,就能够返回一个正常的值,结果就不会报 RE。

另外,C++ 的一切未定义行为都没有准确的结果,出现什么问题都看 RP(


by Tibrella @ 2023-05-11 19:54:04

@MichaelWong 至于为什么越界,我不会 splay(


by MichaelWong @ 2023-05-11 19:54:52

@Tibrella 嗷嗷彳亍()跪谢 dalao QAQ


|