牛客题目数据结构

做过线段树2模板大概可以写出一部分代码，这题主要关键点是怎么维护平方和

借图了

这样处理完maketag的代码就出来了

void maketag(int id,int l,int r,ll v,int opt){
	if(opt==1){
		seg[id].val*=v;
		seg[id].pfval*=(v*v);
		seg[id].mul*=v;
        seg[id].add*=v;
	}else{
		seg[id].pfval+=v*v*(r-l+1)+2*v*seg[id].val;
		seg[id].val+=(r-l+1)*v;
		seg[id].add+=v;
	}
}

感觉这类题只要数学处理出得到懒标记后，式子变化量是什么就可以了

对了还需要看一下变化量有没有用到其他维护量，如果有要把维护量放在后面更新

还有如果有多个标记，要考虑标记之间有没有影响，牛客数据弱，我懒标记没处理好过了

// Problem: 数据结构
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/19684/D
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<algorithm>
#include<vector>
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
const int N=1e5+9;
int a[N];
struct node{
	ll val,pfval,mul,add;
}seg[N<<2];
ll tl(ll x){
	return x<<1;
}
ll tr(ll x){
	return x<<1|1;
}
void pushup(int id){
	seg[id].val=seg[tl(id)].val+seg[tr(id)].val;
	seg[id].pfval=seg[tl(id)].pfval+seg[tr(id)].pfval;
}
void build(int id,int l,int r){
	seg[id].mul=1;
	if(l==r){
		seg[id].val=a[l];
		seg[id].pfval=a[l]*a[l];
	}else{
		int mid=(l+r)>>1;
		build(tl(id),l,mid);
		build(tr(id),mid+1,r);
		pushup(id);
	}
}
bool inrange(int L,int R,int l,int r){
	return L>=l && R<=r;
}
bool outofrange(int L,int R,int l,int r){
	return L>r || l>R;
}
void maketag(int id,int l,int r,ll v,int opt){
	if(opt==1){
		seg[id].val*=v;
		seg[id].pfval*=(v*v);
		seg[id].mul*=v;
        seg[id].add*=v;
	}else{
		seg[id].pfval+=v*v*(r-l+1)+2*v*seg[id].val;
		seg[id].val+=(r-l+1)*v;
		seg[id].add+=v;
	}
}
void pushdown(int id,int l,int r){
	int mid=(l+r)>>1;
	maketag(tl(id),l,mid,seg[id].mul,1);
	maketag(tr(id),mid+1,r,seg[id].mul,1);
	maketag(tl(id),l,mid,seg[id].add,2);
	maketag(tr(id),mid+1,r,seg[id].add,2);
	seg[id].mul=1;
	seg[id].add=0;
}
ll querysum(int id,int L,int R,int l,int r){
	if(inrange(L,R,l,r)){
		return seg[id].val;
	}else if(!outofrange(L,R,l,r)){
		int mid=(L+R)>>1;
		pushdown(id,L,R);
		return querysum(tl(id),L,mid,l,r)+querysum(tr(id),mid+1,R,l,r);
	}else{
		return 0;
	}
}
ll querypfsum(int id,int L,int R,int l,int r){
	if(inrange(L,R,l,r)){
		return seg[id].pfval;
	}else if(!outofrange(L,R,l,r)){
		int mid=(L+R)>>1;
		pushdown(id,L,R);
		return querypfsum(tl(id),L,mid,l,r)+querypfsum(tr(id),mid+1,R,l,r);
	}else{
		return 0;
	}
}
void modifymul(int id,int L,int R,int l,int r,ll v){
	if(inrange(L,R,l,r)){
		maketag(id,L,R,v,1);
	}else if(!outofrange(L,R,l,r)){
		int mid=(L+R)>>1;
		pushdown(id,L,R);
		modifymul(tl(id),L,mid,l,r,v);
		modifymul(tr(id),mid+1,R,l,r,v);
		pushup(id);
	}
}
void modifyadd(int id,int L,int R,int l,int r,ll v){
	if(inrange(L,R,l,r)){
		maketag(id,L,R,v,2);
	}else if(!outofrange(L,R,l,r)){
		int mid=(L+R)>>1;
		pushdown(id,L,R);
		modifyadd(tl(id),L,mid,l,r,v);
		modifyadd(tr(id),mid+1,R,l,r,v);
		pushup(id);
	}
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int opt;
		cin>>opt;
		if(opt==1){
			int l,r;
			cin>>l>>r;
			cout<<querysum(1,1,n,l,r)<<'\n';
		}else if(opt==2){
			int l,r;
			cin>>l>>r;
			cout<<querypfsum(1,1,n,l,r)<<'\n';
		}else if(opt==3){
			int l,r,x;
			cin>>l>>r>>x;
			modifymul(1,1,n,l,r,x);
		}else{
			int l,r,x;
			cin>>l>>r>>x;
			modifyadd(1,1,n,l,r,x);
		}
	}
    return 0;
}