42.86求条

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n,a[MAXN],m;
long long b[MAXN*4],ta[MAXN*10];
void build(int p,int l,int r)
{
	ta[p]=-1;
	if(l==r) 
	{
		b[p]=a[l];
		return ;
	}
	build(p*2,l,(r-l)/2+l);
	build(p*2+1,(r-l)/2+l+1,r);
	b[p]=(b[p*2]+b[p*2+1]);
}
void work(int p,int l,int mid,int r)
{
//	cout<<mid<<"==\n";
	if(ta[p]!=-1)
	{
		ta[p*2]=ta[p];
		ta[p*2+1]=ta[p]+mid+1-l;
		
		b[p*2]=(ta[p]+ta[p]+mid-l)*(mid-l+1)/2;
		b[p*2+1]=(ta[p]+(mid+1-l)+ta[p]+(r-l))*(r-mid)/2;
		
		ta[p]=-1;
	}
}
void u(int p,int l,int r,int x,int y,int k)
{
	if(l>=x&&r<=y)
	{
		b[p]=((k+l-x)+(k+l-x+r-l))*(r-l+1)/2;
		ta[p]=k+l-x;
		//cout<<(k+l-x)<<" "<<(k+l-x+r-l)<<" "<<(r-l+1)<<" "<<b[p]<<" "<<ta[p]<<" "<<p<<" "<<l<<" "<<r<<"+\n";
		return ;
	}
	if(l!=r) work(p,l,(r-l)/2+l,r);
	if((r-l)/2+l>=x) u(p*2,l,(r-l)/2+l,x,y,k);
	if((r-l)/2+l+1<=y) u(p*2+1,(r-l)/2+l+1,r,x,y,k);
	b[p]=b[p*2]+b[p*2+1];
	//cout<<p<<" "<<l<<" "<<r<<" "<<b[p]<<"+\n";
}
long long sum(int p,int l,int r,int x,int y)
{
	//cout<<p<<" "<<l<<" "<<r<<" "<<b[p]<<" "<<b[p*2]<<" "<<b[p*2+1]<<" "<<ta[p]<<"-\n";
	if(l>=x&&r<=y) return b[p];
	long long cnt=0;
	if(l!=r) work(p,l,(r-l)/2+l,r);
	if((r-l)/2+l>=x) cnt+=sum(p*2,l,(r-l)/2+l,x,y);
	if((r-l)/2+l+1<=y) cnt+=sum(p*2+1,(r-l)/2+l+1,r,x,y);
	return cnt;
}
int main()
{
	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 op,x,y,k;
		cin>>op>>x>>y;
		if(op==1)
		{
			cin>>k;
			u(1,1,n,x,y,k);
		}
		else cout<<sum(1,1,n,x,y)<<"\n";
//		for(int i=1;i<=n;i++) cout<<b[i]<<" ";
//		cout<<"-\n";
	}
	return 0;
}