一道二分水题
读题，他要求满足条件的木棍最长的长度
发现，答案明显满足二分性（最终木根长度越小，可以分出的木棍数就越多）
所以，我们可以直接二分答案，假设当前二分出的答案为x
那么， 对于一个长度为y的木棍来说，它可以分出的最多的长度为x的木棍就是
所以，总共最多可以分出的，长度为x的木棍数就是：
我们将这个值和k比较一下，如果大于k，就说明可以分到x，就往右二分，否则就往左二分，即可
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
struct splay{
    int w,son[2],fa,laz,tot,cnt;
}t[N];
int al,root;
inline bool wy(int x){
    return t[t[x].fa].son[1]==x;
}
inline void update(int x){
    t[x].tot=(t[t[x].son[0]].tot+t[t[x].son[1]].tot+t[x].cnt);
}
inline void rotate(int x){
    int y=t[x].fa,z=t[y].fa,k=wy(x),w=t[x].son[k^1];
    t[y].son[k]=w,t[w].fa=y;
    t[x].fa=z,t[z].son[wy(y)]=x;
    t[x].son[k^1]=y,t[y].fa=x;
    update(y),update(x);
}
inline void splay(int x,int gol=0){
    while(t[x].fa!=gol){
        int y=t[x].fa,z=t[y].fa;
        if(z!=gol){
            if(wy(x)==wy(y)){
                rotate(y);
            }else{
                rotate(x);
            }
        }
        rotate(x);
    }
    if(!gol){
        root=x;
    }
}
inline void insert(int x){
    int now=root,fu=0;
    while(now){
        fu=now,now=t[now].son[x>t[now].w];
    }
    now=++al;
    if(fu){
        t[fu].son[x>t[now].w]=al;
    }
    t[now].w=x,t[now].fa=fu;
    t[now].tot=t[now].cnt=1;
    splay(now);
}
inline void down(int now){
    if(t[now].laz){
        swap(t[now].son[0],t[now].son[1]);
        t[t[now].son[0]].laz^=1;
        t[t[now].son[1]].laz^=1;
        t[now].laz=0;
    }
}
inline int kth(int k){
    int now=root;
    while(true){
        down(now);
        if(t[t[now].son[0]].tot>=k){
            now=t[now].son[0];
        }else if(t[t[now].son[0]].tot+t[now].cnt<k){
            k-=(t[t[now].son[0]].tot+t[now].cnt),now=t[now].son[1];
        }else{
            return now;
        }
    }
}
inline void reverse(int l,int r){
    int x=kth(l-1),y=kth(r+1);
    splay(x),splay(y,x);//这样splay后，y的左子树编号全为l-r
    t[t[y].son[0]].laz^=1;
}
int n,m;
inline void print(int now){
    down(now);
    if(t[now].son[0]){
        print(t[now].son[0]);
    }
    if(now>1&&now<n)
        printf("%d ",now-1);
    if(t[now].son[1]){
        print(t[now].son[1]);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    n+=2;
    for(int i=1;i<=n;++i){
        insert(i);
    }
    while(m--){
        int l,r;
        scanf("%d%d",&l,&r);
        ++l,++r;
        reverse(l,r);
    }
    print(root);
    return 0;
}