https://www.luogu.com.cn/problem/U516827

自己出的线段树练手题，做到了 $O(q \log n)$。

但是常数巨大，不开o2 10000ms。

部分代码

struct node
{
	int sum1,sum2,sumv,L,R;
	node(int a=0,int b=0,int c=0,int d=0,int e=0):sum1(a),sum2(b),sumv(c),L(d),R(e){};
	node operator +(const node &o)const{return {sum1+o.sum1+o.sumv*(R-L+1),o.sum2+sum2+sumv*(o.R-o.L+1),sumv+o.sumv,L,o.R};}
}tr[N<<2];
void push(int id,int x)
{
	int len=tr[id].R-tr[id].L+1,sx=(len*len+len)/2;
	lazy[id]+=x,tr[id].sumv+=len*x;
	tr[id].sum1+=sx*x,tr[id].sum2+=sx*x;
}
void push2(int id,int x)
{
	int len=tr[id].R-tr[id].L+1,sx=(len*len+len)/2;
	lazy2[id]+=x,tr[id].sumv+=sx*x;
	tr[id].sum1+=xy[len]*x,tr[id].sum2+=xx[len]*x; 
}
void push3(int id,int x)
{
	int len=tr[id].R-tr[id].L+1,sx=(len*len+len)/2;
	lazy3[id]+=x,tr[id].sumv+=sx*x;
	tr[id].sum1+=xx[len]*x,tr[id].sum2+=xy[len]*x; 
}
void pushdown(int id)
{
	if(lazy[id])
	{
		push(id<<1,lazy[id]);
		push(id<<1|1,lazy[id]);
		lazy[id]=0;
	}
	if(lazy2[id])
	{
		push(id<<1|1,(tr[id<<1|1].L-tr[id].L)*lazy2[id]);
		push2(id<<1,lazy2[id]);
		push2(id<<1|1,lazy2[id]);
		lazy2[id]=0;
	}
	if(lazy3[id])
	{
		push(id<<1,(tr[id].R-tr[id<<1].R)*lazy3[id]);
		push3(id<<1,lazy3[id]);
		push3(id<<1|1,lazy3[id]);
		lazy3[id]=0;
	}
}
void build(int id,int l,int r)
{
	if(l==r)
	{
		tr[id]=node(a[l],a[l],a[l],l,r);
		return;
	}
	int mid=l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	tr[id]=tr[id<<1]+tr[id<<1|1];
}
void add(int id,int l,int r,int x,int y,int v)
{
	if(x<=l&&y>=r)
	{
		push(id,v);
		return;
	}
	int mid=l+r>>1;pushdown(id);
	if(x<=mid)add(id<<1,l,mid,x,y,v);
	if(y>mid)add(id<<1|1,mid+1,r,x,y,v);
	tr[id]=tr[id<<1]+tr[id<<1|1];
}
void addl(int id,int l,int r,int x,int y,int v)
{
	if(x>y)return;
	if(x<=l&&y>=r)
	{
		push(id,(l-x)*v),push2(id,v);
		return;
	}
	int mid=l+r>>1;pushdown(id);
	if(x<=mid)addl(id<<1,l,mid,x,y,v);
	if(y>mid)addl(id<<1|1,mid+1,r,x,y,v);
	tr[id]=tr[id<<1]+tr[id<<1|1];
}
void addr(int id,int l,int r,int x,int y,int v)
{
	if(x>y)return;
	if(x<=l&&y>=r)
	{
		push(id,(y-r)*v),push3(id,v);
		return;
	}
	int mid=l+r>>1;pushdown(id);
	if(x<=mid)addr(id<<1,l,mid,x,y,v);
	if(y>mid)addr(id<<1|1,mid+1,r,x,y,v);
	tr[id]=tr[id<<1]+tr[id<<1|1];
}
node ask(int id,int l,int r,int x,int y)
{
	if(x>y)return {0,0,0,0,0};
	if(x<=l&&y>=r)return tr[id];
	int mid=l+r>>1;pushdown(id);
	if(x<=mid&&y>mid)return ask(id<<1,l,mid,x,y)+ask(id<<1|1,mid+1,r,x,y);
	if(x<=mid)return ask(id<<1,l,mid,x,y);
	if(y>mid)return ask(id<<1|1,mid+1,r,x,y);
}		

随便帮忙评下难度。