Sweetlemon 的博客

Sweetlemon 的博客

区间与球

posted on 2019-11-04 09:31:15 | under 题解 |

[IOI2014] Wall 砖墙

题意

这是一道 IOI 原题。

给定一个初始全 $0$ 序列,有两种操作:

  1. 对某区间内的所有数 $x$ ,令 $x=\max(t,x)$ ( $t$ 是操作参数)
  2. 对某区间内的所有数 $x$ ,令 $x=\min(t,x)$

求最后的序列。

思路

这道题与“[SCOI 2016] 萌萌哒”类似,如果每次区间操作都暴力地对区间内每一个数都进行调整,那么复杂度将无法承受。我们需要选择一种数据结构,直接对“区间”进行操作。

“萌萌哒”这道题中,操作之间互不影响,而且操作区间可以重叠,因此可以直接使用 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$ 始终相同——夹着单个球的板总是紧密合在一起的,因此输出哪一个都可以。

下面用一个小例子演示一下更新和标记下传的过程。

5 2
1 1 3 2
2 3 4 1

为方便阅读,上面这个例子的下标已调整为从 1 开始

初始时是这样。

初始状态

进行第一个操作后变成了这样。

状态1

虚线表示父节点的限制还没有应用到子节点上,因此实际上 $1\sim 3$ 这三个球已经被推到了 $2$ 的位置。

要进行第二个操作,线段树节点 $[1,3]$ 要进行标记下传,下传的结果是这样。

状态1.5

第二个操作的最终结果是这样。

状态2

可以用更复杂的例子来模拟,更好地弄懂这个设计。

代码

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