[yLOI2018] 扶苏的问题

[yLOI2018] 扶苏的问题

题目描述

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

1. 给定区间 [ l , r ] [l, r] [l,r]，将区间内每个数都修改为 x x x。
2. 给定区间 [ l , r ] [l, r] [l,r]，将区间内每个数都加上 x x x。
3. 给定区间 [ 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 的操作，输出一行一个整数表示答案。

样例

样例输入1

6 6
1 1 4 5 1 4
1 1 2 6
2 3 4 2
3 1 4
3 2 3
1 1 6 -1
3 1 6

样例输出1

7
6
-1

样例输入2

4 4
10 4 -3 -7
1 1 3 0
2 3 4 -4
1 2 4 -9
3 1 4

样例输出2

0

提示

数据规模与约定

• 对于 10 % 10\% 10% 的数据， n = q = 1 n = q = 1 n=q=1。
• 对于 40 % 40\% 40% 的数据， n , q ≤ 1 0 3 n, q \leq 10^3 n,q≤103。
• 对于 50 % 50\% 50% 的数据， 0 ≤ a i , x ≤ 1 0 4 0 \leq a_i, x \leq 10^4 0≤ai​,x≤104。
• 对于 60 % 60\% 60% 的数据， o p ≠ 1 op \neq 1 op=1。
• 对于 90 % 90\% 90% 的数据， n , q ≤ 1 0 5 n, q \leq 10^5 n,q≤105。
• 对于 100 % 100\% 100% 的数据， 1 ≤ n , q ≤ 1 0 6 1 \leq n, q \leq 10^6 1≤n,q≤106， 1 ≤ l , r ≤ n 1 \leq l, r \leq n 1≤l,r≤n， o p ∈ { 1 , 2 , 3 } op \in \{1, 2, 3\} op∈{1,2,3}， ∣ a i ∣ , ∣ x ∣ ≤ 1 0 9 |a_i|, |x| \leq 10^9 ∣ai​∣,∣x∣≤109。

提示

请注意大量数据读入对程序效率造成的影响。

思路

这题就是模板线段树加了个区间修改，其他大家都会吧！对于区间修改和区间求和来说，需要两个数组存值,对其进行lazy标记。

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
struct node{ll l,r,Max,laz_add,laz_cover_need,laz_cover_num;
} tre[4000010];

其他就容易了

AC Code

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
struct node{ll l,r,Max,laz_add,laz_cover_need,laz_cover_num;
} tre[4000010];
ll n,m,z,x,y,c,ans,a[1000010];
void make(ll l,ll r,ll s){//建树tre[s].l=l;tre[s].r=r;if(l==r){tre[s].Max=a[l];return;}ll mid=(l+r)>>1;make(l,mid,s<<1);make(mid+1,r,s<<1|1);tre[s].Max=max(tre[s<<1].Max,tre[s<<1|1].Max);return;
}
void push_d(ll s)//清除懒惰标记
{if(tre[s].laz_cover_need==1){tre[s*2].laz_cover_need=1;tre[s*2].laz_cover_num=tre[s].laz_cover_num;tre[s*2].laz_add=0;tre[s*2].Max=tre[s].laz_cover_num;tre[s*2+1].laz_cover_need=1;tre[s*2+1].laz_cover_num=tre[s].laz_cover_num;tre[s*2+1].laz_add=0;tre[s*2+1].Max=tre[s].laz_cover_num;tre[s].laz_cover_need=0;tre[s].laz_cover_num=0; }if(tre[s].laz_add!=0){tre[s*2].Max+=tre[s].laz_add;tre[s*2].laz_add+=tre[s].laz_add;tre[s*2+1].Max+=tre[s].laz_add;tre[s*2+1].laz_add+=tre[s].laz_add;tre[s].laz_add=0;}return;
}
void change_add(ll l,ll r,ll s,ll cc){//区间加减if(tre[s].l>=l&&tre[s].r<=r){tre[s].Max+=cc;tre[s].laz_add+=cc;return;}push_d(s);if(tre[s*2].r>=l)change_add(l,r,s*2,cc);if(tre[s*2+1].l<=r)change_add(l,r,s*2+1,cc);tre[s].Max=max(tre[s*2].Max,tre[s*2+1].Max);return;
}
void change_cover(ll l,ll r,ll s,ll cc){//区间修改if(tre[s].l>=l&&tre[s].r<=r){tre[s].laz_add=0;tre[s].Max=cc;tre[s].laz_cover_need=1;tre[s].laz_cover_num=cc;return;}push_d(s);if(tre[s*2].r>=l)change_cover(l,r,s*2,cc);if(tre[s*2+1].l<=r)change_cover(l,r,s*2+1,cc);tre[s].Max=max(tre[s*2].Max,tre[s*2+1].Max);return;
}
ll ask(ll l,ll r,ll s){//询问区间最大值if(tre[s].l>=l&&tre[s].r<=r)return tre[s].Max;push_d(s);ll value=(ll)-1e15;if(tre[s*2].r>=l)value=max(value,ask(l,r,s*2));if(tre[s*2+1].l<=r)value=max(value,ask(l,r,s*2+1));return value;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;for(ll i=1;i<=n;i++) cin>>a[i];make(1,n,1);for(ll i=1;i<=m;i++){ll q,l,r,num;cin>>q;if(q==1){cin>>l>>r>>num;change_cover(l,r,1,num);}else if(q==2){cin>>l>>r>>num;change_add(l,r,1,num);}else{cin>>l>>r;cout<<ask(l,r,1)<<"\n";}}return 0;
}