Splay类封装究极玄学现象,求解答
查看原帖
Splay类封装究极玄学现象,求解答
765446
MichaelWong楼主2023/5/11 19:36

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

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

就是这个代码:

  #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;
  }

这么写是对的,把 public 的 val[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 后三个点

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

求解答!

2023/5/11 19:36
加载中...