P1253 [yLOI2018] 扶苏的问题

题意简述

1. 给定区间 \([l, r]\) ，将区间内每个数都修改为 \(x\)
2. 给定区间 \([l, r]\) ，将区间内每个数都加上 \(x\)
3. 给定区间 \([l, r]\) ，求区间内的最大值

---

解题思路

就是维护一个最大值就行了

如果是操作 \(1\) ，就把 lazy 改成 \(x\)，并将 add 清零

如果是操作 \(2\) ，就。。。直接加

主要是这个

void pushdown(int p){
    if(tree[p].lazy!=-INF){
	tree[ls].lazy=tree[rs].lazy=tree[p].lazy;
	tree[ls].max=tree[rs].max=tree[p].lazy;
	tree[ls].add=tree[rs].add=0;
	tree[p].lazy=-INF;
    }
    else if(tree[p].add){
	tree[ls].add+=tree[p].add;
	tree[rs].add+=tree[p].add;
	tree[ls].max+=tree[p].add;
	tree[rs].max+=tree[p].add;
	tree[p].add=0;
    }
}

我们可以定义顺序为先赋值再增加

因为在修改的时候有这么一句话

   if(x<=l&&y>=r){
	tree[p].max=k;
	tree[p].lazy=k;
	tree[p].add=0;
	return;
    }

它保证了加法一定是在修改之后的

---

\(Code\)

#include <bits/stdc++.h>
#define ls p<<1
#define rs p<<1|1
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
const int N=1e6+10;
const int INF=1e16;
struct node{
    int max;
    int add;
    int lazy;
}tree[N*16];
int n,m,a[N];
void pushup(int p){
    tree[p].max=max(tree[ls].max,tree[rs].max);
    return;
}
void pushdown(int p){
    if(tree[p].lazy!=-INF){
	tree[ls].lazy=tree[rs].lazy=tree[p].lazy;
	tree[ls].max=tree[rs].max=tree[p].lazy;
	tree[ls].add=tree[rs].add=0;
	tree[p].lazy=-INF;
    }
    if(tree[p].add){
	tree[ls].add+=tree[p].add;
	tree[rs].add+=tree[p].add;
	tree[ls].max+=tree[p].add;
	tree[rs].max+=tree[p].add;
	tree[p].add=0;
    }
}
void build(int p,int l,int r){
    tree[p].lazy=-INF;
    if(l==r){tree[p].max=a[l];return;}
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(p);
}
void upd1(int p,int l,int r,int x,int y,int k){
    if(x<=l&&y>=r){
	tree[p].max=k;
	tree[p].lazy=k;
	tree[p].add=0;
	return;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(x<=mid) upd1(ls,l,mid,x,y,k);
    if(y>mid) upd1(rs,mid+1,r,x,y,k);
    pushup(p);
}
void upd2(int p,int l,int r,int x,int y,int k){
    if(x<=l&&y>=r){
	tree[p].max+=k;
	tree[p].add+=k;
	return;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(x<=mid) upd2(ls,l,mid,x,y,k);
    if(y>mid) upd2(rs,mid+1,r,x,y,k);
    pushup(p);
}
int query(int p,int l,int r,int x,int y){
    int res=-INF;
    if(x<=l&&y>=r){
	res=max(res,tree[p].max);
	return res;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(x<=mid) res=max(res,query(ls,l,mid,x,y));
    if(y>mid) res=max(res,query(rs,mid+1,r,x,y));
    return res;
}
signed main(){
    n=read();m=read();
    for(int i=1;i<=n;++i) a[i]=read();
    build(1,1,n);
    for(int i=1;i<=m;++i){
	int op=read();
	if(op==1){
	    int l,r,x;
	    l=read();r=read();x=read();
	    upd1(1,1,n,l,r,x);
	}
	else if(op==2){
	    int l,r,x;
	    l=read();r=read();x=read();
	    upd2(1,1,n,l,r,x);
	}
	else{
	    int l,r;
	    l=read();r=read();
	    printf("%lld\n",query(1,1,n,l,r));
	}
    }
    return 0;
}

---

\(Experience\)

多种操作的懒标记混合时，需要定义一个顺序

pushdown 写在

	if(x<=l&&y>=r){
    ```
    ```
    ```
	return;
    }

前面要开 \(8\) 倍空间