题解 P3372 【【模板】线段树 1】

· · 题解

线段树好难啊，只好拿平衡树写了~

首先有个“引理”：

所有线段树和平衡树能做的，无旋Treap都能做。

引理欢迎举例打脸，反正也不是我提出来的。

无旋Treap是通过Merge和Split操作来维护的一种强力高效平衡树，码量极小，常数吊打Splay（但是用来写LCT会被Splay吊打，反正我也不会LCT）。

无旋Treap维护区间操作时特别的显然：

对于区间操作，可以直接Split出对应区间，然后在根节点打标记并Pushdown。

对于区间询问，直接Split出对应区间，输出根节点上存的求和数据。

操作或询问结束后，重新Merge回原树。

可以证明，如果节点的随机种子足够随机，树的结构足够随机，那么树高是Log级别的，单次操作的复杂度也是Log级别的。

一定注意下传标记和上传数据（不知道要不要写的地方干脆就多写几个也不会出事）！放刚写的代码：

#include <bits/stdc++.h>
using namespace std ;
inline long long Readin() {
    register long long K = 0 , F = 1 ; register char C = getchar() ;
    while( C < '0' or C > '9' ) F = C == '-' ? -1 : 1 , C = getchar() ;
    while( C >= '0' and C <= '9' ) K = ( K << 3 ) + ( K << 1 ) + C - '0' , C = getchar() ;
    return F * K ;
}
const int MaxN = 800000 + 5 ;
int N , M ;
struct Treap {
    int Root , L[MaxN] , R[MaxN] , Size[MaxN] , Pos[MaxN] ;
    long long Sum[MaxN] , Tag[MaxN] , Val[MaxN] ;
    #define Ls L[Nod]
    #define Rs R[Nod]
    inline void Pushdown( int Nod ) {
        register long long T = Tag[Nod] ;
        if( not T ) return ;
        Tag[Nod] = 0 ;
        Sum[Ls] += T * Size[Ls] ;
        Sum[Rs] += T * Size[Rs] ; 
        Tag[Ls] += T ;
        Tag[Rs] += T ;
        Val[Ls] += T ;
        Val[Rs] += T ;
    }
    inline void Pushup( int Nod ) {
        Size[Nod] = Size[Ls] + Size[Rs] + 1 ;
        Sum[Nod] = Sum[Ls] + Sum[Rs] + Val[Nod] ;
    }
    int Merge( int A , int B ) {
        if( A == 0 or B == 0 ) return Pushup( A | B ) , A | B ;
        Pushdown( A ) ;
        Pushdown( B ) ;
        register int Rt ;
        if( Pos[A] > Pos[B] ) R[A] = Merge( R[A] , B ) , Rt = A ;
        else L[B] = Merge( A , L[B] ) , Rt = B ;
        return Pushup( Rt ) , Rt ;
    }
    void Split( int Nod , int S , int &A , int &B ) {
        if( not Nod ) {
            A = B = 0 ;
            return ;
        }
        Pushdown( Nod ) ;
        if( Size[Ls] >= S ) B = Nod , Split( Ls , S , A , Ls ) ;
        else A = Nod , Split( Rs , S - Size[Ls] - 1 , Rs , B ) ;
        Pushup( Nod ) ;
    }
    void S( int Nod ) {
        Pushdown( Nod ) ;
        if( Ls ) S( Ls ) ;
        printf( "%d %d %d %lld\n" , Nod , Ls , Rs , Val[Nod] ) ;
        if( Rs ) S( Rs ) ;
        Pushup( Nod ) ;
    }
} T ;
int main() {
    N = Readin() ;
    M = Readin() ;
    T.Root = 0 ;
    for(register int i = 0 ; ++i <= N ; ) {
        T.Size[i] = 1 ;
        T.Tag[i] = T.L[i] = T.R[i] = 0 ;
        T.Val[i] = Readin() ;
        T.Pos[i] = rand() << 15 | rand() ;
        T.Root = T.Merge( T.Root , i ) ;
    }
    for(register int i = 0 ; ++i <= M ; T.S( T.Root ) ) {
        if( Readin() == 1 ) {
            register int L = Readin() , R = Readin() , A , B , C ;
            register long long Add = Readin() ;
            T.Split( T.Root , L - 1 , A , B ) ;
            T.Split( B , R - L + 1 , B , C ) ;
            T.Sum[B] += Add * ( R - L + 1 ) ;
            T.Val[B] += Add ;
            T.Tag[B] += Add ;
            T.Pushdown( B ) ;
            T.Root = T.Merge( T.Merge( A , B ) , C ) ; 
        }
        else {
            register int L = Readin() , R = Readin() , A , B , C ;
            T.Split( T.Root , L - 1 , A , B ) ;
            T.Split( B , R - L + 1 , B , C ) ;
            printf( "%lld\n" , T.Sum[B] ) ;
            T.Root = T.Merge( T.Merge( A , B ) , C ) ; 
        }
    }
    return 0 ;
}

那么问题来了！废了这么大劲，这样的“（假）线段树”有什么好处呢？

考虑这样一个加强版问题：

维护一个序列，所有元素初值为0，需要支持区间加、区间求和。序列长度N=10^{14}，操作次数M=3\times10^{5}。甚至毒瘤出题人还可以加上时空限制2s/64MB和强制在线！

这时动态开点线段树也挂啦，权值线段树也挂啦（因为线段树若强制在线，则时空复杂度一定和N有关）。但是！这种无旋Treap的时空复杂度只与M有关，且空间复杂度是线性的！极其优秀。

结尾立Flag：无旋Treap绝对是古往今来处理区间问题最优美的数据结构！