Segment fhqTreap

· · 题解

这么好的区间操作模板题，当然缺不了一篇fhqTreap题解了！（逃

今天刚刚查出了自己文艺平衡树的错，于是兴致勃勃跑来双(san)倍经验

然后被丧心病狂的#2,#9,#10摁在地上摩擦

最后不得已吸了一口氧气，以950ms+卡过了这题

于是就开心地来发题解了！！！

不知道fhqTreap？出门左转普通平衡树，右转文艺平衡树，包您满意

这里仅简单说明思想：把第1至l-1和r+1至n的元素分裂出去，中间剩下的就是要操作的区间，在根上打标记就行了

更详细的注释见代码

由于我强行封装，代码极其冗长，因此将各个部分分开讲

首先是对fhqTreap类的定义 

template<typename T>
class fhq_treap
{
    private:
        struct Node;//所有元素存入结点
        Node* _root;//根指针
        Node* merge(Node*,Node*);//合并两棵树
        void ranksplit(Node*,const int&,Node*&,Node*&);//按排名将树分裂
        void dfs(Node*);//输出全树中序遍历，方便调试
    public:
        struct iterator;//假装写个迭代器，其实几乎全废
        void addchange(int,int,const T&);//区间加法
        void mulchange(int,int,const T&);//区间乘法
        T query(int,int);//区间求和
        iterator insert(const T&);//插入元素
        void vis();//dfs对外的接口
};

然后是结点... 

template<typename T>
struct fhq_treap<T>::Node
{
    T val;
    int pri;//随机优先级
    Node* lc;//左儿子
    Node* rc;//右儿子 //fhqTreap没有旋转，父指针可以不维护
    int s;//以该结点为根的子树大小
    T addflag;//加法标记
    T mulflag;//乘法标记
    T sum;//以该结点为根的子树中元素之和
    Node(const T& v=T(),//构造函数，由于要存的信息多，因此比较长
        Node *l=NULL,
        Node *r=NULL,
        int ss=1,
        const T& aff=T(0),
        const T& mff=T(1)):
        val(v),
        sum(v),
        pri(rand()),
        lc(l),
        rc(r),
        s(ss),
        addflag(aff),
        mulflag(mff) {}
    static int size(Node* ptr)//这样就可以免去对空指针的判断
    {
        return ptr!=NULL?ptr->s:0;
    }
    void maintain()//维护子树大小、子树元素和
    {
        s=size(lc)+size(rc)+1;
        sum=val;
        if(lc!=NULL)sum=(sum+lc->sum*lc->mulflag+lc->s*lc->addflag)%P;
        if(rc!=NULL)sum=(sum+rc->sum*rc->mulflag+rc->s*rc->addflag)%P;
    }
    void pushdown()//区间操作的核心:标记下传
    {
        sum=(sum*mulflag+s*addflag)%P;//先修改当前结点的元素、元素和
        val=(val*mulflag+addflag)%P;//由于开long long，一些不必要的取模可以省略
        if(lc!=NULL)
        {
            lc->addflag=(lc->addflag*mulflag+addflag)%P;//注意顺序！加法标记先乘再加
            lc->mulflag=lc->mulflag*mulflag%P;
        }
        if(rc!=NULL)
        {
            rc->addflag=(rc->addflag*mulflag+addflag)%P;
            rc->mulflag=rc->mulflag*mulflag%P;
        }
        addflag=T(0);//当前结点加法标记归零，乘法标记归一
        mulflag=T(1);
    }
};

伪迭代器（没什么用处，不解释了） 

template<typename T>
struct fhq_treap<T>::iterator
{
    private:
        Node* _real_node;
    public:
        T operator*()const{return _real_node->val;}
        iterator(Node* ptr=NULL):_real_node(ptr) {}
        iterator(const fhq_treap<T>::iterator& iter):_real_node(iter._real_node) {}
};

遍历的代码，很好写的辣！

template<typename T>
void fhq_treap<T>::dfs(Node* ptr)
{
    if(!ptr)return;
    ptr->pushdown();
    dfs(ptr->lc);
    cout<<ptr->val<<' ';//这代码写了本来是希望适配各种类型的，因此用流输出
    dfs(ptr->rc);
}
template<typename T>
void fhq_treap<T>::vis()
{
    dfs(_root);
    cout<<endl;
}

接下来是fhqTreap特有的操作

template<typename T>
typename
fhq_treap<T>::Node* fhq_treap<T>::merge(Node* x,Node* y)//合并以x、y为根的树，返回新树的根
{
    if(!x)return y;
    if(!y)return x;
    if(x->pri<y->pri)//如果x优先级高于y，就把y合并到x的右儿子里
    {
        x->pushdown();//无论干什么，都别忘了传标记、改大小、求和
        x->rc=merge(x->rc,y);
        x->maintain();
        return x;
    }
    else//否则，把x合并到y的左儿子里
    {
        y->pushdown();
        y->lc=merge(x,y->lc);
        y->maintain();
        return y;
    }
};

template<typename T>
void fhq_treap<T>::ranksplit(Node* nroot,const int& k,Node*& ltree,Node*& rtree)
{//按排名分裂以nroot为根的子树 //本来是按权值分裂，但这里用不上
    if(!nroot)
    {
        ltree=NULL;
        rtree=NULL;
        return;
    }
    nroot->pushdown();
    int s=Node::size(nroot->lc);
    if(s>=k)//当前元素排名大于k，则分裂其左子树
    {
        rtree=nroot;
        ranksplit(nroot->lc,k,ltree,nroot->lc);
    }
    else//否则分裂右子树
    {
        ltree=nroot;
        ranksplit(nroot->rc,k-s-1,nroot->rc,rtree);
    }
    nroot->maintain();
}

有了merge和split，下面的操作就变得无脑了QAQ

插入：

template<typename T>
typename
fhq_treap<T>::iterator fhq_treap<T>::insert(const T& v)
{
    Node* ptr=new Node(v);
    if(!_root)
    {
        _root=ptr;
        return ptr;
    }
/*  Node *ptr1,*ptr2;//本来要按权值分裂合并，但这里直接按插入顺序操作就行了
    split(_root,v,ptr1,ptr2);
    _root=merge(merge(ptr1,ptr),ptr2);
    vis();*/
    _root=merge(_root,ptr);//千万，千万，千万要记得把根重置，否则十RE！！！
    return ptr;
}

删除没用，跳过

区间加法： 

template<typename T>
void fhq_treap<T>::addchange(int l,int r,const T& v)
{
    Node *ptr,*ptr1,*ptr2;
    ranksplit(_root,l-1,ptr1,ptr);//将1至l-1的部分分裂出去
    ranksplit(ptr,r-l+1,ptr,ptr2);//将r+1以后的部分分裂出去
    ptr->addflag=(ptr->addflag+v)%P;//在中间部分的根上打标记 //本来想打一个模P同余类，时间紧张没来得及
    _root=merge(ptr1,merge(ptr,ptr2));//同样要重置根
}

区间乘法： 

template<typename T>
void fhq_treap<T>::mulchange(int l,int r,const T& v)//类似的思路，不再赘述
{
    Node *ptr,*ptr1,*ptr2;
    ranksplit(_root,l-1,ptr1,ptr);
    ranksplit(ptr,r-l+1,ptr,ptr2);
    ptr->addflag=(ptr->addflag*v)%P;//但要注意这里需把加法标记一并修改
    ptr->mulflag=(ptr->mulflag*v)%P;
    _root=merge(ptr1,merge(ptr,ptr2));
}

区间求和： 

template<typename T>
T fhq_treap<T>::query(int l,int r)//更简单了有木有！！！
{
    Node *ptr,*ptr1,*ptr2;
    ranksplit(_root,l-1,ptr1,ptr);
    ranksplit(ptr,r-l+1,ptr,ptr2);
    ptr->pushdown();//直接下传标记以取得当前区间的和
    T ans=ptr->sum;
    _root=merge(ptr1,merge(ptr,ptr2));
    return ans;
}

快读快写，不开则T 

template<typename T>
void read(T& x)
{
    x=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+(c^48),c=getchar();
}
template<typename T>
void write(const T& x)
{
    if(x>=10)write(x/10);
    putchar((x%10)^48);
}

主程序


int n,m;
int op,l,r,v;
fhq_treap<long long> my_tree;//注意开long long，否则乘法溢出，全WA

int main()//有了封装好的板子，主程序就简单多了！！！
{
//  ios::sync_with_stdio(0);
//  cin>>n>>m>>P;//cin再怎么加速也会T
    srand(20381314);//这句其实不加也没关系，我开始就忘记了
    read(n);
    read(m);
    read(P);
    for(int i=0;i<n;++i)read(op),my_tree.insert(op);
    for(int i=0;i<m;++i)
    {
        read(op);
        read(l);
        read(r);
        if(op!=3)read(v);

        switch (op)
        {
            case(1):
                my_tree.mulchange(l,r,v);
                break;
            case(2):
                my_tree.addchange(l,r,v);
                break;
            case(3):
                write(my_tree.query(l,r));
                putchar('\n');
                break;
            default:
                break;
        }
    }
}
手打五十行注释不容易，管理员求过