萌新学了\dfrac{1}{0x66ccff}天求调线段树
查看原帖
萌新学了\dfrac{1}{0x66ccff}天求调线段树
1000298
Vsinger_洛天依楼主2023/10/27 15:36

萌新学了10x66ccff\dfrac{1}{0x66ccff}天求调线段树 rt,只有40分

#include<bits/stdc++.h>
using namespace std;
int n,m,a[0x66ccff];
struct node{
	long long l,r;
    long long lazy,dat,lazyy;
}t[0x66ccff];
inline void build(int q,int l,int r){
	t[q].l=l;
	t[q].r=r;
	if(l==r){
		t[q].dat=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(q*2,l,mid);
	build(q*2+1,mid+1,r);
	t[q].dat=max(t[q*2].dat,t[q*2+1].dat);
}
inline void lazy(int q){
    if(!t[q].lazyy){
        t[q*2].lazy+=t[q].lazy;
        t[q*2].dat+=t[q].lazy;
	    t[q*2+1].lazy+=t[q].lazy;
        t[q*2+1].dat+=t[q].lazy;
	    t[q].lazy=0;
    }
    else{
        t[q*2].lazy=t[q].lazy;
        t[q*2].dat=t[q].lazy;
	    t[q*2+1].lazy=t[q].lazy;
        t[q*2+1].dat=t[q].lazy;
        t[q*2].lazyy=1;
        t[q*2+1].lazyy=1;
        t[q].lazyy=0;
	    t[q].lazy=0;
    }
	
}
inline void change1(int q,int l,int r,int v)
{
	if(t[q].l>r||t[q].r<l) return;
	if(t[q].l>=l&&t[q].r<=r){
		t[q].lazy=v;
        t[q].lazyy=1;
		t[q].dat+=v;
		return;
	}
	if(t[q].lazy!=0) 
        lazy(q);
	change1(q*2,l,r,v);
	change1(q*2+1,l,r,v);
	t[q].dat=max(t[q*2].dat,t[q*2+1].dat);
}
inline void change(int q,int l,int r,int v)
{
	if(t[q].l>r || t[q].r<l) return;
	if(t[q].l>=l && t[q].r<=r)
	{
		t[q].lazy+=v;
		t[q].dat+=v;
		return;
	}
	if(t[q].lazy>0) 
        lazy(q);
	change(q*2,l,r,v);
	change(q*2+1,l,r,v);
	t[q].dat=max(t[q*2].dat,t[q*2+1].dat);
}
inline long long ask(int q,int l,int r){
    if(t[q].l>r || t[q].r<l) 
        return 0;
	if(t[q].l>=l && t[q].r<=r) 
        return t[q].dat;
	if(t[q].lazy!=0) 
        lazy(q);
	return max(ask(q*2,l,r),ask(q*2+1,l,r)); 
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		long long qwq,x,y,k;
		cin>>qwq;
        if(qwq==1){
            cin>>x>>y>>k;
            change1(1,x,y,k);
        }
		else if(qwq==2){
			cin>>x>>y>>k;
			change(1,x,y,k);
		}
		else {
			cin>>x>>y;
			cout<<ask(1,x,y)<<endl;
		}
	}
}

怎么板子都打错了,恼了。怎么板子都打错了,恼了。怎么板子都打错了,恼了。 怎么板子都打错了,恼了。怎么板子都打错了,恼了。怎么板子都打错了,恼了。怎么板子都打错了,恼了。

2023/10/27 15:36
加载中...