序列终结者

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

全部评论
#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
//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
_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
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
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
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 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
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 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
void revise(int x,int val){ x=findk(root,x); splay(x,0); v[x]+=val; pushup(x); }
11 回复 分享
发布于 2019-11-25 14:28
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
int query(int x){ x=findk(root,x); return v[x]; }
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 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
真道题好难啊
10 回复 分享
发布于 2019-12-05 19:48
怎么办得呀,谁能帮帮我呀
10 回复 分享
发布于 2019-12-05 19:48
简直毒瘤
10 回复 分享
发布于 2019-12-05 19:48
毒瘤
10 回复 分享
发布于 2019-12-05 19:49
太毒瘤
10 回复 分享
发布于 2019-12-05 19:49
毒瘤
4 回复 分享
发布于 2019-12-09 14:52

相关推荐

我已成为0offer的糕手:别惯着,胆子都是练出来的,这里认怂了,那以后被裁应届被拖工资还敢抗争?
点赞 评论 收藏
分享
沉淀一会:**圣经 1.同学你面试评价不错,概率很大,请耐心等待;2.你的排名比较靠前,不要担心,耐心等待;3.问题不大,正在审批,不要着急签其他公司,等等我们!4.预计9月中下旬,安心过节;5.下周会有结果,请耐心等待下;6.可能国庆节前后,一有结果我马上通知你;7.预计10月中旬,再坚持一下;8.正在走流程,就这两天了;9.同学,结果我也不知道,你如果查到了也告诉我一声;10.同学你出线不明朗,建议签其他公司保底!11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
12 收藏 评论
分享
牛客网
牛客企业服务