链接：https://ac.nowcoder.com/acm/contest/26896/1010
来源：牛客网

题目描述

Keven 特别喜欢线段树，他给你一个长度为 n 的序列，对序列进行m次操作。

操作有两种：

1 l r k：表示将下标在 [l , r] 区间内的数字替换成 [k,k+1,…,k+r−l]

2 l r ：表示查询区间 [l , r] 的区间和

输入描述: 

		
		

			第一行两个整数 n、m，表示序列的长度和操作次数（1<=n,m<=2e5） 
		


		

			第二行 n 个整数，表示序列的初始值 a1,a2,…an（1<=ai<=2e5） 
		


		

			接下来 m 行，每行三或四个数字，若第一个数字是 1，则表示操作 1，反之则表示操作 2。
		


		

			(1<=l<=r<=n，1<=k<=2e5)

输出描述: 

		
		

			对于每个操作2，输出一行一个整数表示区间和。

题型：

线段树--区间修改与区间查询

思路：

对于线段树的区间修改，最关键的一点就是要找出lazy需要维护的量，即每一次区间修改中除了线段树自身的固有信息（如:左边界l，右边界r，初始值tree[p]等）之外，其他要用到的量
所以第一步要做的就是分析区间和的组成
设当线段树的节点编号为p时，其对应的左右边界分别为l和r，操作1中输入的三个数为x,y,k，那么可以求出区间和为(2*(k-x)+r+l)*(r-l+1)/2；（这是等差数列的求和，即(首项+尾项)*(项数)/2，其中首项=k+(l-x)，尾项=k+(r-x)），项数=r-l+1
由此可得，lazy需要维护的值就是(k-x)，因为l和r是区间固有信息，无需维护
至于剩下的建树+区间查询，就是板子（其实区间修改也是板子，只是lazy的值改了一下而已）

代码： 

#include<bits/stdc++.h>
#define int long long int
#define INF 0x3f3f3f3f
using namespace std;
const int N=2e5+200;
int tree[N*4],a[N],lazy[N*4];
//lazy记录k-l
void build(int p,int l,int r){
	lazy[p]=INF;
	if(l==r){
		tree[p]=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p]=tree[p*2]+tree[p*2+1];
}

void pushdown(int p,int l,int r){
	int mid=(l+r)/2;
	lazy[p*2]=lazy[p];
	lazy[p*2+1]=lazy[p];
	tree[p*2]=(2*(lazy[p])+l+mid)*(mid-l+1)/2;
	tree[p*2+1]=(2*(lazy[p])+mid+1+r)*(r-(mid+1)+1)/2;
	lazy[p]=INF;
}

void change(int p,int l,int r,int x,int y,int num,int num2){
	if(x<=l && r<=y){
		tree[p]=(2*(num-num2)+l+r)*(r-l+1)/2; //区间和计算
		lazy[p]=num-num2;
		return;
	}
	if(lazy[p]!=INF) pushdown(p,l,r); //这里的if语句不能删掉，因为lazy[p]==0时执行该函数会对子节点的值有影响（见pushdown函数）
	int mid=(l+r)/2;
	if(x<=mid) change(p*2,l,mid,x,y,num,num2);
	if(y>=mid+1) change(p*2+1,mid+1,r,x,y,num,num2);
	tree[p]=tree[p*2]+tree[p*2+1];
}

int calc(int p,int l,int r,int x,int y){
	if(x<=l && r<=y){
		return tree[p];
	}
	if(lazy[p]!=INF) pushdown(p,l,r); //这里的if语句不能删掉，因为lazy[p]==0时执行该函数会对子节点的值有影响（见pushdown函数）
	int mid=(l+r)/2;
	int ans=0;
	if(x<=mid) ans+=calc(p*2,l,mid,x,y);
	if(y>=mid+1) ans+=calc(p*2+1,mid+1,r,x,y);
	return ans;
}

signed main(){
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	build(1,1,n);
	while(m--){
		int op,x,y,num;
		scanf("%lld",&op);
		if(op==1){
			scanf("%lld%lld%lld",&x,&y,&num);
			change(1,1,n,x,y,num,x); //区间修改
		}
		if(op==2){
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",calc(1,1,n,x,y)); //输出答案
		}
	}
	return 0;
}