因为出题人的懒惰，所以勤劳的我特地奉上神秘线段树代码（非常不建议使用，我调代码的时间不是人能想象的）：发现1<=f<=100(如果没这个性质就只能双重递归懒标记，用线段树做难度接近紫)，那么只需维护一个线段树求和，并进行力的传播的模拟，同时修改a[i]和线段树里的值，最后查询线段树叶子节点，并加上a[i]即为答案（再次温馨提示：此做法适合对线段树极其熟练的入使用，不然纯找罪受（其实极其熟练也是找罪受））。

代码附上，仅供参考！

#include<bits/stdc++.h>
#define int long long
#define lc k<<1
#define rc k<<1|1
using namespace std;
int n,p,q;
struct tree{
    int l,r,zhi,lazy;
}tr[400302];
int a[100005];
void build(int k,int l,int r){
    tr[k].l=l;tr[k].r=r;
    if(l==r){
        tr[k].zhi=0;
        return ;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[k].zhi=tr[lc].zhi+tr[rc].zhi;
}
void pushdown(int k){
	if(tr[k].lazy){
		tr[lc].zhi+=tr[k].lazy*(tr[lc].r-tr[lc].l+1);
		tr[lc].lazy+=tr[k].lazy;
		tr[rc].zhi+=tr[k].lazy*(tr[rc].r-tr[rc].l+1);
		tr[rc].lazy+=tr[k].lazy;
		tr[k].lazy=0;
	} 
	return ;
}
int query(int k,int x,int y){
    int l=tr[k].l;int r=tr[k].r;
    if(l>=x&&r<=y){
		return tr[k].zhi;
	}
	pushdown(k);
    int sum=0,mid=(l+r)/2;
    if(x<=mid)sum+=query(lc,x,y);
    if(y>mid)sum+=query(rc,x,y);
    return sum;
}
void xg(int k,int x,int y,int qwe){
	int l=tr[k].l,r=tr[k].r;
	if(l>=x&&r<=y){
		tr[k].zhi+=qwe*(r-l+1);
		tr[k].lazy+=qwe;
		return ;
	}
	pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid)xg(lc,x,y,qwe);
    if(y>mid)xg(rc,x,y,qwe);
    tr[k].zhi=tr[lc].zhi+tr[rc].zhi;
}
struct node{
	int l,r,f;	
}asd[100005];
int ans=0,d;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>q>>d>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}	
	build(1,1,n);
    while(q--){
    	int op,l,r,id,f;
    	cin>>op;
    	if(op==0){
    		cin>>id;
    		int l=asd[id].l,r=asd[id].r,f=asd[id].f;
			xg(1,l,r,-f);
			for(int i=l-1;i>=1;i--){
				if(f-(l-i)*d<=0)break;
				a[i]-=f-(l-i)*d;
			}
			for(int i=r+1;i<=n;i++){
				if(f-(i-r)*d<=0)break;
				a[i]-=f-(i-r)*d;
			}
		} 
		else{
			cin>>l>>r>>f>>id;
			asd[id]={l,r,f};
			xg(1,l,r,f);
			for(int i=l-1;i>=1;i--){
				if(f-(l-i)*d<=0)break;
				a[i]+=f-(l-i)*d;
			}
			for(int i=r+1;i<=n;i++){
				if(f-(i-r)*d<=0)break;
				a[i]+=f-(i-r)*d;
			}
		}	
	}
	for(int i=1;i<=n;i++){
		cout<<query(1,i,i)+a[i]<<" ";
	}
	return 0;
}

物理课（原名求压力easy）题解

出题人题解。

思路

首先注意到 $n$ 的取值范围较大，$n^2$ 是过不了的，本题涉及区间修改，而且查询是在最后进行（即离线查询），不难想到差分。

但是区间要加的是等差数列，怎么办呢？下面给出两种解题方法：

SOLUTION 1:

这个比较难，可以去看第二种。

直接维护两层差分（两层差分可以实现加等差数列的操作，具体的就不写了，想问可以发评论，不想用这个方法就去看第二个），这样可以做到 $O(1)$ 的修改。

这个很难调，建议有一定代码功底的可以尝试。

正解本来是这样的，但是在写 $F$ 的范围时开小了。

by me

CODE

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200005;
ll n,d,m,a[N],c[N],cc[N],sum[N],sum2[N];
struct M {
	ll l,r,f;
} e[N];
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>d;
	cin>>m;
	for(int i=1; i<=m; i++) {
		cin>>a[i];
		c[i]+=a[i];
		c[i+1]-=a[i];
	}
	for(int i=1; i<=m+1; i++) {
		cc[i]+=c[i];
		cc[i+1]-=c[i];
	}
	for(int i=1; i<=n; i++) {
		int s;
		int id;
		cin>>s;
		if(s==0) {
			cin>>id;
			e[id].f = 0;
		} else {
			ll l,r,f;
			cin>>l>>r>>f>>id;
			e[id]= {l,r,f};
		}
	}
	for (int i = 1; i <= n; i++) {
		ll l=e[i].l,r=e[i].r,f=e[i].f;
		if (f == 0)continue;
		if (d == 0) {
			cc[1] += f;
			cc[2] -= f;
			cc[m + 1] -= f;
			cc[m + 2] += f;
			continue;
		}
		{
			ll left=l-f/d,right=l-1;
			if (left <= right) {
				left = max(1ll, left);
				ll len = right - left;
				ll a = f - d * (len + 1);
				cc[left] += a;
				cc[left+1] -= a;
				cc[left + 1] += d;
				cc[right + 1] -= d;
				cc[right+1] -= a + len * d;
				cc[right+2] += a + len * d;
			}
		}
		{
			ll left = l, right = r;
			cc[left] += f;
			cc[left + 1] -= f;
			cc[right + 1] -= f;
			cc[right + 2] += f;
		}
		{
			ll left = r + 1, right = r + f / d;
			if (left <= right) {
				right = min(right, m);
				ll len = right - left + 1;
				ll a = f - d;
				cc[left] += a;
				cc[left + 1] -= a;
				cc[left + 1] -= d;
				cc[right + 1] += d;
				cc[right + 1] += len * d - f;
				cc[right + 2] -= len * d - f;
			}
		}
	}
	for(int i=1; i<=m; i++) {
		sum[i]=sum[i-1]+cc[i];
	}
	for(int i=1; i<=m; i++) {
		sum2[i]=sum2[i-1]+sum[i];
		cout<<sum2[i]<<" ";
	}
	return 0;
}

SOLUTION 2:

可以注意到 $F<=100$，那么两边的等差数列就可以暴力模拟去做，只要 $d$ 不为 $0$的话，做一边的等差序列最多只要 $100$ 次。 我们又可以注意到 $d$ 可以为 $0$！这下纯模拟的话就可能会超时了（假如 $n,m=100000$ 而且 $d=0$、$l==r$ 的话，那么就相当于每次操作都要给整个区间模拟一遍，还要做 $100000$ 次，肯定会超时）。怎么办呢？直接特判就行了，如果 $d=0$ 的话我们就直接用差分将整个序列加上一个数就行了。

肥肠煎蛋，下面展示优秀的模拟代码：

by 吴祖锟 (100001)

CODE

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 5;
int a[N],diff[N],n,d,id,m,s;
struct op {
    int l, r, f;
}op[N];
int vis[N];
signed main(){
    cin>>n>>d>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>s;
        if(s==1){
            int l, r, f, id;
            cin>>l>>r>>f>>id;
            op[id] = {l, r, f};
            vis[id] = 1;
        }
        else {
            cin>>id;
            vis[id] = 0;
        }
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (vis[i]) {
            //auto [l, r, f] = op[i];
            int l = op[i].l;
            int r = op[i].r;
            int f = op[i].f;
            diff[l]+=f;
            diff[r+1]-=f;
            if(d==0){
            	ans += f;
            	continue;
			}
            for(int j=max(0ll,l-(f/d));j<=l-1;j++){
                if((f-d*(l-j))>0){
                    a[j]+=(f-d*(l-j));
                }
            }
            for(int j=r+1;j<=min(m,r+(f/d));j++){
                if(f-d*(j-r)>0){
                    a[j]+=f-d*(j-r);
                }
                else break;
            }
        }
    }
    for(int i=1;i<=m;i++){
    	diff[i]+=diff[i-1];
    	
	}
    for(int i=1;i<=m;i++){
    	cout<<a[i]+diff[i] + ans<<" ";
	}
    return 0;
}

两种方法都写完了。

本来还有一个线段树的方法，考虑到有点大炮打蚊子，就不在这里写了。其实是因为懒。

题目推荐

有一道加强版可以做一下，同样出题人也是我。需要用到线段树等算法，可以逝逝试试。

没了

编写题解不易，给我的luogu点个关注谢谢。