自动搬运

查看原文

来自洛谷，原作者为

	基地A_I 现实和理想之间，不变的是跋涉，暗淡与辉煌之间，不变的是开拓。

搬运于2025-08-24 22:01:22，当前版本为作者最后更新于2019-06-02 00:35:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简化题意

• 给出一个n长序列，m次修改，支持两种操作

1.add 将区间$[l ,r]$中的每一个数 对 $k$ 取 $max$

2.remove 将区间$[l ,r]$中的每一个数 对 $k$ 取 $min$

题目思路

两个懒标记（add，rem）意思同上，分情况讨论传递标记(乍看不可做，想一下怎么推重复标记就懂了qwq)

具体实现

（如果你想了很久后还是不知道如何下手，再看这部分）

（最好你能拿出笔来边画边理解）

• $Max[p]$，$Min[p]$ 分别是区间最大，区间最小。

我们以 Max标记的下传为例 (即 将区间$[l ,r]$中的每一个数 对 $k$ 取 $max$)

1. 如果 $Min[p]$ < k 那么 $Min[p]$ = k ((如果)区间最小比较小，我们要更新它)
2. 如果 $Max[p]$ < k 那么 $Max[p]$ = k;((如果)$Max$也比$k$小了，同样更新)
3. 注意下传标记时$k$不就是父亲的懒标记$Max$吗？ 所以$Max$ = 0；

Min的标记下传同理，举一反三就可以了

Code

（码风不好，请勿喷）

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#define N 2000007
using namespace std;
int n,m;
struct Segment_Tree	//线段树结构体 
{
    int Max[N<<2],Min[N<<2];	//懒标记 
    inline int ls(int p) {return p<<1;}	//左子树 
    inline int rs(int p) {return p<<1|1;}	//右子树 
    void fx(int p,int k)	//Max标记传递 ，p节点编号，k传递值 
	{
		if(Min[p]<k) Min[p] = k;	//Min比k小，更新Min 
		if(Max[p]<k) Max[p] = k;	//连Max都比k小，更新MMax 
    }
    void fi(int p,int k)	//Min标记传递，p节点编号，k传递值 
	{
		if(Max[p]>k) Max[p] = k;	//Max比k要大，缩小Max 
		if(Min[p]>k) Min[p] = k;	//Min都比k大，k更小，值取k 
    }
//    释放懒标记 
    void push_down(int p) {
//        更新Max 
		fx(ls(p),Max[p]);
        fx(rs(p),Max[p]);
//        更新Min 
		fi(ls(p),Min[p]);
        fi(rs(p),Min[p]);
//        Max 和 Min 回归初始状态 
		Max[p] = 0;
        Min[p] = 0x7fffffff;
    }
//    		修改区间[nl,nr]	当前节点p,代表区间[l,r] 修改数k	,tag判断是操作add还是操作rem 
	void update(int nl,int nr,int p,int l,int r,int k,bool tag)
    {
//    	在范围内 
        if(nl<=l && r<=nr)
        {
//        	tag==0 代表add操作，更新Max 
            if(tag==0) fx(p,k);
//            否则更新Min 
            else fi(p,k);
            return ;
        }
        int mid = (l+r)>>1;
//        释放懒标记 
        push_down(p);
        if(nl<=mid) update(nl,nr,ls(p),l,mid,k,tag);
        if(nr>mid) update(nl,nr,rs(p),mid+1,r,k,tag);
//        push_up(p);
    }
    void Query(int p,int l,int r)
    {
//    	依次输出 叶节点的Max和Min是一样的 
        if(l==r) {printf("%d\n",Max[p]); return;}
        int mid = (l+r)>>1;
//        记得先释放懒标记，更新值 
        push_down(p);
//        继续递归 
        Query(ls(p),l,mid);
        Query(rs(p),mid+1,r);
    }
}Tree;	//定义一棵线段树Tree 
int main()
{
    scanf("%d%d",&n,&m);
//    把Min数组全直无穷大 
    for(int i=1;i<=n<<2;++i)
    	Tree.Min[i] = 0x7fffffff;
    for(int i=1;i<=m;++i)
    {
        int L,R,h,t;	//修改区间[L,R],修改值h,和操作t 
        scanf("%d%d%d%d",&t,&L,&R,&h);
//        题目从0开始编号，我习惯从一开始，故+1 
        Tree.update(L+1,R+1,1,1,n,h,t-1);
    }
//    输出结果 
    Tree.Query(1,1,n); 
    return 0;
}