自动搬运

查看原文

来自洛谷，原作者为

	xpigeon 咚咚哒咚咚

搬运于2025-08-24 23:17:57，当前版本为作者最后更新于2025-07-08 19:00:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

二次差分+树状数组

前言

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

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

正文

先来看点做法没什么关联但是是本题弱化版的 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;
}