[蓝桥杯 2021 省 B] 双向排序 (线段树)

调了整整5个小时,结果发现自己建树的方式有误,气死我了气死我了,比较好的一道线段树(虽然我不会-----

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,res,point;
vector<int>v[2]; // 用于存储结果的数组，下标0表示sum为0，下标1表示sum为1

struct node
{
    int l,r,sum,add; // l表示左端点，r表示右端点，sum表示[l, r]区间内sum的个数，add表示懒惰标记
}tr[N*2]; // 线段树的节点数组

void pushup(int u)
{
    tr[u].sum=tr[2*u].sum+tr[2*u+1].sum; // 合并子节点的sum值更新父节点的sum值
}

void pushdown(int u)
{
    if(tr[u].add==-1) return; // 如果没有懒惰标记，直接返回
    auto &root=tr[u],&left=tr[2*u],&right=tr[2*u+1]; // 引用父节点、左子节点、右子节点
    left.add=root.add,left.sum=(left.r-left.l+1)*root.add; // 更新左子节点的懒惰标记和sum值
    right.add=root.add,right.sum=(right.r-right.l+1)*root.add; // 更新右子节点的懒惰标记和sum值
    root.add=-1; // 清除父节点的懒惰标记
}

void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,1,-1}; // 叶节点初始化，sum为1，懒惰标记为-1
    else{
        tr[u]={l,r}; // 非叶节点初始化
        int mid=(l+r)>>1;
        build(2*u,l,mid); // 递归构建左子树
        build(2*u+1,mid+1,r); // 递归构建右子树
        pushup(u); // 合并子节点的信息更新父节点
    }
}

void modify1(int u,int val)
{
    int num=tr[u].r-tr[u].l+1-tr[u].sum; // 当前节点区间内0的个数
    if(num<=val){
        tr[u].sum=tr[u].r-tr[u].l+1;
        tr[u].add=1; // 更新懒惰标记为1，表示当前区间内的sum全部变为1
        return;
    }
    pushdown(u); // 将当前节点的懒惰标记下传到子节点
    auto &left=tr[2*u],&right=tr[2*u+1];
    int l_num=left.r-left.l+1-left.sum; // 左子节点区间内0的个数
    int r_num=right.r-right.l+1-right.sum; // 右子节点区间内0的个数
    if(l_num>=val) modify1(2*u,val); // 如果左子节点区间内的0个数足够，递归更新左子节点
    else modify1(2*u,l_num),modify1(2*u+1,val-l_num); // 否则分别更新左右子节点
    pushup(u); // 更新当前节点的信息
}

void modify0(int u,int val)
{
    int num=tr[u].sum; // 当前节点区间内1的个数
    if(val>=num){
        tr[u].sum=0,tr[u].add=0; // 更新当前节点的sum为0，懒惰标记为0
        return;
    }
    pushdown(u); // 将当前节点的懒惰标记下传到子节点
    auto &left=tr[2*u],&right=tr[2*u+1];
    int l_num=left.sum; // 左子节点区间内1的个数
    int r_num=right.sum; // 右子节点区间内1的个数
    if(l_num>=val) modify0(2*u,val); // 如果左子节点区间内的1个数足够，递归更新左子节点
    else modify0(2*u,l_num),modify0(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; // 叶节点直接返回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()
{
    cin>>n>>m;
    build(1,1,n); // 构建线段树
    point=1;
    while(m--){
        int op,x;
        cin>>op>>x;
        if(op==1){
            if(point<=x) continue;
            modify1(1,point-x); // 将前面的0变为1
            point=x;
        }
        else{
            if(point>x) continue;
            modify0(1,x-point+1); // 将后面的1变为0
            point=x+1;
        }
    }
    for(int i=1;i<=n;i++){
        if(query(1,i)==0) v[0].push_back(i); // 根据sum值判断属于哪个分组
        else v[1].push_back(i);
    }
    for(int i=v[0].size()-1;i>=0;i--) cout<<v[0][i]<<" "; // 输出结果
    for(int i=0;i<v[1].size();i++) cout<<v[1][i]<<" ";
    return 0;
}