_gifbmp @ 2019-10-05 13:45:31
#include<cstdio>
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
struct Node *null;
struct Node{
Node *ch[2],*fa;
int val,cnt,size,mark;
Node(int v=0){ch[0]=ch[1]=fa=null;val=v;cnt=size=1;mark=0;}
bool get(){return fa->ch[1]==this;}
void push_up(){size=cnt+ch[0]->size+ch[1]->size;}
};
struct Splay{
Node *root;
Splay(){
null=new Node(),null->cnt=null->size=0;
null->ch[0]=null->ch[1]=null->fa=null;
root=null;
insert(-INF);
insert(INF);
}
void push_down(Node *x){
if(!(x->mark))
return ;
x->ch[0]->mark^=1;
x->ch[1]->mark^=1;
x->mark=0;
Node *tmp=x->ch[0];
x->ch[0]=x->ch[1];
x->ch[1]=tmp;
}
void clear(Node *x){
if(x==null)
return ;
clear(x->ch[0]);
clear(x->ch[1]);
delete x;
}
void rotate(Node *x){
Node *y=x->fa,*z=y->fa;
int type=x->get();
z->ch[y->get()]=x;x->fa=z;
y->ch[type]=x->ch[!type];
x->ch[!type]->fa=y;
x->ch[!type]=y;
y->fa=x;
y->push_up();
}
void splay(Node *x,Node *goal){
while(x->fa!=goal){
Node *y=x->fa;
if(y->fa!=goal)
rotate(x->get()==y->get()?y:x);
rotate(x);
}
x->push_up();
if(goal==null)
root=x;
}
Node *kth(int x){
Node *u=root;
x++;
while(1){
if(x<=u->ch[0]->size)
u=u->ch[0];
else if(x>u->ch[0]->size+u->cnt)
x-=u->ch[0]->size+u->cnt,u=u->ch[1];
else return u;
}
}
void insert(int x){
Node *u=root,*f=null;
while(u!=null&&x!=u->val)
f=u,u=u->ch[x>u->val];
if(u!=null)
u->cnt++;
else{
u=new Node(x);
if(f!=null)
f->ch[x>f->val]=u,u->fa=f;
}
splay(u,null);
}
void reverse(int l,int r){
Node *ll=kth(l-1),*rr=kth(r+1);
splay(ll,null);
splay(rr,ll);
root->ch[1]->ch[0]->mark^=1;
}
void print(Node *x){
push_down(x);
if(x->ch[0]!=null)
print(x->ch[0]);
if(x->val>0&&x->val<=n)
printf("%d ",x->val);
if(x->ch[1]!=null)
print(x->ch[1]);
}
}tree;
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n+1;i++)
tree.insert(i);
while(m--){
int l,r;
scanf("%d%d",&l,&r);
tree.reverse(l,r);
}
tree.print(tree.root);
return 0;
}by 神山识 @ 2019-10-05 13:46:09
标题党
by Purple_sword @ 2019-10-05 13:47:07
标题。。。
by 颓废的鲈鱼 @ 2019-10-05 13:51:02
qndmx
by 小main包 @ 2019-10-05 13:51:06
%%%我都只会treap
by Aestas16 @ 2019-10-05 13:52:43
@_gifbmp
#include <cstdio>
#include <algorithm>
#define N 1e5+10
#define inf 0x3f3f3f3f
template<class T>void fr(T &a) {
T s=0,w=1;a=0;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
a=w*s;
}
template<class T>T in() {T a;fr(a);return a;}
struct Node *null;
struct Node {
Node *ch[2],*fa;
int val,cnt,sz;
bool rev;
Node(int v=0) {ch[0]=ch[1]=fa=null,val=v,cnt=sz=1,rev=0;}
bool get() {return fa->ch[1]==this;}
void reverse() {rev^=1,std::swap(ch[0],ch[1]);}
void pushup() {sz=ch[0]->sz+ch[1]->sz+cnt;}
void pushdown() {
if(rev)ch[0]->reverse(),ch[1]->reverse(),rev=0;
}
};
struct Splay {
Node *rt;
Splay() {
null=new Node(),null->cnt=null->sz=0;
null->ch[0]=null->ch[1]=null->fa=null;
rt=null;
insert(-inf),insert(inf);
}
void clear(Node *x) {
if(x==null)return ;
clear(x->ch[0]),clear(x->ch[1]);
delete x;
}
void rotate(Node *x) {
Node *y=x->fa,*z=y->fa;
int k=x->get(),f=y->get();
z->ch[f]=x,x->fa=z;
y->ch[k]=x->ch[!k],x->ch[!k]->fa=y;
x->ch[!k]=y,y->fa=x,y->pushup();
}
void splay(Node *x,Node *g) {
while(x->fa!=g) {
Node *y=x->fa;
if(y->fa!=g)rotate(x->get()==y->get()?y:x);
rotate(x);
}
x->pushup();
if(g==null)rt=x;
}
void find(int v) {
if(rt==null)return ;
Node *u=rt;
while(v!=u->val&&u->ch[v>u->val]!=null)
u=u->ch[v>u->val];
splay(u,null);
}
int rank(int v) {
find(v);
return rt->ch[0]->sz;
}
Node *kth(int k) {
Node *u=rt;k++;
while(1) {
u->pushdown();
if(k<=u->ch[0]->sz)u=u->ch[0];
else if(k>u->ch[0]->sz+u->cnt)
k-=u->ch[0]->sz+u->cnt,u=u->ch[1];
else return u;
}
}
Node *pre(int v) {
find(v);
if(rt->val<v)return rt;
Node *u=rt->ch[0];
while(u->ch[1]!=null)u=u->ch[1];
return u;
}
Node *suc(int v) {
find(v);
if(rt->val>v)return rt;
Node *u=rt->ch[1];
while(u->ch[0]!=null)u=u->ch[0];
return u;
}
void insert(int v) {
Node *u=rt,*f=null;
while(u!=null&&v!=u->val)f=u,u=u->ch[v>u->val];
if(u!=null)u->cnt++;
else {
u=new Node(v);
if(f!=null)f->ch[v>f->val]=u,u->fa=f;
}
splay(u,null);
}
void erase(int v) {
Node *lst=pre(v),*nxt=suc(v),*u;
splay(lst,null),splay(nxt,lst);
u=nxt->ch[0];
if(u->cnt>1)u->cnt--,splay(u,null);
else clear(nxt->ch[0]),nxt->ch[0]=null;
}
void reverse(int l,int r) {
splay(kth(l-1),null),splay(kth(r+1),rt);
rt->ch[1]->ch[0]->reverse();
}
}spt;
int main() {
int n=in<int>(),m=in<int>();
for(int i=1;i<=n;i++)spt.insert(i);
while(m--) {
int l=in<int>(),r=in<int>();
spt.reverse(l,r);
}
for(int i=1;i<=n;i++)printf("%d ",spt.kth(i)->val);
return 0;
}by _gifbmp @ 2019-10-05 13:52:56
@Naive_Cat orz
by Hjcc @ 2019-10-05 13:54:05
@Naive_Cat 可以复制吗
by 312_de_cat @ 2019-10-05 13:55:49
NO FISHING
by guoxinyugz @ 2019-10-05 13:55:49
离题，扣分！
by Provicy @ 2019-10-05 14:21:11
QNDMX