算法1

(线段树合并) $O(nlogn)$

参考洛谷P2824
一篇比较详细的题解

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=1e5+10;
int n,m,top,tot;
int rt[N],stk[N*40],op[N];
struct node{
    int l,r,x;
}q[N*40];
set<int>s;
inline int newnode(){return top?stk[top--]:++tot;}
inline void del(int u){q[stk[++top]=u]={0,0,0};}
void upd(int &u,int l,int r,int p)
{
    q[u=++tot].x=1;
    if(l==r) return;
    int m=(l+r)>>1;
    if(p<=m) upd(q[u].l,l,m,p);
    else upd(q[u].r,m+1,r,p);
}
void print(int u,int l,int r,int f)
{
    if(!u) return;
    if(l==r) cout<<l<<" ";
    int m=(l+r)>>1;
    if(f)
    {
        print(q[u].l,l,m,f);
        print(q[u].r,m+1,r,f);
    }
    else
    {
        print(q[u].r,m+1,r,f);
        print(q[u].l,l,m,f);
    }
}
void split(int x,int &y,int k,int f)
{
    if(!x) return;
    y=newnode();
    if(f)
    {
        int v=q[q[x].l].x;
        if(k<=v)
        {
            if(k<v) split(q[x].l,q[y].l,k,f);
            swap(q[x].r,q[y].r);
        }
        else split(q[x].r,q[y].r,k-v,f);
    }
    else
    {
        int v=q[q[x].r].x;
        if(k<=v)
        {
            if(k<v) split(q[x].r,q[y].r,k,f);
            swap(q[x].l,q[y].l);
        }
        else split(q[x].l,q[y].l,k-v,f);
    }
    q[y].x=q[x].x-k;
    q[x].x=k;
}
int merge(int x,int y)
{
    if(!x||!y) return x+y;
    q[x].x+=q[y].x;
    q[x].l=merge(q[x].l,q[y].l);
    q[x].r=merge(q[x].r,q[y].r);
    del(y);
    return x;
}
auto spl(int x)
{
    auto it=s.lower_bound(x);
    if(*it==x) return it;
    --it;split(rt[*it],rt[x],x-*it,op[x]=op[*it]);
    return s.insert(x).first;
}
int main(void)
{
    sync;
    cin>>n>>m;
    s.insert(n+1);
    for(int i=1;i<=n;++i)
    {
        upd(rt[i],1,n,i);
        s.insert(i);
    }
    while(m--)
    {
        int o,l,r=n;
        cin>>o>>l;
        if(o==0) r=l,l=1;
        auto L=spl(l),R=spl(r+1);
        for(auto it=++L;it!=R;++it)
            rt[l]=merge(rt[l],rt[*it]);
        op[l]=o;s.erase(L,R);
    }
    for(int x:s)
    {
        if(x==n+1) break;
        print(rt[x],1,n,op[x]);
    }
    return 0;
}
//考虑边界！！！
//Think TWICE, Code ONCE!