序列终结者
给定一个长度为N的序列，每个序列的元素是一个整数。要支持以下五种操作：
1.查询第K位置上的数。
2.把第K个位置上的数加上X。
3.查询[L,R]这个区间的和。
4.查询[L,R]这个区间的最大值。
5.将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。
2019-11-25 14:29 已编辑 电子科技大学 C++
关注
全部评论
nocwoder 楼主
楼主 电子科技大学 C++
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; }
nocwoder 楼主
楼主 电子科技大学 C++
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; }
nocwoder 楼主
楼主 电子科技大学 C++
int query(int x){ x=findk(root,x); return v[x]; }
nocwoder 楼主
楼主 电子科技大学 C++
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]]; }
nocwoder 楼主
楼主 电子科技大学 C++
void revise(int x,int val){ x=findk(root,x); splay(x,0); v[x]+=val; pushup(x); }
nocwoder 楼主
楼主 电子科技大学 C++
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); }
nocwoder 楼主
楼主 电子科技大学 C++
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); }
nocwoder 楼主
楼主 电子科技大学 C++
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; }
nocwoder 楼主
楼主 电子科技大学 C++
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); }
nocwoder 楼主
楼主 电子科技大学 C++
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; } }
nocwoder 楼主
楼主 电子科技大学 C++
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; }
nocwoder 楼主
楼主 电子科技大学 C++
_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; }
nocwoder 楼主
楼主 电子科技大学 C++
//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++)
nocwoder 楼主
楼主 电子科技大学 C++
#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>
nocwoder 楼主
楼主 电子科技大学 C++
太毒瘤
nocwoder 楼主
楼主 电子科技大学 C++
毒瘤
nocwoder 楼主
楼主 电子科技大学 C++
简直毒瘤
nocwoder 楼主
楼主 电子科技大学 C++
怎么办得呀，谁能帮帮我呀
nocwoder 楼主
楼主 电子科技大学 C++
真道题好难啊
nocwoder 楼主
楼主 电子科技大学 C++
毒瘤毒瘤
相关推荐
不愿透露姓名的神秘牛友
昨天 15:24
在度假的布拉德很想退...：敢主动删hr微信你也是强
点赞 评论 收藏
分享
查看30道真题和解析