P8747题解
SakurajiamaMai
·
·
题解
思路:
根据数据范围，可猜得每次操作只能是 \log 级别的复杂度。
本题有两种解题方法，个人认为用栈的思维度较高，这里用线段树的方法，简单易懂。利用线段树维护每一个需要降序或者升序的区间，然后利用数组从小到大储存每个数的状态。
这里难点在于如何维护区间内的升降序，重点说下。我们设升序为状态 1，降序为状态 0，再设一个中间分界点 point，那么如果此时我们要修改一个区间为升序，如果起点在 point 之后，我们就不需要修改了，降序也是同理。如果当前的升序区间不满足，需要从降序区间里改变，这里注意我们只需要修改较小数的状态即可。
$2$.如果升序操作把一部分降序的数变到了升序区，其实就是把为 $0$ 的数中较小的那几个数变为 $1$。
```cpp
#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;
}
```