区间与球
Sweetlemon
2019-11-04 09:31:15
### [IOI2014] Wall 砖墙
#### 题意
这是一道 IOI 原题。
给定一个初始全 $0$ 序列,有两种操作:
1. 对某区间内的所有数 $x$,令 $x=\max(t,x)$($t$ 是操作参数)
2. 对某区间内的所有数 $x$,令 $x=\min(t,x)$
求最后的序列。
#### 思路
这道题与“[[SCOI 2016] 萌萌哒](https://www.luogu.org/problem/P3295)”类似,如果每次区间操作都暴力地对区间内每一个数都进行调整,那么复杂度将无法承受。我们需要选择一种数据结构,直接对“区间”进行操作。
“萌萌哒”这道题中,操作之间互不影响,而且操作区间可以重叠,因此可以直接使用 st 表(若操作区间不可重叠,同样可使用 st 表,但操作区间要被二进制拆分成为 $O(\log l)$ 个)。但是在这道题中,不同的操作前后会有影响,因此我们可以使用线段树。
线段树的每一个点维护“已经对这个区间进行、但还没有对这个区间的孩子应用 (apply) 的限制”。如果我们把我们的数想象成一排金属球,那么 1 操作可以想象成用一块钢板从下往上推区间内的球,一直推到高度 $t$,使之不低于 $t$;2 操作可以想象成用一块钢板从上往下压,一直压到高度 $t$。于是“每个区间的限制”有两种,一种是向下压的板到达的最小高度,一种是向上推的板到达的最大高度。初始时长度大于 $1$ 的区间都没有限制——向下压的板的最小高度(记为 $n$)为 $\infty$,向上推的板的最大高度(记为 $m$)为 $0$;可以认为初始时长度为 $1$ 的区间的 $n$ 和 $m$ 都是 $0$。
现在考虑对一个区间进行 1 操作。用一块自下而上的上推钢板推这个区间,会有什么变化呢?如果原来的下界钢板低于 $t$,当然会被推到 $t$ 位置,否则不变;上界同理。因此,这个操作对这个区间的变化是 $m=\max(m,t),n=\max(n,t)$。
再考虑 2 操作,类似地,$m=\min(m,t),n=\min(n,t)$。
由于有些操作之间会相互影响,因此如果有一个要应用到孩子、但不应用到父亲区间的操作,就必须先把标记下传。标记下传也就是把之前 lazy tag 延迟应用的操作应用到孩子上,也就是对孩子进行 $1\ m,\ 2\ n$ 这两个操作——这两个操作的顺序无关紧要,因为在维护父节点的两个标记的时候,已经保证了这两块钢板 $m\le n$,因此这两个操作之间不会相互影响。
输出的时候直接输出叶子节点的 $m$ 或 $n$ 即可。由于上述过程中,叶子节点的 $m,n$ 始终相同——夹着单个球的板总是紧密合在一起的,因此输出哪一个都可以。
下面用一个小例子演示一下更新和标记下传的过程。
```text
5 2
1 1 3 2
2 3 4 1
```
为方便阅读,上面这个例子的下标**已调整为从 1 开始**。
初始时是这样。
![初始状态](https://cdn.luogu.com.cn/upload/image_hosting/c36laq34.png)
进行第一个操作后变成了这样。
![状态1](https://cdn.luogu.com.cn/upload/image_hosting/qiji4qlv.png)
虚线表示父节点的限制还没有应用到子节点上,因此实际上 $1\sim 3$ 这三个球已经被推到了 $2$ 的位置。
要进行第二个操作,线段树节点 $[1,3]$ 要进行标记下传,下传的结果是这样。
![状态1.5](https://cdn.luogu.com.cn/upload/image_hosting/ifvkbnft.png)
第二个操作的最终结果是这样。
![状态2](https://cdn.luogu.com.cn/upload/image_hosting/idc268a0.png)
可以用更复杂的例子来模拟,更好地弄懂这个设计。
#### 代码
```cpp
#include <cstdio>
#include <cctype>
#include <algorithm>
#define MAXIOLG 25
#define MAXN 2000005
#define MAX4N 8000005
#define INF 19260817
using namespace std;
typedef int io_t;
//快读快写
io_t shin[MAXIOLG];
io_t seto(void);
void ayano(io_t x,char spliter='\n');
//线段树节点
struct Ene{
int l,r,mxm,mnm;
//以下依次为节点区间左端点、右端点、m 值、n 值、左右儿子序号
#define L(x) ((stree[(x)]).l)
#define R(x) ((stree[(x)]).r)
#define MX(x) ((stree[(x)]).mxm)
#define MN(x) ((stree[(x)]).mnm)
#define LC(x) (((x)<<1))
#define RC(x) (((x)<<1)^1)
};
int n;
Ene stree[MAX4N]; //线段树
void build_tree(int root,int l,int r); //建树
void cmx(int root,int l,int r,int x); //1 操作
void cmn(int root,int l,int r,int x); //2 操作
void pushdown(int root); //标记下传,把父节点的操作应用到子节点
void output(int root); //输出答案
int main(void){
int q;
n=seto(),q=seto();
const int troot=1; //线段树根节点
build_tree(troot,1,n);
while (q--){
int op,l,r,x;
op=seto(),l=seto()+1,r=seto()+1,x=seto();
if (op==1)
cmx(troot,l,r,x);
else
cmn(troot,l,r,x);
}
output(troot);
return 0;
}
void build_tree(int root,int l,int r){
//建树
//初始时非叶节点没有限制
L(root)=l,R(root)=r,MX(root)=0,MN(root)=INF;
if (l==r)
//叶节点有限制, m=n=0
return MX(root)=MN(root)=0,void();
int mid=(l+r)>>1;
build_tree(LC(root),l,mid);
build_tree(RC(root),mid+1,r);
}
void cmx(int root,int l,int r,int x){
if (l<=L(root) && r>=R(root)){
//把限制标记在这个区间
//m,n 都取 max
MX(root)=max(MX(root),x);
MN(root)=max(MN(root),x);
return;
}
int mid=(L(root)+R(root))>>1;
pushdown(root);
(l<=mid)?(cmx(LC(root),l,r,x)):(void());
(r>mid)?(cmx(RC(root),l,r,x)):(void());
}
void cmn(int root,int l,int r,int x){
if (l<=L(root) && r>=R(root)){
//m,n 都取 min
MX(root)=min(MX(root),x),
MN(root)=min(MN(root),x);
return;
}
int mid=(L(root)+R(root))>>1;
pushdown(root);
(l<=mid)?(cmn(LC(root),l,r,x)):(void());
(r>mid)?(cmn(RC(root),l,r,x)):(void());
}
void pushdown(int root){
//标记下传
if (L(root)==R(root))
return;
//对左右儿子的 m,n 值都应用等效 2 操作
MX(LC(root))=min(MX(LC(root)),MN(root));
MX(RC(root))=min(MX(RC(root)),MN(root));
MN(LC(root))=min(MN(LC(root)),MN(root));
MN(RC(root))=min(MN(RC(root)),MN(root));
//对左右儿子的 m,n 值都应用等效 1 操作
MX(LC(root))=max(MX(LC(root)),MX(root));
MX(RC(root))=max(MX(RC(root)),MX(root));
MN(LC(root))=max(MN(LC(root)),MX(root));
MN(RC(root))=max(MN(RC(root)),MX(root));
//父节点的限制应用完毕,取消限制
MX(root)=0,MN(root)=INF;
}
void output(int root){
if (L(root)==R(root)){
ayano(MX(root));
return;
}
pushdown(root);
output(LC(root)),output(RC(root));
}
//以下两个函数为读入输出优化
io_t seto(void){
io_t x=0;
int symbol=0;
char ch=getchar();
while (!isdigit(ch))
(ch=='-')?(symbol=1):(0),
ch=getchar();
while (isdigit(ch))
x=(x*10)+(ch-'0'),
ch=getchar();
return (symbol)?(-x):(x);
}
void ayano(io_t x,char spliter){
if (!x){
putchar('0'),putchar(spliter);
return;
}
if (x<0)
putchar('-'),x=-x;
int len=0;
while (x){
io_t d=x/10;
shin[len++]=x-(d*10);
x=d;
}
while (len--)
putchar(shin[len]+'0');
putchar(spliter);
}
```