线段树区间仿射区间和模板，看注释就能懂。

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

typedef long long LL;
#define lc(p) (p << 1)
#define rc(p) ((p << 1) | 1)
const int N = 3e5 + 10;

struct node {
	int l, r;
	LL s, a, sum;
	LL tags, taga;
} tr[N << 2];

LL a[N];

void pushup(int p) {
	tr[p].sum = tr[lc(p)].sum + tr[rc(p)].sum;
}

LL get_(LL l, LL r) {
	return (l + r) * (r - l + 1) / 2;
}

void pushdown(int p) {
	if (tr[p].tags != 0) {
		LL s = tr[p].tags;
		
		tr[lc(p)].s += s;
		tr[lc(p)].sum += (tr[lc(p)].r - tr[lc(p)].l + 1) * s;
		tr[lc(p)].tags += s;
		
		tr[rc(p)].s += s;
		tr[rc(p)].sum += (tr[rc(p)].r - tr[rc(p)].l + 1) * s;
		tr[rc(p)].tags += s;
		
		tr[p].tags = 0;
	}
	if (tr[p].taga != 0) {
		LL a = tr[p].taga;
		
		tr[lc(p)].a += a;
		tr[lc(p)].sum += get_(tr[lc(p)].l, tr[lc(p)].r) * a;
		tr[lc(p)].taga += a;
		
		tr[rc(p)].a += a;
		tr[rc(p)].sum += get_(tr[rc(p)].l, tr[rc(p)].r) * a;
		tr[rc(p)].taga += a;
		
		tr[p].taga = 0;
	}
}

void build(int p, int l, int r) {
	tr[p].l = l; tr[p].r = r;
	tr[p].tags = 0; tr[p].taga = 0;
	tr[p].s = 0;  tr[p].a = 0;
	tr[p].sum = 0;
	if (l == r) {
		return ;
	}
	int mid = (l + r) >> 1;
	build(lc(p), l, mid);
	build(rc(p), mid + 1, r);
	pushup(p);
}

void change(int p, int l, int r, LL Qs, LL Qa) {
	if (r < tr[p].l || tr[p].r < l) {
		return ;
	}
	if (l <= tr[p].l && tr[p].r <= r) {
		if (Qs != 0) {
			tr[p].s += Qs;
			tr[p].sum += (tr[p].r - tr[p].l + 1) * Qs;
			tr[p].tags += Qs;
		}
		if (Qa != 0) {
			tr[p].a += Qa;
			tr[p].sum += get_(tr[p].l, tr[p].r) * Qa;
			tr[p].taga += Qa;
		}
		return ;
	}
	pushdown(p);
	change(lc(p), l, r, Qs, Qa);
	change(rc(p), l, r, Qs, Qa);
	pushup(p);
}

LL query(int p, int l, int r) {
	if (r < tr[p].l || tr[p].r < l) {
		return 0;
	}
	if (l <= tr[p].l && tr[p].r <= r) {
		return tr[p].sum;
	}
	pushdown(p);
	return query(lc(p), l, r) + query(rc(p), l, r);
}

struct que {
	LL s, a;
} q[N];

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n, Q;
	cin >> n >> Q;
	
	build(1, 1, n);
	
	char s[5];
	while (Q --) {
		cin >> s;
		if (s[0] == 'P') {
			LL x; LL s, a;
			cin >> x >> s >> a;
			LL mxd = floor(1.0 * s / a);
			LL L = max(1ll, x - mxd);
			LL R = min(1ll * n, x + mxd);
			
			// 对于 i < x, x - i = d
			// i += s - a * d
			// i += s - a * (x - i)
			// i += (s - a * x) + a * i
			if (L <= x - 1) change(1, L, x - 1, s - a * x, a); 
			// 对于 i >= x, i - x = d
			// i += s - a * d
			// i += s - a * (i - x)
			// i += (s + a * x) - a * i
			if (x <= R) change(1, x, R, s + a * x, -a);
			
			q[x].s = s;
			q[x].a = a;
		}
		else if (s[0] == 'U') {
			LL x;
			cin >> x;
			LL s = q[x].s, a = q[x].a;
			LL mxd = floor(1.0 * s / a);
			LL L = max(1ll, x - mxd);
			LL R = min(1ll * n, x + mxd);
			
			// 对于 i < x, x - i = d
			// i -= s - a * d
			// i -= s - a * (x - i)
			// i -= (s - a * x) + a * i
			if (L <= x - 1) change(1, L, x - 1, -(s - a * x), -a); 
			// 对于 i >= x, i - x = d
			// i -= s - a * d
			// i -= s - a * (i - x)
			// i -= (s + a * x) - a * i
			if (x <= R) change(1, x, R, -(s + a * x), a);
		}
		else {
			int l, r;
			cin >> l >> r;
			LL t = (r - l + 1);
			LL res = query(1, l, r);
			res = floor(1.0 * res / t);
			cout << res << "\n";
		}
	}
	return 0;
}

O个人想看的构式解法：

在差分数组上，原问题转化为区间加，求二阶前缀和的问题。

我们考虑前缀和如何维护，显然，对于一个数 $i$，当询问区间为 $[1,n]$ 时，它会被调用 $[n-i+1]$ 次，所以如果查询全局的前缀和是比较好处理的。

但是，每个点被调用的次数会随询问右端点的变化而变化，如 $1$，在 $[1,n]$ 中会被调用 $n$ 次，在 $[1,2]$ 中只会被调用 $2$ 次，这时，在区间加后的查询中是不怎么好处理的。

真的吗？

我们考虑这么一个情况（$n=5$，查询区间为 $[1,3]$，$1$ 代表此次查询中会被调用一次）：

1
11
111

和我们的权重对比一下：

1
11
111
111
111

差别是不是就在下面两行？

所以我们只需要多维护一个区间和，就能 $O(1)$ 将下面的差别抹掉。

然后就是构式的区间加了，我们来看这么一个数列：

0 1 3 5 7 5 3 1 0 0

其差分数组如下：

0 1 2 2 2 -2 -2 -2 -1 0

我们考虑维护差分数组，将操作转化为若干次后缀操作（为什么非得这么干我也不清楚，反正考场上就这么干了）。

0 0 0 0 0 0 0 0 0 0
change(1,1,n,w,w,z);//w是本次修改的第一个位置，z是增加的值
0 1 1 1 1 1 1 1 1 1
change(1,1,n,w,n,z);
0 1 2 2 2 2 2 2 2 2
change(1,1,n,w,n,z);
0 1 2 2 2 -2 -2 -2 -2 -2
change(1,1,n,w,n,z);
0 1 2 2 2 -2 -2 -2 0 0
change(1,1,n,w,w,-cz);//cz=s%a
0 1 2 2 2 -2 -2 -2 -1 0

所以拆成五次区间操作即可。

代码：

#include<bits/stdc++.h>
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;

int n, m;
long long fw[2000005];          // 权重数组：fw[i] = sum_{j=i}^n (n-j+1) = (n-i+1)(n-i+2)/2
long long tg[2000005];          // 线段树懒标记（区间加常数）
long long si[2000005], ai[2000005]; // 记录每个位置的天线参数 s 和 a，用于删除

// 线段树节点：维护差分数组 B 的区间和，以及加权和
struct node {
    long long sum;      // 区间内 B[i] 的和
    long long ts_sum;   // 区间内 B[i] * (n-i+1) 的和，用于计算答案
    node operator + (const node &ano) const {
        node ans;
        ans.sum = sum + ano.sum;
        ans.ts_sum = ts_sum + ano.ts_sum;
        return ans;
    }
};
node tr[2000005];

void up(int root) {
    tr[root] = tr[ls(root)] + tr[rs(root)];
}

// 下传懒标记：对区间 [l, r] 的 B 数组加常数 tg[root]
void down(int root, int l, int r) {
    if (tg[root]) {
        int mid = (l + r) >> 1;
        // 左子区间 [l, mid]
        tr[ls(root)].sum += tg[root] * (mid - l + 1);
        tr[ls(root)].ts_sum += tg[root] * (fw[l] - fw[mid + 1]); // 加权和增量
        // 右子区间 [mid+1, r]
        tr[rs(root)].sum += tg[root] * (r - mid);
        tr[rs(root)].ts_sum += tg[root] * (fw[mid + 1] - fw[r + 1]);
        // 累加懒标记
        tg[ls(root)] += tg[root];
        tg[rs(root)] += tg[root];
        tg[root] = 0;
    }
}

// 对差分数组 B 在区间 [x, y] 上加常数 k
void change(int root, int l, int r, int x, int y, long long k) {
    if (x <= l && r <= y) {
        tr[root].sum += k * (r - l + 1);
        tr[root].ts_sum += k * (fw[l] - fw[r + 1]);
        tg[root] += k;
        return;
    }
    down(root, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) change(ls(root), l, mid, x, y, k);
    if (y > mid) change(rs(root), mid + 1, r, x, y, k);
    up(root);
}

// 查询差分数组 B 在区间 [x, y] 的 sum 和 ts_sum
node query(int root, int l, int r, int x, int y) {
    if (x > y) return {0, 0};
    if (x <= l && r <= y) {
        return tr[root];
    }
    down(root, l, r);
    int mid = (l + r) >> 1;
    node ans = {0, 0};
    if (x <= mid) ans = ans + query(ls(root), l, mid, x, y);
    if (y > mid) ans = ans + query(rs(root), mid + 1, r, x, y);
    return ans;
}

// 调试用：打印当前原数组 A（通过前缀和差分得到）
void print() {
    for (int i = 1; i <= n; i++) {
        node ans = query(1, 1, n, 1, i);
        cout << ans.sum << " ";  // 此处打印的是 B 的前缀和，即 A[i] 的差分？实际上 sum 是 B 的和，不是 A。
    }
    cout << "\n";
    for (int i = 1; i <= n; i++) {
        node ans = query(1, 1, n, i, i);
        cout << ans.sum << " ";
    }
    cout << "\n";
}

int main() {
    cin >> n >> m;

    // 预处理权重 fw[i] = sum_{j=i}^n (n-j+1)
    for (int i = 1; i <= n; i++) fw[i] = 1;
    for (int i = n; i >= 1; i--) fw[i] += fw[i + 1];
    for (int i = n; i >= 1; i--) fw[i] += fw[i + 1];

    while (m--) {
        char op;
        int x, s, a;
        cin >> op >> x;

        if (op == 'P') {  // 添加天线：在位置 x 放置参数为 s, a 的天线
            cin >> s >> a;
            si[x] = s, ai[x] = a;

            // 情况 1：a >= s，信号只覆盖 x 一个点，A[x] = s，其余为 0
            if (a >= s) {
                // 差分 B 在 x 处 +s，在 x+1 处 -s，用三次区间加实现
                change(1, 1, n, x, n, s);
                change(1, 1, n, x + 1, n, -2 * s);
                change(1, 1, n, x + 2, n, s);
                continue;
            }

            // 情况 2：a < s，信号覆盖 [x - s/a, x + s/a]
            // 左半段斜率为 +a，右半段斜率为 -a
            long long w = max(x - s / a, 1);          // 左端点
            long long z = s - (x - w) * a;            // 左端点处的信号值
            long long cz = s % a;                     // 用于最后调整的余数

            // 构造差分数组 B
            // 在 w 处加 z（左端点信号值）
            change(1, 1, n, w, w, z);
            w++;
            z = a;
            // 从 w 到 x 加常数 a（左半段斜率）
            change(1, 1, n, w, n, z);
            // 在 x+1 处减 2a（斜率从 +a 变为 -a）
            w = x + 1;
            z = -2 * a;
            change(1, 1, n, w, n, z);
            // 在右端点之后加 a 恢复斜率为 0
            w = min(x + s / a + 1, n + 1);
            z = a;
            change(1, 1, n, w, n, z);
            // 处理右端点处的边界值调整
            change(1, 1, n, w, w, -cz);
        }
        else if (op == 'Z') {  // 查询区间 [x, y] 的平均信号强度
            int y;
            cin >> y;
            // 利用前缀查询计算区间和
            node ans1 = query(1, 1, n, 1, y);
            node ans2 = query(1, 1, n, 1, x - 1);
            // 公式推导：区间和 = ans1.ts_sum - (n-y)*ans1.sum - ans2.ts_sum + (n-(x-1))*ans2.sum
            cout << (ans1.ts_sum - (n - y) * ans1.sum - ans2.ts_sum + (n - (x - 1)) * ans2.sum) / (y - x + 1) << "\n";
        }
        else {  // op == 'U'，移除位置 x 的天线
            s = si[x], a = ai[x];
            si[x] = 0, ai[x] = 0;

            if (a >= s) {
                // 与添加相反的操作
                change(1, 1, n, x, n, -s);
                change(1, 1, n, x + 1, n, 2 * s);
                change(1, 1, n, x + 2, n, -s);
                continue;
            }

            // 与添加相反，所有区间加取负
            long long w = max(x - s / a, 1), z = s - (x - w) * a, cz = s % a;
            change(1, 1, n, w, w, -z);
            w++, z = a;
            change(1, 1, n, w, n, -z);
            w = x + 1, z = -2 * a;
            change(1, 1, n, w, n, -z);
            w = min(x + s / a + 1, n + 1), z = a;
            change(1, 1, n, w, n, -z);
            change(1, 1, n, w, w, cz);
        }
    }
    return 0;
}

二次差分+树状数组

前言

场上被创飞了，见过区间加等差序列，没见过要求区间查的，还是太菜了，本题我目前知道两个做法，一种是在线段树上打首项与公差的标记的（题解区有），一种是本题解待会要讲的，比较神秘，我也是从学长那里学来的（学得不是很精髓，可能讲得不太好，如有狗叫之处欢迎指出）。

同时个人认为这题能到上位绿下位蓝的程度，建议蓝一下（小声）。

正文

先来看点做法没什么关联但是是本题弱化版的 P1438 无聊的数列

两个操作分别是对一个区间加上首项为 $K$ 公差为 $D$ 的等差数列，并单点查询位置 $p$ 上的值。

由于区间加的值有等差的性质，我们可以考虑把维护的原序列转换成差分序列，在差分序列上进行单点加首项，区间加公差即可完成一操作。单点查询 $p$ 也就变成了区间查询 $[1,p]$ 的和，因为我们在线段树上维护的是差分数组，故查询区间和也就变成了原数组上的单点查询。

再回到这道题，题目诡异的查询操作竟然是对原序列求区间和，如果我们继续按照 $P1438$ 的做法维护差分序列，那么我们要查询的是区间前缀和的前缀和，接下来我们慢慢分析并尝试解决这个乱七八糟的东西。

设原序列为:

$$a_1,a_2,a_3 \cdots a_n$$

差分一次后：

$$b_1,b_2,b_3 \cdots b_n$$

我们暂且把 $b$ 序列放到线段树上，并按单点加首项，区间加公差来完成修改操作，那么查询区间 $[1,n]$ 即为查询：

$$\sum_{i=1}^{n} \sum_{j=1}^{i}b_j$$

困难在于，式子的后半部分是一个区间信息，前面又带一个 $\sum_{i=1}^{n}$ 导致这个式子没法在正确的时间复杂度下求出，如果能把后半部分转化成单点信息，我们就可以试着考虑每一个单点的贡献，从而转化成一个区间的查询。

说起来太抽象了，我直接说做法，你们进行一些体会。

我们把差分序列再差分一次得到：

$$c_1,c_2,c_3 \cdots c_n$$

这时对于修改操作就变成了两个单点修改，在 $l$ 加首项在 $r+1$ 加整个等差数列的和，查询区间 $[1,n]$ 变成了：

$$\sum_{i=1}^{n} \sum_{j=1}^{i}\sum_{k=1}^{j}c_k$$

考虑把每一个 $c_k$ 的贡献拆开来看，式子变成：

$$\sum_{k=1}^{n}c_k \times \sum_{i=1}^{n}\sum_{i=1}^{n}[k\leq j \leq i\leq n]$$

后半部分可以直接化出式子,变成：

$$\sum_{k=1}^{n}c_k \times\frac{(n-k+1)(n-k+2)}{2}$$

简单说一下后半部分怎么化的（反正我一开始没反应过来）：考虑 $j\in [k,n]$,一共有 $(n-k+1)$ 种取值，$i\in [j,n]$，对于 $j$ 取不同的值，$i$ 的取值数量有 $n-k+1,n-k,n-k-1 \cdots 1$，求和公式算一下这俩就总共 $\frac{(n-k+1)(n-k+2)}{2}$ 种合法状态。

我们把式子拆拆再归归类：

$$\sum_{k=1}^{n} [k^2 -(2 \cdot n+3) \cdot k+(n^2+3 \cdot n+2)] \cdot c_k$$

发现有关 $k$ 的可以拆成 $0$ 次项、$1$ 次项和 $2$ 次项，我们可以用三个树状数组来维护对应的次项。

这样一来我的查询就优化成了正常的 $O(\log n)$ 级别，核心思想就是对每个单点的信息拆开来计算，保证式子只有一个 $\sum_{k=1}^{n}$。

代码：

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define lb(x) ((x)&(-x))
using namespace std;
const int N=3e5+5;
int n,m;
struct {
    int sx,gc;
}ev[N];
struct BIT{
    int t[N];
    void add(int x,int v){
        while(x<=n){
            t[x]+=v;
            x+=lb(x);
        }
    }
    int query(int x){
        int res=0;
        while(x){
            res+=t[x];
            x-=lb(x);
        }
        return res;
    }
}p0,p1,p2;
void add(int x,int v){
    p0.add(x,v),p1.add(x,v*x),p2.add(x,v*x*x);
}
void update(int l,int r,int k,int d){
    //点修首项
    add(l,k),add(l+1,d-k);
    //点修右端点，二次差分后差值为等差数列的和
    add(r+1,-(k+d*(r-l+1))),add(r+2,k+d*(r-l));
}
int query(int x){
    int res=0;
    //0次项计算，后面也可写成(x*x+3*x+2)
    res+=p0.query(x)*(x+1)*(x+2);
    //一次项
    res-=(2*x+3)*p1.query(x);
    //二次项
    res+=p2.query(x);
    return res/2;
}

void xpigeon(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        char opt;
        cin>>opt;
        if(opt=='P'){
            int x,s,a;
            cin>>x>>s>>a;
            ev[x].sx=s;
            ev[x].gc=a;
            int l=max(1ll,x-s/a),r=min(x+s/a,n);
            update(l,x-1,s-a*(x-l),a);
            update(x,r,s,-a);
            
        }else if(opt=='U'){
            int x,s,a;
            cin>>x;
            s=-ev[x].sx,a=-ev[x].gc;
            int l=max(1ll,x-s/a),r=min(x+s/a,n);
            update(l,x-1,s-a*(x-l),a);
            update(x,r,s,-a);
            
        }else{
            int l,r;
            cin>>l>>r;
            cout<<(query(r)-query(l-1))/(r-l+1)<<'\n';
        }
    }
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    xpigeon();
    return 0;
}