线段树40分求助
查看原帖
线段树40分求助
285617
黑影洞人楼主2022/10/3 21:02
#include<cstdio>
#include<algorithm>
#define N 814514
#define lc p<<1
#define rc p<<1|1
#define int __int128
using namespace std;
int n,m;
inline int read(){
	int ans=0,sym=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')sym=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){ans=ans*10+ch-'0';ch=getchar();}
	return ans*sym;
}
inline void write(int x,bool mode){
    x<0?x=-x,putchar('-'):0;static short Stack[50],top(0);
    do Stack[++top]=x%10,x/=10; while(x);
    while(top) putchar(Stack[top--]|48);
    mode?putchar('\n'):putchar(' ');
}
struct Segement_tree{
	int lm,rm,val,sum,l,r;
	Segement_tree(){lm=rm=val=sum=l=r=0;}
	Segement_tree operator+(const Segement_tree &b)const{
		Segement_tree res,a=*this;	
		res.sum=a.sum*b.sum;
		res.lm=max(a.lm,a.sum*b.lm);
		res.rm=max(b.rm,a.rm*b.sum);
		res.val=max(a.rm*b.lm,max(a.val,b.val));
		return res;
	}
}s[N],ept;
void pushup(int p){
	s[p].sum=s[lc].sum*s[rc].sum;
	s[p].lm=max(s[lc].lm,s[lc].sum*s[rc].lm);
	s[p].rm=max(s[rc].rm,s[lc].rm*s[rc].sum);
	s[p].val=max(s[lc].rm*s[rc].lm,max(s[lc].val,s[rc].val));
}
void build(int p,int l,int r){
	s[p].l=l,s[p].r=r;
	if(l==r){
		s[p].lm=s[p].rm=s[p].val=s[p].sum=read();
		return;
	}
	build(lc,l,(l+r)/2);
	build(rc,(l+r)/2+1,r);
	pushup(p);
}
void change(int p,int x,int a){
	if(s[p].l>x||s[p].r<x)return;
	if(s[p].l==x&&s[p].r==x){
		s[p].lm=s[p].rm=s[p].val=s[p].sum=a;
		return;
	}
	change(lc,x,a);change(rc,x,a);
	pushup(p);
}
Segement_tree query(int p,int l,int r){
	if(s[p].l>r||s[p].r<l)return ept;
	if(s[p].l>=l&&s[p].r<=r)return s[p];
	return query(lc,l,r)+query(rc,l,r);
}
signed main(){
	//freopen("T1ex2.in","r",stdin);
	ept.lm=1;
	ept.rm=1;
	ept.sum=1;
	ept.val=1;
	n=read(),m=read();
	build(1,1,n);
	while(m--){
		int op=read(),l=read(),r=read();
		if(op==2){
			if(l>r)swap(l,r);
			int now=query(1,l,r).val;
			if(now<=1ll<<30)write(now,1);
			else puts("Too large");
		}
		if(op==1)change(1,l,r);
	}
	return 0;
}

2022/10/3 21:02
加载中...