应该有人看见我霸屏的提交了吧……
就是这个代码:
#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 后三个点