萌新刚学线段树,全WA求帮助QAQ
查看原帖
萌新刚学线段树,全WA求帮助QAQ
68960
M_and_P_楼主2020/12/27 11:59

哪位dalao可以帮助看一下代码,感激不尽!!

#include<cstdio>
#include<algorithm>
using namespace std;
const int ADD=1,QUE=2,N=100005<<2;
int lx,ly,k;//对[lx,ly]操作 
int _sum,_mn,_mx;
int n,m,op;
struct Intervel_Tree{ 
	int sum[N],mx[N],mn[N],add[N]; 
	void maintain(int o,int L,int R)
	{
	int lc=o*2,rc=o*2+1;
	if (R>L)
	{ 
	sum[o]=sum[lc]+sum[rc];
	mx[o]=max(mx[lc],mx[rc]);
	mn[o]=min(mn[lc],mn[rc]);
	} 
	if (add[o]){
		sum[o]+=(R-L+1)*add[o];
		mn[o]+=add[o];
		mx[o]+=add[o];
		}
	} 
	void pushdown(int o,int L,int R)
	{
		int lc=o*2,rc=o*2+1,mid=L+(R-L)/2;
		if (add[o])
		{
			if (lx<=mid)add[lc]=add[o];
			if (ly>=mid+1)add[rc]=add[o];
			add[o]=0;
		}
	}
	void update(int o,int L,int R)
	{
		int lc=o*2,rc=o*2+1;
		if (lx<=L&&R<=ly)
			add[o]+=k;
		else
		{
			pushdown(o,L,R);//标记向下传递 
			int mid=L+(R-L)/2;
			if (lx<=mid)update(lc,L,mid);else maintain(lc,L,mid);
			if (ly>=mid+1)update(rc,mid+1,R);else maintain(rc,mid+1,R);
		}
		maintain(o,L,R);
	}	
	void quary(int o,int L,int R,int plus)
	{
		printf("%d %d %d %d;%d %d %d\n",o,L,R,plus,_sum,_mx,_mn);
		int lc=o*2,rc=o*2+1;
		if (lx<=L&&R<=ly)//搜到了一个边界节点 
		{
			_sum+=sum[o]+plus;
			_mn=min(_mn,plus+mn[o]);
			_mx=max(_mx,plus+mx[o]);
		}
		else
		{
			int mid=L+(R-L)/2;
			if (lx<=mid)quary(lc,L,mid,plus+add[o]);
			if (ly>=mid+1)quary(rc,mid+1,R,plus+add[o]);
		}
	}	
};
Intervel_Tree tree;

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		op=ADD;
		lx=ly=i;
		scanf("%d",&k);
		tree.update(1,1,n);
	}
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&op,&lx,&ly);
		if (op==ADD)
		{
			scanf("%d",&k);
			tree.update(1,1,n);
		}
		if (op==QUE)
		{
			_sum=0,_mn=0,_mx=0;
			tree.quary(1,1,n,0);
			printf("%d\n",_sum);
		}
	}
	return 0;
}
2020/12/27 11:59
加载中...