2018.08.06 bzoj1500: [NOI2005]维修数列(非旋treap)

时间:2021-11-29 19:30:55

传送门

平衡树好题。

我仍然是用的fhqtreap,感觉速度还行。

维护也比线段树splay什么的写起来简单。

%%%非旋treap大法好。

代码:

#include<bits/stdc++.h>
#define N 500005
#define inf 0x3f3f3f3f
using namespace std;
queue<int>garbage;
typedef pair<int,int> res;
int n,m,rt=0,cnt=0,a[N],son[N][2],siz[N],rd[N],val[N],ls[N],rs[N],ms[N],sum[N],rev[N],cov[N];
inline int read(){
    int ans=0,w=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans*w;
}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline void swap(int&a,int&b){a^=b,b^=a,a^=b;}
inline int newnode(int v){
    int x;
    if(!garbage.empty())x=garbage.front(),garbage.pop();
    else x=++cnt;
    son[x][0]=son[x][1]=rev[x]=0,cov[x]=inf,siz[x]=1,rd[x]=rand(),val[x]=sum[x]=ms[x]=v,ls[x]=rs[x]=max(v,0);
    return x;
}
inline void pushup(int p){
    if(!son[p][0]&&!son[p][1]){siz[p]=1,sum[p]=ms[p]=val[p],ls[p]=rs[p]=max(val[p],0);return;}
    siz[p]=siz[son[p][0]]+siz[son[p][1]]+1;
    sum[p]=sum[son[p][0]]+sum[son[p][1]]+val[p];
    if(son[p][0]&&son[p][1]){
        ms[p]=max(max(ms[son[p][0]],ms[son[p][1]]),rs[son[p][0]]+val[p]+ls[son[p][1]]);
        ls[p]=max(ls[son[p][0]],sum[son[p][0]]+val[p]+ls[son[p][1]]);
        rs[p]=max(rs[son[p][1]],sum[son[p][1]]+val[p]+rs[son[p][0]]);
        return;
    }
    if(son[p][0]){
        ms[p]=max(ms[son[p][0]],rs[son[p][0]]+val[p]);
        ls[p]=max(ls[son[p][0]],sum[son[p][0]]+val[p]);
        rs[p]=max(0,val[p]+rs[son[p][0]]);
        return;
    }
    ms[p]=max(ms[son[p][1]],ls[son[p][1]]+val[p]);
    rs[p]=max(rs[son[p][1]],sum[son[p][1]]+val[p]);
    ls[p]=max(0,val[p]+ls[son[p][1]]);
}
inline void pushrev(int p){swap(son[p][0],son[p][1]),swap(ls[p],rs[p]),rev[p]^=1;}
inline void pushcov(int p,int v){
    sum[p]=v*siz[p],val[p]=cov[p]=v;
    ls[p]=rs[p]=max(sum[p],0);
    ms[p]=max(sum[p],v);
}
inline void pushdown(int p){
    if(rev[p]){
        if(son[p][0])pushrev(son[p][0]);
        if(son[p][1])pushrev(son[p][1]);
        rev[p]=0;
    }
    if(cov[p]!=inf){
        if(son[p][0])pushcov(son[p][0],cov[p]);
        if(son[p][1])pushcov(son[p][1],cov[p]);
        cov[p]=inf;
    }
}
inline int build(int dat[],int len){
    int p,las=0;
    static int stk[N],top;
    for(int i=1;i<=len;++i){
        p=newnode(dat[i]),las=0;
        while(top&&rd[stk[top]]>rd[p])pushup(stk[top]),las=stk[top],stk[top--]=0;
        if(top)son[stk[top]][1]=p;
        son[p][0]=las,stk[++top]=p;
    }
    while(top)pushup(stk[top--]);
    return stk[1];
}
inline int merge(int a,int b){
    if(!a||!b)return a+b;
    pushdown(a),pushdown(b);
    if(rd[a]<rd[b]){son[a][1]=merge(son[a][1],b),pushup(a);return a;}
    son[b][0]=merge(a,son[b][0]),pushup(b);return b;
}
inline res split(int p,int k){
    if(!p)return res{0,0};
    pushdown(p);
    res ans,tmp;
    if(siz[son[p][0]]>=k){
        tmp=split(son[p][0],k);
        ans.first=tmp.first,son[p][0]=tmp.second,pushup(p),ans.second=p;
        return ans;
    }
    tmp=split(son[p][1],k-siz[son[p][0]]-1);
    ans.second=tmp.second,son[p][1]=tmp.first,pushup(p),ans.first=p;
    return ans;
}
inline void garbages(int p){
    if(!p)return;
    garbage.push(p),garbages(son[p][0]),garbages(son[p][1]);
}
inline void ins(){
    int pos=read(),len=read();
    static int dat[N];
    for(int i=1;i<=len;++i)dat[i]=read();
    int rtt=build(dat,len);
    res x=split(rt,pos);
    rt=merge(merge(x.first,rtt),x.second);
}
inline void del(){
    int pos=read(),len=read();
    res x=split(rt,pos-1),y=split(x.second,len);
    rt=merge(x.first,y.second);
    garbages(y.first);
}
inline void modify(){
    int pos=read(),len=read(),v=read();
    res x=split(rt,pos-1),y=split(x.second,len);
    pushcov(y.first,v);
    rt=merge(x.first,merge(y.first,y.second));
}
inline void reverse(){
    int pos=read(),len=read();
    res x=split(rt,pos-1),y=split(x.second,len);
    pushrev(y.first);
    rt=merge(x.first,merge(y.first,y.second));
}
inline void query(){
    int pos=read(),len=read();
    res x=split(rt,pos-1),y=split(x.second,len);
    printf("%d\n",sum[y.first]);
    rt=merge(x.first,merge(y.first,y.second));
}
int main(){
    srand(time(NULL));
    n=read(),m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    rt=build(a,n);
    while(m--){
        char s[20];
        scanf("%s",s);
        if(s[0]=='I')ins();
        else if(s[0]=='D')del();
        else if(s[0]=='M'&&s[2]=='K')modify();
        else if(s[0]=='R')reverse();
        else if(s[0]=='G')query();
        else printf("%d\n",ms[rt]);
    }
    return 0;
}

2018.08.06 bzoj1500: [NOI2005]维修数列(非旋treap)的更多相关文章

  1. BZOJ1500&lbrack;NOI2005&rsqb;维修数列——非旋转treap

    题目描述 请写一个程序,要求维护一个数列,支持以下 6 种操作: 请注意,格式栏 中的下划线‘ _ ’表示实际输入文件中的空格 输入 输入的第1 行包含两个数N 和M(M ≤20 000),N 表示初 ...

  2. bzoj千题计划221:bzoj1500&colon; &lbrack;NOI2005&rsqb;维修数列(fhq treap)

    http://www.lydsy.com/JudgeOnline/problem.php?id=1500 1.覆盖标记用INF表示无覆盖标记,要求可能用0覆盖 2.代表空节点的0号节点和首尾的两个虚拟 ...

  3. &lbrack;BZOJ1500&rsqb;&lbrack;NOI2005&rsqb;维修数列---解题报告

    Portal Gun:[BZOJ1500][NOI2005]维修数列 有一段时间没写博客了,最近在刚数据结构......各种板子背得简直要起飞,题目也是一大堆做不完,这里就挑一道平衡树的题来写写好了 ...

  4. &lbrack;BZOJ1500&rsqb;&lbrack;NOI2005&rsqb;维修数列 解题报告 Splay

    Portal Gun:[BZOJ1500][NOI2005]维修数列 有一段时间没写博客了,最近在刚数据结构......各种板子背得简直要起飞,题目也是一大堆做不完,这里就挑一道平衡树的题来写写好了 ...

  5. &lbrack;bzoj1500&rsqb;&lbrack;NOI2005&rsqb;维修数列&lowbar;非旋转Treap

    维修数列 bzoj-1500 NOI-2005 题目大意:给定n个数,m个操作,支持:在指定位置插入一段数:删除一个数:区间修改:区间翻转.查询:区间和:全局最大子序列. 注释:$1\le n_{ma ...

  6. BZOJ1500&lbrack;NOI2005&rsqb;维修数列

    Description Input 输入的第1 行包含两个数N 和M(M ≤20 000),N 表示初始时数列中数的个数,M表示要进行的操作数目.第2行包含N个数字,描述初始时的数列.以下M行,每行一 ...

  7. splay模板三合一 luogu2042 &lbrack;NOI2005&rsqb;维护数列&sol;bzoj1500 &lbrack;NOI2005&rsqb;维修数列 &vert; poj3580 SuperMemo &vert; luogu3391 【模板】文艺平衡树(Splay)

    先是维修数列 题解看这里,但是我写的跑得很慢 #include <iostream> #include <cstdio> using namespace std; int n, ...

  8. BZOJ1500&colon; &lbrack;NOI2005&rsqb;维修数列&lbrack;splay &ast;&ast;&ast;&rsqb;

    1500: [NOI2005]维修数列 Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 12278  Solved: 3880[Submit][Statu ...

  9. &lbrack;bzoj1500&rsqb;&lbrack;NOI2005&rsqb;维修数列——splay

    题目 题解 这道题可以说是数列问题的大BOSS,也算是这一周来学习splay等数据结构的一个总结. 我们一个一个地看这些操作. 对于操作1,我们首先建一棵子树,直接接上原树即可. 对于操作2,我们找到 ...

随机推荐

  1. 多对多关系&lt&semi;EntityFramework6&period;0&gt&semi;

    无负载建立多对多关联的模型 原文中是Modeling a Many-to-Many Relationship with No Payload,虽然这么翻译也有点不准确,但是可以说明其目的,如下图所示, ...

  2. 北理工c语言单项选择题

    1.在函数中,只要说明了变量,就可为其分配存储单元 error:如auto和register类型的变量在定义它的函数被调用时才被分配存储单元 auto:默认的局部变量存储方式,(这种变量定义时在动态存 ...

  3. 【转载】我也说 IEnumerable&comma;ICollection&comma;IList&comma;List之间的区别

    做C#的同学们,都知道,一类只能有一个继承类,但可以实现多个接口.这句话就告诉我们:IEnumerable,ICollection,IList,List区别了 首先我看看 IEnumerable: / ...

  4. Pyhon中的除法

    Python中分为3种除法:传统除法.精确除法.地板除. 传统除法: 如果是整数除法则执行地板除,如果是浮点数除法则执行精确除法. >>>1/2 0 >>>1.0/ ...

  5. Qt入门(11)——Qt插件

    Qt提供了一个简单地插件接口,可以轻松地生成作为独立组件的定制数据库驱动.图象格式.文本编解码器(text codec).风格(style)和部件.警告:Qt 3.0.5对插件的一些方面做了改变,具体 ...

  6. Defender Game 游戏实践(1) 基本游戏场景实现

    在网上看到 郑州|boy 这个博客,里面有几篇文章,记录了其用cocos2d-x这个游戏引擎编写的一个游戏,十分不错,所以这段时间,依样画葫芦,依次学习一下. 由于博主开发的平台是在win32,而且屏 ...

  7. 关于html,css,js三者的加载顺序问题

    <head lang="en"> <meta charset="utf-8"> <title></title> ...

  8. python 学习源码练习(1)

    #编译方式,python3 文件名 #!/usr/bin/python3#print('hello world') mystring = 'hello world'print (mystring) # ...

  9. Activity class &lbrace;com&period;&period;&period;&sol;com&period;&period;&period;&period;MainActivity&rcub; does not exist&period;

    报错信息如上图所示,解决步骤: 1. 首先是检查这个MainActivity.java是不是真的存在,且包名和路径无误: 2. 如果文件存在,且包名和路径没有问题,那么就打开你项目所在的/androi ...

  10. uoj&num;213&period; 【UNR &num;1】争夺圣杯

    http://uoj.ac/problem/209 单调栈求出每个位置x左边第一个大于它的位置L[x]和右第一个不小于它的位置R[x],于是矩形L[x]<=l<=x<=r<=R ...