P3372 题解

· · 题解

这篇题解说了什么？

这篇题解包括了三种解决 P3372 【模板】线段树 1 的方法：

首先声明：这篇题解所用的 有些 算法 并不是 解决这道题的正确算法。如果你想要看正确的 线段树 ，大可不必看这片题解。

蒟蒻的第一篇题解。

解法一： 线段树

这道题的正确解法就是线段树。

但是，我并不打算写线段树的具体构建方式，因为其他的题解讲的比我好得多。如果您打开题解就是为了学习线段树， 那也可以拿我的代码看看，毕竟注释写的还是蛮多的

这里贴出代码：

#include<iostream>
using namespace std;
const int N=100010;
typedef long long ll;
ll tree[N*4];
ll lazy[N*4];
int a[N];
#define lson ((root<<1))
#define rson ((root<<1)+1)
#define mid (l+r>>1)
void build(int root,int l,int r){// O(n) 建树
    if(l==r){
        tree[root]=a[l];//如果递归到了最底层，直接返回。
        return;
    }
    build(lson,l,mid);//分别递归左右子树。
    build(rson,mid+1,r);
    tree[root]=tree[lson]+tree[rson];//重新计算这个节点所覆盖的元素的和。
}
void fun(int root,int l,int r,int v){//推标记
    tree[root]+=(r-l+1)*v;
    lazy[root]+=v;
}
void pushdown(int root,int l,int r){//放标记
    fun(lson,l,mid,lazy[root]);
    fun(rson,mid+1,r,lazy[root]);
    lazy[root]=0;
}
void update(int root,int l,int r,int lr,int rr,int v){//更新
    if(r<lr||rr<l){//如果现在这个节点所代表的线段完全不在更新的范围之内，直接返回。
        return ;
    }
    if(lr<=l&&r<=rr){//如果现在这个节点所代表的线段完全在更新的范围之内，直接推标记。
        fun(root,l,r,v);
        return;
    }
    pushdown(root,l,r);//下放标记。
    update(lson,l,mid,lr,rr,v);
    update(rson,mid+1,r,lr,rr,v);
    tree[root]=tree[lson]+tree[rson];//重新计算这个节点所覆盖的元素的和。
}
ll query(int root,int l,int r,int lr,int rr){//差不多和update函数一样。
    if(r<lr||rr<l){//如果现在这个节点所代表的线段完全不在查询的范围之内，直接返回。
        return 0;
    }
    if(lr<=l&&r<=rr){//如果现在这个节点所代表的线段完全在查询的范围之内，直接sum。
        return tree[root];
    }
    pushdown(root,l,r);//下放标记
    return (ll)query(lson,l,mid,lr,rr)+(ll)query(rson,mid+1,r,lr,rr);
}
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int a,b,c,d,i=1;i<=m;i++){
        cin>>a;
        if(a==1){
            cin>>b>>c>>d;
            update(1,1,n,b,c,d);
        }else{
            cin>>b>>c;
            cout<<(ll)query(1,1,n,b,c)<<endl;
        }
    }
}

解释一下为什么建树是 O(n) 的（直观感受来看，它很容易被认为是 O(n\log n) ）：

根据主定理，T(n)=2T(\dfrac{n}{2})+\theta(1)=O(n)

尽管这个东西可以做到 O(n) ，但是跟这个代码的其他部分比起来，这只是优化了个常数。

解法二：平衡树

平衡树所能维护的不仅仅是一种动态集合，它也可以用来解决某些序列区间问题。但是如果需要实现区间操作，普通的平衡树不能满足要求，最好使用 能够支持分裂和合并 的平衡树。

该解法前置知识：Splay 或是 fhq-Treap 。

这篇题解所采用的平衡树是 fhq-Treap 。它易于实现，常数也不错（虽然跟线段树比起来就差远了

不同于按照值来进行排序的平衡树，这棵平衡树是 按照下标进行排序 的。

下图演示了按照下标进行排序的平衡树和按照值进行排序的平衡树的区别。

这个地方应该挺好理解吧

那么，构建了一棵按照下标排序的平衡树之后我们该怎么办呢？

我们应该考虑去维护 每一个节点的子树的值之和 。

如果我们可以维护，那么我们在查询的时候，只需要将对应的子树分裂出来，然后查询这个被分裂出来的子树的根节点的 子树之和 即可。

实际上这里是很好维护的，我们只需要对于每一个节点维护 sum ，当这棵平衡树分裂或者是合并的时候重新计算受到影响的节点的 sum 即可，也就是 分裂操作或者是合并操作所经过的节点 。

那么按照这个思路，我们也可以对于每一个节点维护一个 lazy ，当我们修改的时候，也是像查询一样，先把我们要修改的这棵子树分裂出来，然后 给树根打上一个 lazy tag 。

现在的问题就是怎么维护这个 lazy tag 。其实像 sum 一样，我们所要做的其实就只是 在分裂操作或是合并操作之前将 lazy tag 下放 。

这样的话，这道题的代码就不难写出来了。

平均时间复杂度： O(m \log n)

之所以这里用的是“平均时间复杂度”，是因为 Treap 的时间复杂度依赖于随机出来数据的好坏。它是个随机化算法。 不过这其实不影响你在竞赛的时候写 Treap ，这是因为 Treap 因为随机出来数据不好而导致 TLE 的可能性微乎其微。

代码：

#include<iostream>
#include<cstdlib>
#define int long long
using namespace std;
const int N=1e6;
struct treap{
    int v,l,r,p,s,lz,su;
}t[N];
#define v(x) t[x].v //代表这个节点的值。
#define ls(x) t[x].l //代表这个节点的左儿子。
#define rs(x) t[x].r //代表这个节点的右儿子。
#define p(x) t[x].p //代表这个节点的优先级
#define s(x) t[x].s //代表这个节点的子树的节点个数
#define lz(x) t[x].lz //lazy tag
#define su(x) t[x].su //sum
void pushup(int x,int v){//上推
    if(x==0)return;
    v(x)+=v;
    su(x)+=s(x)*v;
    lz(x)+=v;
}
void pushdown(int x){//下放
    pushup(ls(x),lz(x));
    pushup(rs(x),lz(x));
    lz(x)=0;
}
int merge(int x,int y){//合并操作
    if(x==0||y==0)
        return x+y;
    if(p(x)<p(y)){
        pushdown(x);//这里是对于 lazy tag 的处理：合并、分裂之前先下放。
        rs(x)=merge(rs(x),y);
        s(x)=s(ls(x))+s(rs(x))+1;
        su(x)=su(ls(x))+su(rs(x))+v(x);//这里是对于 sum 的处理：合并、分裂之后更新 sum
        return x;
    }else{
        pushdown(y);//这里是对于 lazy tag 的处理：合并、分裂之前先下放。
        ls(y)=merge(x,ls(y));
        s(y)=s(ls(y))+s(rs(y))+1;
        su(y)=su(ls(y))+su(rs(y))+v(y);
        return y;
    }
}
void split(int x,int& a,int& b,int siz){
    if(x==0){
        a=b=0;
        return;
    }
    pushdown(x);//这里是对于 lazy tag 的处理：合并、分裂之前先下放。
    if(s(ls(x))<siz){
        a=x;
        split(rs(x),rs(x),b,siz-s(ls(x))-1);
    }else{
        b=x;
        split(ls(x),a,ls(x),siz);
    }
    s(x)=s(ls(x))+s(rs(x))+1;
    su(x)=su(ls(x))+su(rs(x))+v(x);//这里是对于 sum 的处理：合并、分裂之后更新 sum
}
int cnt=0;
int create(int x){
    su(++cnt)=x;
    v(cnt)=x;
    s(cnt)=1;
    p(cnt)=rand()+rand();
    return cnt;
}
int root;
int n,m;
signed main(){
    cin>>n>>m;
    for(int x,i=1;i<=n;i++){
        cin>>x;
        root=merge(root,create(x));//读入一个数，并直接将它合并到平衡树的最后一个位置去。
    }
    int a,b,c;
    for(int ty,l,r,x,i=1;i<=m;i++){
        cin>>ty;
        if(ty==1){
            cin>>l>>r>>x;
            split(root,a,b,l-1);
            split(b,b,c,r-l+1);//先将所修改的子树分裂出来
            pushup(b,x);//打上个lazy tag
            root=merge(merge(a,b),c);//合并回去
        }else{
            cin>>l>>r;
            split(root,a,b,l-1);
            split(b,b,c,r-l+1);//先将所修改的子树分裂出来
            cout<<su(b)<<endl;//查一下sum
            root=merge(merge(a,b),c);//合并回去
        }
    }
}

解法三：CDQ 分治

这才是这篇题解的独特之处！

前置知识：CDQ分治

其实不会 CDQ 分治也可以看这篇题解，毕竟 CDQ 分治只是一种思想，而不是一种具体的算法。

先将这个题差分化

如果我们来把一个修改拆开，变成两个修改，分别修改开头和末尾（也就是把一个原本是 [l,r]+x 的修改变成 [l,n]+x ;[r+1,n]-x 的两个修改），这个东西就变成了一个差分。

我们不妨也把原本的数组也这样处理：对于每一个 i \in [1,n] ，加入两个修改：[i,n]+a_i;[i+1,n]-a_i 。（其中 a_i 表示原本的数组的第 i 个元素）

既然修改都做到这样了，我们也可以对查询这么做：对于一个查询 [l,r] ，我们把它拆成两个查询 [1,r];[1,l-1] 。最后我们只需要将第一个查询的答案减去第二个查询的答案即可得到原本的查询的答案。

探究一个查询的答案的构成。

现在我们来看一个查询 [1,x] 的答案是怎么构成的：

首先，如果有一个修改[y,n]+z，它的位置在 x 之前 （也就是 y<=x）,它出现的时间也在 x 之前，那么这个修改一定可以对查询 [l,x] 造成贡献。那么这个贡献是什么呢？我们会发现，这个修改其实相当于把区间 [y,x] 之间的每一个数都造成了贡献 z ,所以这个修改对于查询 [1,x] 的贡献为 (x-y+1)\times z 。

我们现在已经搞明白了如果有一个修改和一个查询，那么这个修改什么条件下会对查询造成贡献以及造成贡献的量。现在我们将这个结论推向多个修改和一个查询。

我们先不妨设 y_i 为第 i 个询问的 y ， z_i 为第 i 个询问的 z 。

如果现在有 s 个查询和一个修改，并且每一个查询都能对这个修改造成贡献，，那么贡献之和理应是

\sum_{i=1}^{s}z_i(x-y_i+1)=\sum_{i=1}^{s}(z_ix-z_iy_i+z_i)=(x+1)\sum_{i=1}^{s}z_i-\sum_{i=1}^{s}z_iy_i

分治统计答案

现在我们已经成功把这个题转化为了差分形式和搞明白了一个查询的答案的构成。但是知道这些有什么用吗？我们怎么用这些信息把答案算出来？

我们假设每一个询问和修改现在都被我们放在一个序列里，它们都有以下属性：

既然它们的属性基本一致，我们就叫它们节点好了。

我们重新改写题意：给出每一个节点的 t,x,y ，算出每一个节点能获得的贡献。

好了，那么，现在又怎么做？

分治？

怎么分治？

我们考虑到，如果现在你正在处理一个区间 [l,r] 中的节点（并且它们的 t 是一个 [l,r] 的排列），我们首先可以把它们分为两类：

很明显，对于同一类节点之间造成的贡献，我们直接递归下去好了，我们需要考虑的只是不同类节点之间造成的贡献，而且，如果有贡献，一定是第一类节点对第二类节点造成贡献。

这个其实很显然：第一类节点的 t 都小于第二类节点的 t ，无论如何也不可能让后来者影响先来者。

于是这就变成了第一类节点单向对第二类节点造成贡献的问题。 那么怎么计算贡献呢？我们首先把两类节点都以 x 为关键词排序，（因为之后 x 小的节点能对 x 大的节点造成贡献）。然后我们可以来用双指针法算贡献。具体流程如下：

请注意：原来的贡献公式中，x ,y ,z 的定义与现在的定义不同，请勿混淆。

  1. 创建两个变量 sum 和 all ，分别表示已经处理的第一类节点的 y 之值 和 已经处理的第一类节点的 x 与 y 的乘积之和。跳转至第 2 步。

  2. 如果第一类节点的第一个节点的 x 比 第二类节点的第一个节点的 x 小，那么我们就先处理第一类节点的第一个节点，跳转至第 3 步；否则我们就先处理第二类节点的第一个节点，转至第 4 步。

  3. 将第一类第一个节点的 y 加入 sum ，将 xy 加入 all 。将这个节点“删掉”，并返回到第二步。（让下一个节点变成第一个节点）

  4. 按照公式 \text{contribution}=(x+1)\sum_{i=1}^{s}y_i-\sum_{i=1}^{s}x_iy_i=(x+1)sum + all 算出贡献，并将其加入到这个节点的总贡献中。将这个节点“删掉”，并返回到第二步。（让下一个节点变成第一个节点）

这里的“删掉”并不是真的删掉，只是为了方便说明原理而已。

我们可以保证，在这个算法运行完毕之后，每一个第二类的节点都已经加上了第一类节点所能造成的贡献。

现在，我已经将这整个算法的流程说明完毕。如果你在上面没有理解明白，可以到下面去看看具体实现。

下面是代码：

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=1e6;
int a[N];
struct query{//节点的结构体。
    int time,x,y;
}p[N],temp[N];
int cnt=0;
void add(int x,int y){//添加一个节点
    p[++cnt].time=cnt;
    p[cnt].x=x;
    p[cnt].y=y;
}
int ans[N];//a[x]用来存储t为x的节点所获得的总贡献。
pair<int,int> qa[N];
int n,m;
bool cmp(query a,query b){//一个按照 x 排序的 cmp 函数。
    if(a.x!=b.x)
        return a.x<b.x;
    return a.time<b.time;
}
void cdq(int l,int r){//现在在处理区间 [l,r]
    if(l==r)
        return;//只有一个元素，直接返回
    int mid=(l+r)>>1,x=l,y=mid+1;
    for(int i=l;i<=r;i++)       //先将区间 [l,r] 分为两类节点
        if(p[i].time<=mid)
            temp[x++]=p[i]; //这个节点属于第一类
        else temp[y++]=p[i];  //这个节点属于第二类
    for(int i=l;i<=r;i++)p[i]=temp[i];  
    cdq(l,mid);         //分治第一类节点之间的贡献
    cdq(mid+1,r);       //分治第二类节点之间的贡献
    sort(p+l,p+mid+1,cmp);      //排序，使得它对于 x 有序。
    sort(p+mid+1,p+r+1,cmp);
    x=l,y=mid+1;int sum=0,all=0;
    while(x<=mid||y<=r)         //双指针算法。其中 x 代表第一类元素现在的下标，y 代表第二类元素现在的下标。
        if(x<=mid&&(y>r||p[x].x<=p[y].x))                   //如果我们要先处理第一类节点
            sum+=p[x].x*p[x].y,all+=p[x].y,x++;             //更新sum和all
        else                                                //否则处理第二类节点
              ans[p[y].time]+=all*(p[y].x+1)-sum,y++;   //计算贡献
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        add(i,a[i]-a[i-1]);
    int qm=0;
    for(int ty,l,r,x,i=1;i<=m;i++){
        cin>>ty;
        if(ty==1){//是一个修改操作
            cin>>l>>r>>x;
            add(l,x);//进行差分
            add(r+1,-x);
        }else{
            cin>>l>>r;
            add(l-1,0);
            qa[++qm].first=cnt;//存下来这个询问对应着哪两个询问，方便最后处理。
            add(r,0);
            qa[qm].second=cnt;
        }
    }
    cdq(1,cnt);
    for(int i=1;i<=qm;i++)
        cout<<ans[qa[i].second]-ans[qa[i].first]<<endl;
}

复杂度分析和优化

那么这个算法我们写完了，它的时间复杂度是什么呢？

很遗憾， O(n \log^2 n) ，比线段树要劣。

我们先看 O(n \log^2 n) 是怎么来的，再看怎么把它再优化。（这个时间复杂度并不是这个算法的最优时间复杂度。)

我们用 T(n) 表示分治完一个长度为 n 的块的总时间复杂度。很明显，我们可以列出以下式子：

T(n)=2T(\dfrac{n}{2})+O(n \log n)

（其中那个 O(n\log n) 是快排的时间复杂度和双指针算法的总时间复杂度。）

然后这个东西可以用主定理推出来 T(n)= O(n\log^2 n)

如果你没有学过主定理，正好可以学学（

复杂度分析我们说完了，那么怎么优化呢？

我们注意到，复杂度的瓶颈其实在快排上，我们只要把快排去掉，我们就可以实现 O(n\log n) 的优异复杂度。

我们怎么不用快排呢？

你会发现，我们实际上所排序的东西，也就是下一层分治的区间，被分成了两部分，他们分别有序。

说人话就是假设你现在在处理区间 [l,r] ，设 mid=\dfrac{l+r}{2},lmid=\dfrac{l+mid}{2}，那么其实 [l,lmid]是有序的，[lmid+1,mid]是有序的。我们无需快排，只需要在 \text{cdq}(l,mid) 之后再用一个类似于归并排序一样的东西就行。

这比较不好描述，不过以下的代码描述了这个过程。

void cdq(int l,int r){
    if(l==r)
        return;
    int mid=(l+r)>>1,x=l,y=mid+1;
    for(int i=l;i<=r;i++)
        if(p[i].time<=mid)
            temp[x++]=p[i];
        else temp[y++]=p[i];
    for(int i=l;i<=r;i++)p[i]=temp[i];
    cdq(l,mid);
    cdq(mid+1,r);
    x=l,y=mid+1;int sum=0,now=0,all=l;
    //双指针算法
    while(x<=mid||y<=r)
        if(x<=mid&&(y>r||p[x].x<=p[y].x))
            sum+=p[x].x*p[x].y,now+=p[x].y,temp[all++]=p[x++];
        else ans[p[y].time]+=now*p[y].x-sum,temp[all++]=p[y++];
    for(int i=l;i<=r;i++)
        p[i]=temp[i];
}

（因为基本上只有这里有修改，所以无需把整个代码搬过来。）

如果你写过归并排序，你会发现这东西其实就是把双指针算法和归并排序的板子揉在了一块，或者说， 归并排序的合并实现就是双指针算法 。

在双指针算法执行完了之后，你会发现 p 数组回到了 x 为第一个关键字排序的状态。

那么，我们这么改了之后，复杂度变成了什么?

T(n)=2T(\dfrac{n}{2})+\theta(n)=\theta(n\log n)

这样，这个算法的时间复杂度就和线段树一样了。

下面是完整代码：

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=1e6;
int a[N];
struct query{
    int time,x,y;
}p[N],temp[N];
int cnt=0;
void add(int x,int y){
    p[++cnt].time=cnt;
    p[cnt].x=x;
    p[cnt].y=y;
}
int ans[N];
pair<int,int> qa[N];
int n,m;
void cdq(int l,int r){
    if(l==r)
        return;
    int mid=(l+r)>>1,x=l,y=mid+1;
    for(int i=l;i<=r;i++)
        if(p[i].time<=mid)
            temp[x++]=p[i];
        else temp[y++]=p[i];
    for(int i=l;i<=r;i++)p[i]=temp[i];
    cdq(l,mid);
    cdq(mid+1,r);
    x=l,y=mid+1;int sum=0,now=0,all=l;
    while(x<=mid||y<=r)
        if(x<=mid&&(y>r||p[x].x<=p[y].x))
            sum+=p[x].x*p[x].y,now+=p[x].y,temp[all++]=p[x++];
        else ans[p[y].time]+=now*p[y].x-sum,temp[all++]=p[y++];
    for(int i=l;i<=r;i++)
        p[i]=temp[i];
}
bool cmp(query a,query b){
    if(a.x!=b.x)
          return a.x<b.x;
    return a.time<b.time;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        add(i,a[i]-a[i-1]);
    int qm=0;
    for(int ty,l,r,x,i=1;i<=m;i++){
        cin>>ty;
        if(ty==1){//update
            cin>>l>>r>>x;
            add(l,x);
            add(r+1,-x);
        }else{
            cin>>l>>r;
            add(l,0);
            qa[++qm].first=cnt;
            add(r+1,0);
            qa[qm].second=cnt;
        }
    }
    sort(p+1,p+1+cnt,cmp);
    cdq(1,cnt);
    for(int i=1;i<=qm;i++)
        cout<<ans[qa[i].second]-ans[qa[i].first]<<endl;
}

完结撒花！（（（

这篇题解难免会有一些错误，如果您发现了一些错误，欢迎在评论区指出，谢谢！

引用：

洛谷用户“这人太菜了”的洛谷日报博客：https://www.luogu.com.cn/blog/GJY-JURUO/master-theorem

Orz Orz %%%