lsy263 @ 2019-01-14 23:45:13
连样例都过不去
@ouuan
dalao您一定会qwq
root不知道为什么变成0,然后就死循环了
#include<iostream>
#define INF 0x7fffffff
using namespace std;
int root,tot;
const int SIZE=1e6;
struct TR{int tag,size,val,ch[2],f;}t[SIZE];
namespace SPLAY
{
#define LS t[u].ch[0]
#define RS t[u].ch[1]
void pushdown(int u)
{
t[u].tag=0;
t[LS].tag^=1,t[RS].tag^=1;
//LS+=RS,RS=LS-RS,LS-=RS;
swap(LS,RS);
}
inline void Link(int f, int son, int k)
{
if(f) t[f].ch[k] = son;
if(son) t[son].f = f;
}
void pushup(int u)
{
t[u].size=t[LS].size+t[RS].size+1;
}
void rotate(int x)
{
int y=t[x].f;
int z=t[y].f;
int kx=t[y].ch[1]==x;
int ky=t[z].ch[1]==y;
// Link(y,t[x].ch[kx],kx);
// Link(x,y,kx);
// Link(z,x,ky);
//pushup(z);
Link(y,t[x].ch[kx^1],kx);
Link(x,y,kx^1);
Link(z,x,ky);
pushup(y);
pushup(x);
}
void splay(int x,int to)
{
//
while(t[x].f!=to)
{
int y=t[x].f;
int z=t[y].f;
//if(t[z].tag)pushdown(z);
//if(t[y].tag)pushdown(y);
//if(t[x].tag)pushdown(x);
if(z!=to)rotate((t[y].ch[0]==x) ^ (t[z].ch[0]==y)?x:y);
rotate(x);
}
if(!to) root=x;
}
void find(int x)
{
int u=root;
if(!u)return;
while(t[u].ch[ x>t[u].val ]&&x!=t[u].val)
{
if(t[u].tag)pushdown(u);
u=t[u].ch[ x>t[u].val ];
}
splay(u,0);
}
void insert(int x)
{
int u=root,f=0;
while(u)f=u,u=t[u].ch[ x>t[u].val ];
u=++tot;
if(f)t[f].ch[ x>t[f].val ]=u;
t[u].f=f;
t[u].val=x;
t[u].size=1;
LS=RS=t[u].tag=0;
if(!root)root=u;
splay(u,0);
}
int lower(int x)
{
find(x);
if(t[root].val<x)return root;
int u=root;
u=LS;
while(RS)u=RS;
splay(u,0);
return u;
}
int upper(int x)
{
find(x);
if(t[root].val>x)return root;
int u=root;
u=RS;
while(LS)u=LS;
splay(u,0);
return u;
}
int Kth(int k) //注意是改变第x大不是x号
{
int u=root;
while(true)
{
if(t[u].tag)pushdown(u);
if(k<=t[LS].size)u=LS;
else
{
k-=t[LS].size+1;
if(!k)return u;
u=RS;
}
}
}
void change(int l,int r)
{
int x=Kth(l-1);
int y=Kth(r+1);
splay(x,0);
splay(y,x);
int u=root;u=RS;u=LS;
t[u].tag^=1;
}
void midroot(int u)
{
if(t[u].tag)pushdown(u);
if(LS)midroot(LS);
if(t[u].val!=INF&&t[u].val!=-INF)
cout<<t[u].val<<" ";
if(RS)midroot(RS);
}
}
using namespace SPLAY;
int main()
{
freopen("data.in","r",stdin);
int n,m;cin>>n>>m;
t[0].size=0;
insert(INF),insert(-INF);
t[1].size=t[2].size=0;
for(int i=1;i<=n;++i)
insert(i);
int l,r;
while(m--)
{
cin>>l>>r;
change(l,r);
}
midroot(root);
return 0;
}
by ouuan @ 2019-01-19 12:16:19
@lsy263 首先你要明白序列Splay中“大小”指的是在序列中位置的先后,而不是下标的大小。不知道你是不是这里理解有问题...
by lsy263 @ 2019-01-19 19:23:03
@ouuan 原来不是元素值的大小吗....qwq