文艺平衡树FHQ-Treap-指针版
文艺平衡树 FHQ-Treap-指针版 代码存档
貌似这玩意厌氧啊
/**************************************************************
* Problem: 3391(FHQ-Treap-pointer)
* Author: Vanilla_chan
* Date: 20210402
**************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<limits.h>
#define IL inline
#define re register
#define LL long long
#define ULL unsigned long long
#ifdef TH
#define debug printf("Now is %d\n",__LINE__);
#else
#define debug
#endif
#ifdef ONLINE_JUDGE
char buf[1<<23],* p1=buf,* p2=buf,obuf[1<<23],* O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
using namespace std;
template<class T>inline void read(T& x)
{
char ch=getchar();
int fu;
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') fu=-1,ch=getchar();
x=ch-'0';ch=getchar();
while(isdigit(ch)) { x=x*10+ch-'0';ch=getchar(); }
x*=fu;
}
inline int read()
{
int x=0,fu=1;
char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') fu=-1,ch=getchar();
x=ch-'0';ch=getchar();
while(isdigit(ch)) { x=x*10+ch-'0';ch=getchar(); }
return x*fu;
}
int G[55];
template<class T>inline void write(T x)
{
int g=0;
if(x<0) x=-x,putchar('-');
do { G[++g]=x%10;x/=10; } while(x);
for(int i=g;i>=1;--i)putchar('0'+G[i]);putchar('\n');
}
#define N 100010
struct Treap
{
struct node
{
node *ls,*rs;
int val,k,sze;
bool flag;
void upd()
{
sze=1;
if(ls) sze+=ls->sze;
if(rs) sze+=rs->sze;
}
node(int v)
{
ls=rs=0;
val=v;
sze=1;
k=rand();
upd();
}
void work()
{
flag^=1;
swap(ls,rs);
}
void spread()
{
if(flag)
{
if(ls) ls->work();
if(rs) rs->work();
flag=0;
}
}
}*root;
node *merge(node *x,node *y)
{
if(!x) return y;
if(!y) return x;
if(x->k<y->k)
{
x->spread();
x->rs=merge(x->rs,y);
x->upd();
return x;
}
else
{
y->spread();
y->ls=merge(x,y->ls);
y->upd();
return y;
}
}
int sss(node *x)
{
if(x) return x->sze;
return 0;
}
void split(node *i,int k,node *&x,node *&y)
{
if(!i)
{
x=y=0;
return;
}
i->spread();
if(sss(i->ls)<k)
{
x=i;
split(i->rs,k-sss(i->ls)-1,i->rs,y);
}
else
{
y=i;
split(i->ls,k,x,i->ls);
}
i->upd();
}
void out(node *x)
{
x->spread();
if(x->ls) out(x->ls);
cout<<x->val<<" ";
if(x->rs) out(x->rs);
}
}tree;
Treap::node *a,*b,*c;
int n,m;
int main()
{
n=read();
m=read();
for(int i=1;i<=n;i++)
{
tree.root=tree.merge(tree.root,new Treap::node(i));
}
for(int i=1,l,r;i<=m;i++)
{
l=read();
r=read();
tree.split(tree.root,l-1,a,b);
tree.split(b,r-l+1,b,c);
b->work();
tree.root=tree.merge(a,tree.merge(b,c));
}
tree.out(tree.root);
return 0;
}