Cgod @ 2018-02-21 21:38:54
本地测试秒出解,洛谷上TLE
#include<iostream>
#include<cstdio>
#include<algorithm>
#define lc ch[x][0]
#define rc ch[x][1]
#define gt getchar()
#define rg register
using namespace std;
const int N=5e4+5;
int f[N],ch[N][2],lz[N],root,s[N],cnt,val[N],n,m;
inline int in()
{
int k=0,p=1;
char ch=gt;
while((ch>'9'||ch<'0')&&ch!='-')ch=gt;
if(ch=='-')p=-1,ch=gt;
while(ch>='0'&&ch<='9')k=(k<<3)+(k<<1)+(ch^48),ch=gt;
return k*p;
}
inline void clear(int x){ch[x][0]=ch[x][1]=f[x]=lz[x]=0;}
inline int get(int x){return ch[f[x]][1]==x;}
inline void maintain(int x){s[x]=s[lc]+s[rc]+1;}
inline void update(int x)
{
if(!x)return;
if(lz[x])
{
lz[lc]^=1,lz[rc]^=1,lz[x]^=1;
swap(lc,rc);
}
return;
}
inline void rotate(int x)
{
update(f[x]);update(x);
int fa=f[x],gr=f[fa],p=get(x);
ch[fa][p]=ch[x][p^1];f[ch[fa][p]]=fa;
ch[x][p^1]=fa;f[fa]=x;f[x]=gr;
if(gr)
{
int d=ch[gr][1]==fa;
ch[gr][d]=x;
}
maintain(fa);maintain(x);
}
inline void splay(int x,int mu)
{
for(int fa;(fa=f[x])!=mu;rotate(x))
if(f[fa]!=mu)
rotate(get(x)==get(fa)?fa:x);
if(!mu)root=x;maintain(x);
}
int init(int l,int r,int fa)
{
int x=++cnt,mid=(l+r)>>1;
f[x]=fa,val[x]=mid;
if(l<mid)lc=init(l,mid-1,x);
if(r>mid)rc=init(mid+1,r,x);
maintain(x);
}
inline int kth(int k,int x)
{
update(x);
int d=s[lc];
if(k==d+1)return x;
if(k<=d)return kth(k,lc);
return kth(k-d-1,rc);
}
void print(int x)
{
if(x)
{
update(x);
print(lc);
if(val[x]>=1&&val[x]<=n)printf("%d ",val[x]);
print(rc);
}
}
int main()
{
n=in();
root=init(0,n+1,0);
m=in();
while(m--)
{
int l=in(),r=in();
l=kth(l,root);r=kth(r+2,root);
splay(l,0),splay(r,l);
lz[ch[r][0]]^=1;
}
print(root);
return 0;
}
by FlashHu @ 2018-02-21 22:19:23
@cx233666
So careless......
加一句``` return x
就好啦
by FlashHu @ 2018-02-21 22:20:51
@cx233666 有个警告,还是过了
by Tyher @ 2018-02-22 07:27:31
似乎回到了我当初hhh
by λᴉʍ @ 2018-02-22 18:54:11
@cx233666 %%%%%%%%%%%