bzoj1895&&poj3580 supermemo

bzoj1895&&poj3580 supermemo

​​ Description 给出一个初始序列fA1;A2;:::Ang，要求你编写程序支持如下操作： 1. ADDxyD：给子序列fAx:::Ayg的每个元素都加上D。例如对f1,2, 3,4,5g执行”ADD 241” 会得到f1,3,4,5,5g。 2. REVERSExy：将子序列fAx:::Ayg翻转。例如对f1,2,3,4,5g执 行”REVERSE 24”会得到f1,4,3,2,5g。 3. REVOLVExyT：将子序列fAx:::Ayg旋转T个单位。例如， 对f1,2,3,4,5g执行”REVOLVE 242”会得到f1,3,4,2,5g。 4. INSERTxP：在Ax后插入P。例如，对f1,2,3,4,5g执行”INSERT 24”会得到f1,2,4,3,4,5g。 5. DELETEx：删去Ax。例如，对f1,2,3,4,5g执行”DELETE 2”会得 到f1,3,4,5g。 6. MINxy：查询子序列fAx:::Ayg中的最小元素。例如，对于序列f1, 2,3,4,5g，询问”MIN 24”的返回应为2。 Input 第一行包含一个整数n，表示初始序列的长度。 以下n行每行包含一个整数，描述初始的序列。 接下来一行包含一个整数m，表示操作的数目。 以下m行每行描述一个操作。 Output 对于所有”MIN”操作，输出正确的答案，每行一个。 Sample Input 5 1 2 3 4 5 2 ADD 2 4 1 MIN 4 5 Sample Output 5 HINT

输入、输出以及中间运算结果均不会超过32位整数。 对于30%的数据，n;m 6 1000; 对于100%的数据，n;m 6 100000。

本题需要开longlong

注意这个revolve的操作比较坑..是什么意思呢 蒟蒻我的理解就是将其旋转 而不是对称反转 将其顺时针旋转T个单位 一开始 我sb了想了很久这怎么转 会了这个今年noip那题队列不是就可搞了 后来发现自己sb了 直接算好在哪里切开 然后直接交换下就好

#include#include#define N 220000#define ll long longusing namespace std;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar(); return x*f;}int fa[N],size[N],cnt,root,n,c[N][2],rev[N],a[N];char op[10];ll v[N],min1[N],tag[N];inline void update(int x){ int l=c[x][0],r=c[x][1]; size[x]=size[l]+size[r]+1; min1[x]=min(v[x],min(min1[l],min1[r]));}inline void pushdown(int x){ int l=c[x][0],r=c[x][1]; if (tag[x]){ if (l) tag[l]+=tag[x],min1[l]+=tag[x],v[l]+=tag[x]; if (r) tag[r]+=tag[x],min1[r]+=tag[x],v[r]+=tag[x];tag[x]=0; } if(rev[x]){ rev[x]=0;rev[l]^=1;rev[r]^=1; swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]); }}inline void build(int f,int l,int r){ if (l>r) return; int mid=l+r>>1;v[mid]=a[mid];fa[mid]=f;c[f][mid>f]=mid;min1[mid]=a[mid]; if (l==r){size[l]=1;return;} build(mid,l,mid-1);build(mid,mid+1,r);update(mid);}inline int find(int x,int sz){ pushdown(x);int l=c[x][0],r=c[x][1]; if(size[l]+1==sz) return x; if (sz<=size[l]) return find(l,sz);else return find(r,sz-size[l]-1);}inline void rotate(int x,int &tar){ int y=fa[x],z=fa[y]; if (y==tar) tar=x;else c[z][c[z][1]==y]=x; int l=c[y][1]==x,r=l^1; fa[c[x][r]]=y;fa[y]=x;fa[x]=z; c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);}inline void splay(int x,int &tar){ while(x!=tar){ int y=fa[x],z=fa[y]; if (y!=tar){ if (c[y][0]==x^c[z][0]==y) rotate(x,tar);else rotate(y,tar); }rotate(x,tar); }}inline int split(int x,int y){ int xx=find(root,x),yy=find(root,y); splay(yy,root);splay(xx,c[root][0]);return c[xx][1];}inline void print(int x){ pushdown(x); if (c[x][0]) print(c[x][0]); printf("%d,v[x],size[x],min1[x]); if (c[x][1]) print(c[x][1]);}int main(){ freopen("bzoj1895.in","r",stdin); min1[0]=0x3f3f3f3f;n=read();cnt=n+2; for (int i=2;i<=n+1;++i) a[i]=read();build(0,1,n+2); root=n+3>>1;n=read(); for (int i=1;i<=n;++i){ scanf("%s",op); if (op[0]=='A'){ int x=read(),y=read();ll z=read();int tmp=split(x,y+2); v[tmp]+=z;min1[tmp]+=z;tag[tmp]+=z;update(fa[tmp]); } if (op[0]=='R'){ if (op[3]=='E'){ int x=read(),y=read();int tmp=split(x,y+2);rev[tmp]^=1;swap(c[tmp][0],c[tmp][1]); } if (op[3]=='O'){ int x=read(),y=read(),t=read();int dis=y-x+1;t%=dis;if (!t) continue;t=dis-t; int tmp=split(x,x+t+1);int y2=fa[tmp];c[y2][1]=0;update(y2);update(root);dis-=t; int xx=find(root,x+dis),yy=find(root,x+dis+1);splay(yy,root);splay(xx,c[root][0]); c[xx][1]=tmp;fa[tmp]=xx;update(xx);update(root); } } if (op[0]=='I'){ int x=read(),p=read(); int xx=find(root,x+1),yy=find(root,x+2); splay(yy,root);splay(xx,c[root][0]);v[++cnt]=p;min1[cnt]=p; size[cnt]=1;fa[cnt]=xx;c[xx][1]=cnt;update(xx);update(root); } if (op[0]=='D'){ int x=read();int xx=find(root,x),yy=find(root,x+2);splay(yy,root); splay(xx,c[root][0]);c[xx][1]=0;update(xx);update(root); } if (op[0]=='M'){ int x=read(),y=read();int tmp=split(x,y+2);printf("%lld\n",min1[tmp]); }//print(root);puts(""); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。