序列终结者

给定一个长度为N的序列,每个序列的元素是一个整数。要支持以下五种操作:
 1.查询第K位置上的数。
 2.把第K个位置上的数加上X。
 3.查询[L,R]这个区间的和。
 4.查询[L,R]这个区间的最大值。
 5.将[L,R]这个区间翻转,比如1 2 3 4变成4 3 2 1。

全部评论
int main(){ // freopen(".in","r",stdin); // freopen(".out","w",stdout); n=read();m=read(); for(_R int i=2;i<=n+1;++i)a[i]=read(); maxx[0]=-INF;a[1]=a[n+2]=-INF; root=build(0,1,n+2); int op,l,r,x,val; while(m--){ op=read(); if(op==1)x=read()+1,printf("%d\n",query(x)); if(op==2)x=read()+1,val=read(),revise(x,val); if(op==3)l=read()+1,r=read()+1,printf("%d\n",query(l,r,0)); if(op==4)l=read()+1,r=read()+1,printf("%d\n",query(l,r,1)); if(op==5)l=read()+1,r=read()+1,reverse(l,r); } return 0; }
11 回复 分享
发布于 2019-11-25 14:29
int build(int father,int l,int r){ if(l>r)return 0; int mid=(l+r)>>1,x=++cnt; fa[x]=father;v[x]=maxx[x]=a[mid]; ch[x][0]=build(x,l,mid-1); ch[x][1]=build(x,mid+1,r); pushup(x); return x; }
11 回复 分享
发布于 2019-11-25 14:29
int query(int x){ x=findk(root,x); return v[x]; }
11 回复 分享
发布于 2019-11-25 14:29
int query(int l,int r,bool flag){ l=findk(root,l-1);r=findk(root,r+1); splay(l,0);splay(r,l); if(flag)return maxx[ch[r][0]]; else return sum[ch[r][0]]; }
11 回复 分享
发布于 2019-11-25 14:28
void revise(int x,int val){ x=findk(root,x); splay(x,0); v[x]+=val; pushup(x); }
11 回复 分享
发布于 2019-11-25 14:28
void reverse(int l,int r){ l=findk(root,l-1);r=findk(root,r+1); splay(l,0);splay(r,l); flag[ch[r][0]]^=1; pushup(r);pushup(l); }
11 回复 分享
发布于 2019-11-25 14:28
int findk(int x,int k){ pushdown(x); if(size[ch[x][0]]+1==k)return x; if(ch[x][0]&&size[ch[x][0]]+1>k)return findk(ch[x][0],k); return findk(ch[x][1],k-size[ch[x][0]]-1); }
11 回复 分享
发布于 2019-11-25 14:28
void splay(int x,int f){ while(fa[x]!=f){ int y=fa[x],z=fa[y]; pushdown(z);pushdown(y);pushdown(x); if(z==f){rotate(x);break;} if((y==ch[z][0])^(x==ch[y][0]))rotate(x);else rotate(y); rotate(x); } if(!f)root=x; }
11 回复 分享
发布于 2019-11-25 14:28
void rotate(int x){ int y=fa[x],z=fa[y],son=(x==ch[y][1]); if(y==ch[z][0])ch[z][0]=x;else ch[z][1]=x; fa[y]=x;fa[x]=z;fa[ch[x][son^1]]=y;ch[y][son]=ch[x][son^1];ch[x][son^1]=y; pushup(y);pushup(x); }
11 回复 分享
发布于 2019-11-25 14:28
void pushdown(int x){ if(flag[x]){ if(ch[x][0])flag[ch[x][0]]^=1;if(ch[x][1])flag[ch[x][1]]^=1; swap(ch[x][0],ch[x][1]); flag[x]=0; } }
11 回复 分享
发布于 2019-11-25 14:27
const int N=100005; int n,m,root,cnt; int a[N],fa[N],ch[N][2],size[N],v[N],maxx[N],flag[N],sum[N]; void pushup(int x){ sum[x]=max(sum[ch[x][0]],0)+max(sum[ch[x][1]],0)+max(v[x],0); maxx[x]=max(max(maxx[ch[x][0]],maxx[ch[x][1]]),v[x]); size[x]=size[ch[x][0]]+size[ch[x][1]]+1; }
11 回复 分享
发布于 2019-11-25 14:27
_I int read(){ int x=0;bool f=0;char ch=getchar(); while(ch<'0'||ch>'9')f|=(ch=='-'),ch=getchar(); while('0'<=ch&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); f&&(x=-x); return x; }
11 回复 分享
发布于 2019-11-25 14:27
//char buf[1<<21],*p1=buf,*p2=buf; //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
11 回复 分享
发布于 2019-11-25 14:27
#include<bits> #define _I inline #define _R register #define lowbit(i) ((i)&(-i)) #define memset(x,y) memset(x,y,sizeof(x)) #define mod 1000000007 #define INF 0x3f3f3f3f #define ull unsigned long long #define ll long long using namespace std;</bits>
11 回复 分享
发布于 2019-11-25 14:27
太毒瘤
10 回复 分享
发布于 2019-12-05 19:49
毒瘤
10 回复 分享
发布于 2019-12-05 19:49
简直毒瘤
10 回复 分享
发布于 2019-12-05 19:48
怎么办得呀,谁能帮帮我呀
10 回复 分享
发布于 2019-12-05 19:48
真道题好难啊
10 回复 分享
发布于 2019-12-05 19:48
毒瘤毒瘤
4 回复 分享
发布于 2019-12-09 14:53

相关推荐

06-13 17:33
门头沟学院 Java
顺序不记了,大致顺序是这样的,有的相同知识点写分开了1.基本数据类型2.基本数据类型和包装类型的区别3.==和equals区别4.ArrayList与LinkedList区别5.hashmap底层原理,put操作时会发生什么6.说出几种树型数据结构7.B树和B+树区别8.jvm加载类机制9.线程池核心参数10.创建线程池的几种方式11.callable与runnable区别12.线程池怎么回收线程13.redis三剑客14.布隆过滤器原理,不要背八股,说说真正使用时遇到了问题没有(我说没有,不知道该怎么回答了)15.堆的内存结构16.自己在写项目时有没有遇见过oom,如何处理,不要背八股,根据真实经验,我说不会17.redis死锁怎么办,watchdog机制如何发现是否锁过期18.如何避免redis红锁19.一个表性别与年龄如何加索引20.自己的项目的QPS怎么测的,有没有真正遇到大数量表21.说一说泛型22.springboot自动装配原理23.springmvc与springboot区别24.aop使用过嘛?动态代理与静态代理区别25.spring循环依赖怎么解决26.你说用过es,es如何分片,怎么存的数据,1000万条数据怎么写入库中27.你说用limit,那么在数据量大之后,如何优化28.rabbitmq如何批次发送,批量读取,答了延迟队列和线程池,都不对29.计网知不知道smtp协议,不知道写了对不对,完全听懵了30.springcloud知道嘛?只是了解反问1.做什么的?短信服务,信息量能到千万级2.对我的建议,基础不错,但是不要只背八股,多去实际开发中理解。面试官人不错,虽然没露脸,但是中间会引导我回答问题,不会的也只是说对我要求没那么高。面完问我在济宁生活有没有困难,最快什么时候到,让人事给我聊薪资了。下午人事打电话,问我27届的会不会跑路,还在想办法如何使我不跑路,不想扣我薪资等。之后我再联系吧,还挺想去的😭,我真不跑路哥😢附一张河科大幽默大专图,科大就是大专罢了
查看30道真题和解析
点赞 评论 收藏
分享
下个早班:秒挂就是不缺人
点赞 评论 收藏
分享
测试糕手手:社会第一课,随便吹牛逼,直接说四个月,别老实。老实人只会被欺负
点赞 评论 收藏
分享
评论
12
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务