自动搬运

查看原文

来自洛谷，原作者为

	SakurajiamaMai 行则将至,道阻且长

搬运于2025-08-24 22:42:03，当前版本为作者最后更新于2023-08-13 23:44:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路:

根据数据范围，可猜得每次操作只能是 $\log$ 级别的复杂度。

本题有两种解题方法，个人认为用栈的思维度较高，这里用线段树的方法，简单易懂。利用线段树维护每一个需要降序或者升序的区间，然后利用数组从小到大储存每个数的状态。

这里难点在于如何维护区间内的升降序，重点说下。我们设升序为状态 $1$，降序为状态 $0$，再设一个中间分界点 point，那么如果此时我们要修改一个区间为升序，如果起点在 point 之后，我们就不需要修改了，降序也是同理。如果当前的升序区间不满足，需要从降序区间里改变，这里注意我们只需要修改较小数的状态即可。

$1$.如果降序操作把一部分升序的数变到了降序区，其实就是把为 $1$ 的数中较小的那几个数变为 $0$ 。

$2$.如果升序操作把一部分降序的数变到了升序区，其实就是把为 $0$ 的数中较小的那几个数变为 $1$。

#include<iostream>
#include<cstdio>
#include<vector>
//using namespace std;
const int N=1e5+10;
int n,m,point,op,x;
std::vector<int>a[2];// 用于存储结果的数组，下标0表示sum为0，下标1表示sum为1
struct node
{
    int l,r,sum,lazy;// l表示左端点，r表示右端点，sum表示[l, r]区间内sum的个数，add表示懒惰标记
}tr[N*3];
void pushup(int u)
{
    tr[u].sum=tr[2*u].sum+tr[2*u+1].sum;
}
void pushdown(int u)
{
    if(tr[u].lazy==-1) return;// 如果没有懒惰标记，直接返回
    auto &root=tr[u],&left=tr[2*u],&right=tr[2*u+1];
    left.lazy=root.lazy,left.sum=(left.r-left.l+1)*root.lazy;
    right.lazy=root.lazy,right.sum=(right.r-right.l+1)*root.lazy;
    root.lazy=-1;
}
void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,1,-1};
    else{
        tr[u]={l,r,0,-1};
        int mid=l+r>>1;
        build(2*u,l,mid),build(2*u+1,mid+1,r);
        pushup(u);
    }
}
void modify_1(int u,int val)
{
    int num=tr[u].r-tr[u].l+1-tr[u].sum;// 如果没有懒惰标记，直接返回
    if(num<=val){
        tr[u].sum=tr[u].r-tr[u].l+1;
        tr[u].lazy=1;// 更新懒惰标记为1，表示当前区间内的sum全部变为1
        return;
    }
    pushdown(u);
    int l_num=tr[2*u].r-tr[2*u].l+1-tr[2*u].sum;
    if(l_num>=val) modify_1(2*u,val);// 如果左子节点区间内的0个数足够，递归更新左子节点
    else modify_1(2*u,l_num),modify_1(2*u+1,val-l_num);
    pushup(u);
}
void modify_0(int u,int val) //同理
{
    int num=tr[u].sum;
    if(num<=val){
        tr[u].sum=0;
        tr[u].lazy=0;
        return;
    }
    pushdown(u);
    int l_num=tr[2*u].sum;
    if(l_num>=val) modify_0(2*u,val);
    else modify_0(2*u,l_num),modify_0(2*u+1,val-l_num);
    pushup(u);
}
int query(int u,int pos)
{
    if(tr[u].l==tr[u].r) return tr[u].sum;
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(pos<=mid) return query(2*u,pos);// 根据位置递归查询左子树或右子树
    else return query(2*u+1,pos);
}
int main()
{
    scanf("%d%d",&n,&m);
    build(1,1,n);
    point=1;
    while(m--){
        scanf("%d%d",&op,&x);
        if(op==1){
            if(point<=x) continue;
            modify_1(1,point-x);// 将前面的0变为1
            point=x;
        }
        else{
            if(point>x) continue;
            modify_0(1,x-point+1);// 将前面的0变为1
            point=x+1;
        }
    }
    for(int i=1;i<=n;i++){
        if(query(1,i)!=0) a[1].push_back(i); // 根据sum值判断属于哪个分组
        else a[0].push_back(i); 
    }
    for(int i=a[0].size()-1;i>=0;i--) printf("%d ",a[0][i]);
    for(auto i:a[1]) printf("%d ",i);
    return 0;
}