显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstdarg>
#include <algorithm>
#include <vector>
#include <cctype>
#include <queue>
#include <ctime>
using namespace std;
#define BT __attribute__((optimize("O3")))
struct node
{
node *ls, *rs;
int key, value;
int size;
int rev;
#define SIZE(x) ((x)?(x)->size:0)
BT
inline node(int v):key(rand()), value(v)
{
ls = rs = NULL;
size = 1;
rev = 0;
}
BT
inline void reverse()
{
if(!this)return;
swap(ls, rs);
rev ^= 1;
}
BT
inline void pushdown()
{
if(!this)return;
if(rev)
{
ls->reverse();
rs->reverse();
rev = 0;
}
}
BT
inline void pushup()
{
size = 1+SIZE(ls)+SIZE(rs);
}
};
typedef node *pnode;
typedef pair<node *, node *>droot;
BT
__attribute__((fastcall)) node *merge(node *a, node *b)
{
if(!a)return b;
if(!b)return a;
if(a->key < b->key)
{
a->pushdown();
a->rs = merge(a->rs, b);
a->pushup();
return a;
}else
{
b->pushdown();
b->ls = merge(a, b->ls);
b->pushup();
return b;
}
}
BT
__attribute__((fastcall)) droot split(node *x, int k)
{
if(!x)return droot(NULL, NULL);
x->pushdown();
droot r;
if(SIZE(x->ls) >= k)
{
r = split(x->ls, k);
x->ls = r.second;
x->pushup();
r.second = x;
}else
{
r = split(x->rs, k-SIZE(x->ls)-1);
x->rs = r.first;
x->pushup();
r.first = x;
}
return r;
}
BT
int kth(node *x, int k)
{
if(!x || k > SIZE(x) || k <= 0)return 0;
int s = SIZE(x->rs);
if(k == s+1)return x->value;
else if(k <= s)return kth(x->rs, k);
else return kth(x->ls, k-s-1);
}
BT
int rank(node *x, int v)
{
if(!x)return 0;
if(v < x->value)
return rank(x->ls, v);
else
return rank(x->rs, v)+SIZE(x->ls)+1;
}
BT
node* insert(node *root, int v)
{
int k = rank(root, v);
droot x = split(root, k);
node *nd = new node(v);
return merge(merge(x.first, nd), x.second);
}
BT
node *build(int *a, int n)
{
pnode *stk = new pnode[n];
node *last;
int tp = 0;
for(int i = 1; i <= n; i++)
{
node *p = new node(i);
last = NULL;
while(tp && stk[tp-1]->key > p->key)
{
stk[tp-1]->pushup();
last = stk[tp-1];
stk[--tp] = NULL;
}
if(tp)stk[tp-1]->rs = p;
p->ls = last;
stk[tp++] = p;
}
while(tp)stk[--tp]->pushup();
node *r = stk[0];
delete []stk;
return r;
}
char buf[1<<18], *fs, *ft;
BT
inline char readc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),fs==ft))?0:*fs++;
}
BT
int fast_read()
{
int r;
char c;
bool s = false;
while(c = readc())
{
if(c >= '0' && c <= '9')
{
r = c^0x30;
break;
}else if(c == '-')s = true;
}
while(isdigit(c = readc()))
r = (r<<3)+(r<<1)+(c^0x30);
return s?-r:r;
}
char obuf[1<<23];
char *poi = obuf;
char tmpb[14];
BT
__attribute__((fastcall)) inline void write_int(int n)
{
if(!n)
{
*poi++ = '0';
*poi++ = ' ';
return;
}
register int p = 0;
while(n)
{
int k = n;
k /= 10;
tmpb[++p] = n-(k<<3)-(k<<1);
n = k;
}
for(register int i = p; i >= 1; --i)
*poi++ = tmpb[i]+'0';
*poi++ = ' ';
}
BT
inline void putbuf()
{
fwrite(obuf, 1, poi-obuf, stdout);
}
BT
__attribute__((fastcall)) void dfs(node *u)
{
if(!u)return;
u->pushdown();
dfs(u->ls);
write_int(u->value);
dfs(u->rs);
}
int d[100002];
BT
int main()
{
//freopen("test_data.txt", "r", stdin);
//freopen("test_data.out", "w", stdout);
freopen("sph.in", "r", stdin);
freopen("sph.out", "w", stdout);
srand(time(NULL));
int n, m;
n = fast_read();
m = fast_read();
// for(int i = 1; i <= n; i++)
// d[i] = i;
node *t = build(d, n);
while(m--)
{
int l, r;
l = fast_read();
r = fast_read();
droot p1 = split(t, l-1);
droot p2 = split(p1.second, r-l+1);
p2.first->reverse();
t = merge(p1.first, merge(p2.first, p2.second));
}
dfs(t);
putbuf();
return 0;
}
sxysxy