luogu1253扶苏的问题题解-创新互联

扶苏的问题题目题目描述

给定一个长度为 n n n 的序列 a a a，要求支持如下三个操作：

在娄烦等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供成都网站设计、成都网站制作网站设计制作按需网站开发,公司网站建设,企业网站建设,品牌网站建设,网络营销推广,外贸网站建设,娄烦网站建设费用合理。

给定区间 [ l , r ] [l, r] [l,r]，将区间内每个数都修改为 x x x。
给定区间 [ l , r ] [l, r] [l,r]，将区间内每个数都加上 x x x。
给定区间 [ l , r ] [l, r] [l,r]，求区间内的大值。

输入格式

第一行是两个整数，依次表示序列的长度 n n n 和操作的个数 q q q。
第二行有 n n n 个整数，第 i i i 个整数表示序列中的第 i i i 个数 a i a_i ai。
接下来 q q q 行，每行表示一个操作。每行首先有一个整数 o p op op，表示操作的类型。

若 o p = 1 op = 1 op=1，则接下来有三个整数 l , r , x l, r, x l,r,x，表示将区间 [ l , r ] [l, r] [l,r] 内的每个数都修改为 x x x。
若 o p = 2 op = 2 op=2，则接下来有三个整数 l , r , x l, r, x l,r,x，表示将区间 [ l , r ] [l, r] [l,r] 内的每个数都加上 x x x。
若 o p = 3 op = 3 op=3，则接下来有两个整数 l , r l, r l,r，表示查询区间 [ l , r ] [l, r] [l,r] 内的大值。

输出格式

对于每个 o p = 3 op = 3 op=3 的操作，输出一行一个整数表示答案。

题解解法一线段树

方法：用两个懒标记，lazy1存的是相加懒标记，lazy2存的是修改懒标记,tree存的是大值。
但是问题来了：又相加又覆盖怎么解决？

修改

当我们需要修改时，我们不需要管lazy1相加懒标记的值，因此，我们需要将lazy1相加懒标记清零，lazy2修改懒标记相加。
代码：

void intervalcover(int l,int r,int rt,int x,int y,LL data){if(x<=l&&r<=y)return lazy2[rt]=tree[rt]=data,lazy1[rt]=0,void();
    push_down(rt);
    if(x<=mid)intervalcover(lson,x,y,data);
    if(mid

相加当我们需要相加时，我们需要先将lazy2修改懒标记下放，这样才能相加。
inline void change_cover(int rt,LL data){lazy1[rt]=0,tree[rt]=data,lazy2[rt]=data;}
inline void push_down_cover(int rt){if(lazy2[rt]!=-INF){change_cover(ls(rt),lazy2[rt]);change_cover(rs(rt),lazy2[rt]);
        lazy2[rt]=-INF;
    }
}
void intervaland(int l,int r,int rt,int x,int y,LL data){if(x<=l&&r<=y){push_down_cover(rt);
        return tree[rt]+=data,lazy1[rt]+=data,void();
    }
    push_down(rt);
    if(x<=mid)intervaland(lson,x,y,data);
    if(mid
至于普通的下放懒标记操作，就是先下放lazy2修改懒标记，再下放lazy1相加懒标记。
inline void change_cover(int rt,LL data){lazy1[rt]=0,tree[rt]=data,lazy2[rt]=data;}
inline void push_down_cover(int rt){if(lazy2[rt]!=-INF){change_cover(ls(rt),lazy2[rt]);change_cover(rs(rt),lazy2[rt]);
        lazy2[rt]=-INF;
    }
}
inline void change_and(int rt,LL data){tree[rt]+=data,lazy1[rt]+=data;}
inline void push_down_and(int rt){if(lazy1[rt]){change_and(ls(rt),lazy1[rt]);change_and(rs(rt),lazy1[rt]); 
        lazy1[rt]=0;
    }
}
inline void push_down(int rt){push_down_cover(rt);push_down_and(rt);}
合并相加，覆盖操作这时候聪明的你一定会发现，区间和函数和区间修改函数的不同点仅仅是if(x<=l&&r<=y)的处理不同，这个时候，我们就可以合并成一个函数。
void intervalchange(int l,int r,int rt,int x,int y,LL data,int op){if(x<=l&&r<=y){if(op==2){push_down_cover(rt);
            return tree[rt]+=data,lazy1[rt]+=data,void();
        }else return lazy2[rt]=tree[rt]=data,lazy1[rt]=0,void();
    }
    push_down(rt);
    if(x<=mid)intervalchange(lson,x,y,data,op);
    if(mid
求值&建树没什么好说的，注意一下push_up()函数
inline void push_up(const int &r){tree[rt]=max(tree[ls(rt)],tree[rs(rt)]);}
最终的代码注意：一定要开long long，不开long long见祖宗！
#include#include#include#include#include
using std::max;
typedef long long LL;
typedef unsigned long long ULL;
namespace FastIo{typedef __uint128_t ULLL;
    static char buf[100000],*p1=buf,*p2=buf,fw[100000],*pw=fw;
    #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
    inline void pc(const char &ch){if(pw-fw==100000)fwrite(fw,1,100000,stdout),pw=fw;
		*pw++=ch;
	}
    #define fsh fwrite(fw,1,pw-fw,stdout),pw=fw
	struct FastMod{FastMod(ULL b):b(b),m(ULL((ULLL(1)<<64)/b)){}
        ULL reduce(ULL a){ULL q=(ULL)((ULLL(m)*a)>>64);
            ULL r=a-q*b;
            return r>=b?r-b:r;
        }
        ULL b,m;
    }HPOP(10);
    struct QIO{char ch;
    	int st[40];
		bool pd;
		templateinline void read(T &x){x=0,ch=gc,pd=false;
    		while(!isdigit(ch)){pd=ch=='-'?true:false;ch=gc;}
    		while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
    		if(pd)x=-x;
		}
		inline void write(LL a){	if(a<0)a=-a,pc('-');
			do{st[++st[0]]=HPOP.reduce(a);a/=10;}while(a);
			while(st[0])pc(st[st[0]--]^48);
			pc('\n');
		}
	}qrw;
}
using namespace FastIo;
const LL INF=1e18;//有些题解把INF设为1145141919810
#define NUMBER1 1000000
#define P(A) A=-~A
#define fione_i(begin,end) for(register int i=begin;i<=end;P(i))
#define ls(rt) rt<<1
#define rs(rt) rt<<1|1
#define mid (l+r>>1)
#define lson l,mid,ls(rt)
#define rson mid+1,r,rs(rt)
LL a[NUMBER1+5];
struct Segment{LL tree[(NUMBER1<<3)+5],lazy1[(NUMBER1<<3)+5],lazy2[(NUMBER1<<3)+5];
	inline void change_cover(int rt,LL data){lazy1[rt]=0,tree[rt]=data,lazy2[rt]=data;}
	inline void push_down_cover(int rt){if(lazy2[rt]!=-INF){	change_cover(ls(rt),lazy2[rt]);change_cover(rs(rt),lazy2[rt]);
			lazy2[rt]=-INF;
		}
	}
	inline void change_and(int rt,LL data){tree[rt]+=data,lazy1[rt]+=data;}
	inline void push_down_and(int rt){if(lazy1[rt]){	change_and(ls(rt),lazy1[rt]);change_and(rs(rt),lazy1[rt]); 
			lazy1[rt]=0;
		}
	}
	inline void push_down(int rt){push_down_cover(rt);push_down_and(rt);} 
	inline void push_up(const int &rt){tree[rt]=max(tree[ls(rt)],tree[rs(rt)]);}
	void build(int l,int r,int rt){lazy2[rt]=-INF;
		if(l==r)return tree[rt]=a[l],void();
		build(lson);build(rson);
		push_up(rt);
	}
	LL intervalmax(int l,int r,int rt,int x,int y){if(x<=l&&r<=y)return tree[rt];
		push_down(rt);
		LL res(-INF);//不要把res初始化为0！
		if(x<=mid)res=max(intervalmax(lson,x,y),res);
		if(midif(x<=l&&r<=y){	if(op==2){		push_down_cover(rt);
				return tree[rt]+=data,lazy1[rt]+=data,void();
			}else return lazy2[rt]=tree[rt]=data,lazy1[rt]=0,void();
		}
		push_down(rt);
		if(x<=mid)intervalchange(lson,x,y,data,op);
		if(midint m,k,x,y,op,n;
	qrw.read(n);
	qrw.read(m);
	fione_i(1,n)qrw.read(a[i]);
	seg.build(1,n,1);
	while(m--){qrw.read(op);
		qrw.read(x);
		qrw.read(y);
		if(op==3)qrw.write(seg.intervalmax(1,n,1,x,y));
		else{	qrw.read(k);
			seg.intervalchange(1,n,1,x,y,k,op);
		}
	}
	fsh;
    exit(0);
    return 0;
}
解法二ODT——珂朵莉树珂朵莉树不是数据结构！！！
我没用这个方法做，可以把ODT卡掉的。
如果对这种方法有兴趣的同学，可以看这道题（洛谷）（CF）。
                
     你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
                

                网站栏目：luogu1253扶苏的问题题解-创新互联                

                文章链接：http://pwwzsj.com/article/dhccsd.html


        
            其他资讯
            
                
                        浪潮ERPGS6.0安装教程-创新互联
                    

                        Windows开机改IP计划任务-创新互联
                    

                        solr语法如何在spring中使用-创新互联
                    

                        网站优化做起来，有流量了，如何留住搜索用户？
                    

                        python和ruby有哪些区别-创新互联