C++14(g++5.4) 解法, 执行用时: 668ms, 内存消耗: 16304K, 提交时间: 2019-12-21 22:39:24

#include<bits/stdc++.h>
using namespace std;
#define ll long long 

const int N=2e5+100;

ll t[N<<2],lzy[N<<2];
ll a[N];
#define ls x<<1
#define rs x<<1|1


void pushdown(int x,int l,int r)
{
	if(lzy[x])
	{
		int mid=l+r>>1;
		lzy[ls]=lzy[x];
		lzy[rs]=lzy[x]+mid-l+1;
		t[ls]=(lzy[x]+lzy[x]+mid-l)*(mid-l+1)/2;
		t[rs]=(lzy[rs]+lzy[rs]+r-mid-1)*(r-mid)/2;
		lzy[x]=0;
	}
}
void build(int l,int r,int x)
{
	if(l==r) 
	{
		t[x]=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
	t[x]=t[ls]+t[rs];
}
void update(int l,int r,int L,int R,int x,int k)
{
	if(L<=l&&r<=R)
	{
		t[x]=1ll*(k+l-L+k+l-L+r-l)*(r-l+1)/2;
		lzy[x]=k+l-L;
		return ;
	}
	pushdown(x,l,r);
	int mid=l+r>>1;
	if(L<=mid) update(l,mid,L,R,ls,k);
	if(R>mid) update(mid+1,r,L,R,rs,k);
	t[x]=t[ls]+t[rs]; 
}
ll query(int l,int r,int L,int R,int x)
{
	if(L<=l&&r<=R) return t[x];
	pushdown(x,l,r);
	int mid=l+r>>1;
	ll ans=0;
	if(L<=mid) ans+=query(l,mid,L,R,ls);
	if(R>mid) ans+=query(mid+1,r,L,R,rs);
	return ans; 
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
	build(1,n,1);
	while(m--)
	{
		int op,x,y,z;
		scanf("%d%d%d",&op,&x,&y);
		if(op==1)
		{
			scanf("%d",&z);
			update(1,n,x,y,1,z);
		}
		else cout<<query(1,n,x,y,1)<<endl;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 399ms, 内存消耗: 18912K, 提交时间: 2020-02-25 13:28:59

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c))
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x;
}
struct node
{
	int l,r;
	long long v;
	bool operator <(const node &tmp)const
	{
		return l<tmp.l;
	}
};
set<node>s;
typedef set<node>::iterator It;
It split(int pos)
{
	It it=s.lower_bound({pos,0,0});
	if(it!=s.end()&&it->l==pos) return it;
	--it;
	if(pos>it->r)return s.end();
	int l=it->l,r=it->r,v=it->v;
	s.erase(it);
	s.insert({l,pos-1,v});
	return s.insert({pos,r,v+pos-l}).first;
}
void _assign(int l,int r,int v)
{
	It R=split(r+1),L=split(l);
	s.erase(L,R);
	s.insert({l,r,v});
}
long long query(int l,int r)
{
	It R=split(r+1),L=split(l);
	long long ans=0;
	for(It it=L;it!=R;++it)
	{
		long long len=it->r-it->l+1;
		ans+=it->v*len+len*(len-1)/2;
	 } 
	 return ans;
}
int main()
{
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	s.insert({i,i,read()});
	while(m--)
	{
		int op,l,r,k;
		scanf("%d %d %d",&op,&l,&r);
		if(op==1)
		{
			scanf("%d",&k);
			_assign(l,r,k);
		}
		else
		printf("%lld\n",query(l,r));
	}
}