违规用户名577241 @ 2024-04-06 18:27:22
#include <iostream>
#include <climits>
#include <cstdio>
using namespace std;
int n, q;
const int maxn = 1E6 + 5;
int a[maxn];
const long long Inf = LLONG_MAX;
struct segment_tree
{
long long value;
long long tag1, tag2;
};
segment_tree tree[maxn * 4];
void pushup(int root)
{
tree[root].value = max(tree[root << 1].value, tree[(root << 1) + 1].value);
}
void build(int root, int l, int r)
{
tree[root].tag1 = Inf;
if (l == r)
{
tree[root].value = a[l];
return;
}
int mid = (l + r) >> 1;
build(root << 1, l, mid);
build((root << 1) + 1, mid + 1, r);
pushup(root);
}
void pushdown(int root)
{
if (tree[root].tag1 == Inf)
{
tree[root << 1].tag2 += tree[root].tag2;
tree[root << 1].value += tree[root].tag2;
tree[(root << 1) + 1].tag2 += tree[root].tag2;
tree[(root << 1) + 1].value += tree[root].tag2;
tree[root].tag2 = 0;
return;
}
else
{
tree[root << 1].tag2 = tree[(root << 1) + 1].tag2 = 0;
tree[root << 1].tag1 = tree[(root << 1) + 1].tag1 = tree[root].tag1;
tree[root << 1].value = tree[(root << 1) + 1].value = tree[root].tag1;
tree[root].tag1 = Inf;
tree[root].tag2 = 0;
return;
}
}
void update(int root, int l, int r, int L, int R, int x, int opt)
{
if (L <= l && r <= R)
{
if (opt == 1)
{
tree[root].tag1 = x;
tree[root].tag2 = 0;
tree[root].value = x;
}
else
{
if (tree[root].tag1 == Inf)
{
tree[root].tag2 += x;
tree[root].value += x;
}
else
{
tree[root].tag1 += x;
tree[root].value += x;
tree[root].tag2 = 0;
}
}
return;
}
int mid = (l + r) >> 1;
pushdown(root);
if (L <= mid) update(root << 1, l, mid, L, R, x, opt);
if (R > mid) update((root << 1) + 1, mid + 1, r, L, R, x, opt);
pushup(root);
}
long long query(int root, int l, int r, int L, int R)
{
if (L <= l && r <= R)
return tree[root].value;
int mid = (l + r) >> 1;
pushdown(root);
long long res = 0;
if (L <= mid) res += query(root << 1, l, mid, L, R);
if (R > mid) res += query((root << 1) + 1, mid + 1, r, L, R);
return res;
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
while (q--)
{
int opt;
scanf("%d", &opt);
if(opt != 3)
{
int l, r;
int x;
scanf("%d%d%d", &l, &r, &x);
update(1, 1, n, l, r, x, opt) ;
}
else
{
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", query(1, 1, n, l, r));
}
}
return 0;
}by Elysian_Realme @ 2024-04-06 18:30:17
a?
by 违规用户名577241 @ 2024-04-06 18:36:45
@Elysian_Realme 没过样例
by 123456jiangyuxuan @ 2024-04-06 19:01:56
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;
struct node{
ll max,add=0,cover=0x7f7f7f7f;
int l,r,len;
}tree[N<<2];
int a[N],q,n,op,x,y;
ll k;
void push_up(int p){
tree[p].max=max(tree[p<<1].max,tree[p<<1|1].max);
}
void build(int p,int l,int r){
tree[p].l=l;
tree[p].r=r;
tree[p].add=0;
tree[p].len=r-l+1;
if(l==r){
tree[p].max=a[l];
return;
}
int mid=l+(r-l>>1);
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
push_up(p);
}
void push_down(int p){
if(tree[p].cover!=0x7f7f7f7f){
tree[p<<1].add=tree[p<<1|1].add=0;
tree[p<<1].cover=tree[p<<1|1].cover=tree[p].cover;
tree[p<<1].max=tree[p<<1|1].max=tree[p].cover;
tree[p].cover=0x7f7f7f7f;
}
if(tree[p].add){
tree[p<<1].add+=tree[p].add;
tree[p<<1|1].add+=tree[p].add;
tree[p<<1].max+=tree[p].add;
tree[p<<1|1].max+=tree[p].add;
tree[p].add=0;
}
}
void update_add(int p,ll v,int l,int r){
if(tree[p].l>r||tree[p].r<l)return;
if(tree[p].l>=l&&tree[p].r<=r){
tree[p].max+=v;
if(tree[p].l<tree[p].r){
if(tree[p].cover==0x7f7f7f7f)tree[p].add+=v;
else tree[p].cover+=v;
}
return;
}
push_down(p);
update_add(p<<1,v,l,r);
update_add(p<<1|1,v,l,r);
push_up(p);
}
void update_cover(int p,ll v,int l,int r){
if(tree[p].l>r||tree[p].r<l)return;
if(tree[p].l>=l&&tree[p].r<=r){
tree[p].max=v;
if(tree[p].l<tree[p].r){
tree[p].add=0;
tree[p].cover=v;
}
return;
}
push_down(p);
update_cover(p<<1,v,l,r);
update_cover(p<<1|1,v,l,r);
push_up(p);
}
ll query(int p,int l,int r){
if(tree[p].l>r||tree[p].r<l)return -1e18;
if(tree[p].l>=l&&tree[p].r<=r)return tree[p].max;
push_down(p);
return max(query(p<<1,l,r),query(p<<1|1,l,r));
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;++i)cin>>a[i];
build(1,1,n);
for(int i=1;i<=q;++i){
cin>>op>>x>>y;
if(op==1){
cin>>k;
update_cover(1,k,x,y);
}
else if(op==2){
cin>>k;
update_add(1,k,x,y);
}
else{
cout<<query(1,x,y)<<"\n";
}
}
return 0;
}```
@[Coder2021](/user/577241)by 123456jiangyuxuan @ 2024-04-06 19:05:14
@Coder2021
by 违规用户名577241 @ 2024-04-09 16:48:34
谢谢