BZOJ1251序列终结者——非旋转treap-白红宇

BZOJ1251序列终结者——非旋转treap

阅读量：7123 次

发布时间：2019-06-28

本文共 1642 字，大约阅读时间需要 5 分钟。

题目描述

网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……这样我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。这道题目就叫序列终结者吧。【问题描述】给定一个长度为N的序列，每个序列的元素是一个整数（废话）。要支持以下三种操作： 1. 将[L,R]这个区间内的所有数加上V。 2. 将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。 3. 求[L,R]这个区间中的最大值。最开始所有元素都是0。

输入

第一行两个整数N，M。M为操作个数。以下M行，每行最多四个整数，依次为K，L，R，V。K表示是第几种操作，如果不是第1种操作则K后面只有两个数。

输出

对于每个第3种操作，给出正确的回答。

样例输入

4 4

1 1 3 2

1 2 4 -1

2 1 3

3 2 4

样例输出

【数据范围】

N<=50000，M<=100000。

非旋转treap模板题，对于区间翻转和区间修改直接将修改区间断裂出来打上标记，像线段树一样遍历到点时再下传标记就好了。注意有负数。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define ll long longusing namespace std;int x,y,z;int n,m;int k,L,R;ll c;int cnt;int root;int s[50010];ll mx[50010];int r[50010];ll v[50010];int ls[50010];int rs[50010];int size[50010];ll a[50010];int build(int rt){ r[++cnt]=rand(); size[cnt]=1; return cnt;}void add(int rt,int val){ mx[rt]+=val; a[rt]+=val; v[rt]+=val;}void rotate(int rt){ swap(ls[rt],rs[rt]); s[rt]^=1;}void pushup(int rt){ size[rt]=size[ls[rt]]+size[rs[rt]]+1; mx[rt]=v[rt]; if(ls[rt]) { mx[rt]=max(mx[rt],mx[ls[rt]]); } if(rs[rt]) { mx[rt]=max(mx[rt],mx[rs[rt]]); }}void pushdown(int rt){ if(s[rt]) { if(ls[rt]) { rotate(ls[rt]); } if(rs[rt]) { rotate(rs[rt]); } s[rt]=0; } if(a[rt]) { if(ls[rt]) { add(ls[rt],a[rt]); } if(rs[rt]) { add(rs[rt],a[rt]); } a[rt]=0; }}int merge(int x,int y){ if(!x||!y) { return x+y; } pushdown(x); pushdown(y); if(r[x]

转载于:https://www.cnblogs.com/Khada-Jhin/p/9687076.html

你可能感兴趣的文章