题解:
线段树,不过这里线段树区间维护要换一种方法。
我们发现这个等差数列的等差为1。对于修改一段区间如果我们知道首项值,那么我们便可以在的时间复杂度计算出这段区间的大小。
又可以知道,对于线段树每一个结点,代表一段区间,那么我们我们用lazy数组保存这一段区间的首项,那么我们便可以在O(1)的时间复杂度内算出这一段区间的值。
代码:
#pragma GCC optimize(3 , "Ofast" , "inline") #include<bits/stdc++.h> //#define ll long long using namespace std; #define endl '\n' #define int long long const int maxn=1e6+10; const int mod=1e9+7; int tree[maxn],a[maxn]; int lazy[maxn]; void push_up(int node){ tree[node]=tree[node*2+1]+tree[node*2]; } void build(int node,int l,int r){ if(l==r){ tree[node]=a[l]; return ; } int mid=(l+r)/2; build(node*2,l,mid); build(node*2+1,mid+1,r); push_up(node); } int cal(int x,int len){ return (2*x+len-1)*len/2; } void push_down(int node,int start,int ends){ if(lazy[node]){ int mid=(start+ends)/2; lazy[node*2]=lazy[node]; lazy[node*2+1]=lazy[node]+mid-start+1; tree[node*2]=cal(lazy[node*2],mid-start+1); tree[node*2+1]=cal(lazy[node*2+1],ends-mid); lazy[node]=0; } } void update(int node,int start,int ends,int l,int r,int val){ if(start>=l&&ends<=r){ lazy[node]=val+start-l; tree[node]=cal(val+start-l,ends-start+1); //cout<<"debug "<<start<<" "<<ends<<" "<<lazy[node]<<" "<<tree[node]<<endl; return ; } push_down(node,start,ends); int mid=(start+ends)/2; if(l<=mid) update(node*2,start,mid,l,r,val); if(mid<r) update(node*2+1,mid+1,ends,l,r,val); push_up(node); } int query(int node,int start,int ends,int l,int r){ if(start>=l&&ends<=r){ return tree[node]; } push_down(node,start,ends); int mid=(start+ends)/2; int res=0; if(l<=mid) res+=query(node*2,start,mid,l,r); if(mid<r) res+=query(node*2+1,mid+1,ends,l,r); return res; } signed 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); //cout<<query(1,1,n,1,5)<<endl;; for(int i=0;i<m;i++){ int opt; cin>>opt; if(opt==1){ int x,y,k; cin>>x>>y>>k; update(1,1,n,x,y,k); } else{ int x,y; cin>>x>>y; cout<<query(1,1,n,x,y)<<endl;; } //cout<<query(1,1,n,1,5)<<endl;; } }