1 #include <cstdio>  2 #include <cstdlib>  3 #include <cstring>  4 #include <algorithm>  5 using namespace std;  6 const double eps = 1e-8;  7 const int maxn = 100086;  8 int siz[maxn],pre[maxn],ch[maxn][2],rev[maxn],key[maxn];  9 int n,m,tot,root; 10 void update_rev(int r) 11 { 12     if (!r) 13         return; 14     swap(ch[r][0],ch[r][1]); 15     rev[r] ^= 1; 16 } 17 void push_up(int r) 18 { 19     siz[r] = siz[ch[r][0]] + siz[ch[r][1]] + 1; 20 } 21 void push_down(int r) 22 { 23     if (rev[r]) 24     { 25         update_rev(ch[r][0]); 26         update_rev(ch[r][1]); 27         rev[r] = 0; 28     } 29 } 30 void NewNode(int &r,int father,int k) 31 { 32     r = ++tot; 33     pre[r] = father; 34     ch[r][0] = ch[r][1] = 0; 35     key[r] = k; 36     rev[r] = 0; 37     siz[r] = 1; 38 } 39 void build(int &x,int l,int r,int father) 40 { 41     if (l > r) 42         return; 43     int mid = (l + r) >> 1; 44     NewNode(x,father,mid); 45     build(ch[x][0],l,mid-1,x); 46     build(ch[x][1],mid+1,r,x); 47     push_up(x); 48 } 49 void init() 50 { 51     root = tot = 0; 52     NewNode(root,0,-1); 53     NewNode(ch[root][1],root,-1); 54     build(ch[ch[root][1]][0],1,n,ch[root][1]); 55     push_up(root); 56     push_up(ch[root][1]); 57 } 58 void Rotate(int x,int kind) 59 { 60     int y = pre[x]; 61     push_down(y); 62     push_down(x); 63     ch[y][!kind] = ch[x][kind]; 64     pre[ch[x][kind]] = y; 65     if (pre[y]) 66         ch[pre[y]][ch[pre[y]][1] == y] = x; 67     pre[x] = pre[y]; 68     ch[x][kind] = y; 69     pre[y] = x; 70     push_up(y); 71 } 72 void Splay(int r,int goal) 73 { 74     push_down(r); 75     while (pre[r] != goal) 76     { 77         if (pre[pre[r]] == goal) 78         { 79             push_down(pre[r]); 80             push_down(r); 81             Rotate(r,ch[pre[r]][0] == r); 82         } 83         else 84         { 85             int y = pre[r]; 86             int kind = (ch[pre[y]][1] == y); 87             push_down(pre[y]); 88             push_down(y); 89             push_down(r); 90             if (ch[y][kind] == r) 91             { 92                 Rotate(y,!kind); 93                 Rotate(r,!kind); 94             } 95             else 96             { 97                 Rotate(r,kind); 98                 Rotate(r,!kind); 99             }100         }101     }102     push_up(r);103     if (goal == 0)104         root = r;105 }106 int Get_kth(int r,int k)107 {108     push_down(r);109     int t = siz[ch[r][0]] + 1;110     if (k == t)111         return r;112     if (k >= t)113         return Get_kth(ch[r][1],k-t);114     else115         return Get_kth(ch[r][0],k);116 }117 void Reverse(int u,int v)118 {119     Splay(Get_kth(root,u),0);120     Splay(Get_kth(root,v+2),root);121     update_rev(ch[ch[root][1]][0]);122     push_up(ch[root][1]);123     push_up(root);124 }125 void dfs(int r)126 {127     if (!r)128         return;129     push_down(r);130     dfs(ch[r][0]);131     if (r != -1 && key[r] != -1)        //-1设置的虚节点 132         printf("%d\n",key[r]);133     dfs(ch[r][1]);134 }135 int main(void)136 {137     #ifndef ONLINE_JUDGE138         freopen("in.txt","r",stdin);139     #endif140     while (~scanf ("%d%d",&n,&m))141     {142         init();143         for (int i = 0; i < m; i++)144         {145             int u,v;146             scanf ("%d%d",&u,&v);147             Reverse(u,n);148             Reverse(u,u+n-v-1);149         }150         dfs(root);151     }152     return 0;153 }