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;
}
这么写是对的,把 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 后三个点
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 嗷嗷彳亍()跪谢