题解：P12762 [POI 2018 R2] 电信中继站 Transceivers

· · 题解

二次差分+树状数组

前言

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

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

正文

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