区间与球

Sweetlemon

2019-11-04 09:31:15

Solution

### [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); } ```