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
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。
Solution
模板题。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; const int N=210000; int n,a[N],root,tot,m; char s[20]; struct SPLAY { int fa[N],son[N][2],size[N],Min[N],lazy_add[N],rev[N],Tree[N]; void update(int x) { if (!x) return; int l=son[x][0],r=son[x][1]; size[x]=size[l]+size[r]+1; Min[x]=Tree[x]; if (l) Min[x]=min(Min[x],Min[l]); if (r) Min[x]=min(Min[x],Min[r]); } void downdate(int x) { if (!x) return; int l=son[x][0],r=son[x][1]; if (lazy_add[x]!=0) { if (l) Tree[l]+=lazy_add[x],Min[l]+=lazy_add[x],lazy_add[l]+=lazy_add[x]; if (r) Tree[r]+=lazy_add[x],Min[r]+=lazy_add[x],lazy_add[r]+=lazy_add[x]; lazy_add[x]=0; } if (rev[x]) { swap(son[x][0],son[x][1]); if (l) rev[l]^=1; if (r) rev[r]^=1; rev[x]=0; } } void Rotate(int x,int &k) { int y=fa[x],z=fa[y],l,r; if (x==son[y][0]) l=0;else l=1; r=l^1; if (y==k) k=x; else { if (son[z][0]==y) son[z][0]=x;else son[z][1]=x; } fa[x]=z;fa[y]=x;fa[son[x][r]]=y; son[y][l]=son[x][r];son[x][r]=y; update(y);update(x); } void splay(int x,int &k) { while (x!=k) { int y=fa[x],z=fa[y]; if (y!=k) { if ((son[z][0]==y)^(son[y][0]==x)) Rotate(x,k); else Rotate(y,k); } Rotate(x,k); } } void build(int l,int r,int father) { if (l>r) return; if (l==r) { fa[l]=father; if (l<father) son[father][0]=l; else son[father][1]=l; Tree[l]=a[l]; rev[l]=0; lazy_add[l]=0; size[l]=1; Min[l]=a[l]; return; } int mid=(l+r)>>1; build(l,mid-1,mid); build(mid+1,r,mid); fa[mid]=father; if (mid<father) son[father][0]=mid; else son[father][1]=mid; Tree[mid]=a[mid]; Min[mid]=a[mid]; rev[mid]=0; lazy_add[mid]=0; size[mid]=1; update(mid); } int find(int x) { int i=root; while (i) { downdate(i); if (size[son[i][0]]+1==x) return i; if (size[son[i][0]]>=x) i=son[i][0]; else x-=size[son[i][0]]+1,i=son[i][1]; } } int split(int x,int y) { int i=find(x),j=find(y); splay(i,root); splay(j,son[i][1]); return son[j][0]; } void Add(int x,int y,int z) { int i=split(x-1,y+1); Min[i]+=z; Tree[i]+=z; lazy_add[i]+=z; update(fa[i]); update(fa[fa[i]]); } void Reverse(int x,int y) { int i=split(x-1,y+1); rev[i]^=1; } void Insert(int x,int y) { int i=find(x),j=find(x+1); splay(i,root); splay(j,son[i][1]); son[j][0]=++tot; fa[tot]=j; Min[tot]=y; Tree[tot]=y; lazy_add[tot]=0; rev[tot]=0; size[tot]=1; update(j); update(i); } void Del(int x) { int i=split(x-1,x+1); son[fa[i]][0]=0; update(fa[i]); update(fa[fa[i]]); fa[i]=0; Tree[i]=Min[i]=lazy_add[i]=rev[i]=size[i]=0; if (i==root) root=0; } int Min_Ans(int x,int y) { int i=split(x-1,y+1); return Min[i]; } }Splay; int main() { scanf("%d",&n); a[1]=a[n+2]=(1LL<<31)-1; for (int i=2;i<=n+1;i++) scanf("%d",&a[i]); Splay.build(1,n+2,0); root=(n+3)>>1; tot=n+2; scanf("%d",&m); while (m--) { int x,y,z; scanf("%s",s+1); if (s[1]=='A') scanf("%d%d%d",&x,&y,&z),Splay.Add(++x,++y,z); if (s[1]=='R'&&s[4]=='E') scanf("%d%d",&x,&y),Splay.Reverse(++x,++y); if (s[1]=='R'&&s[4]=='O') { scanf("%d%d%d",&x,&y,&z); x++;y++; int len=(z%(y-x+1)+(y-x+1))%(y-x+1); if (len==0) continue; Splay.Reverse(x,y); Splay.Reverse(x,x+len-1); Splay.Reverse(x+len,y); } if (s[1]=='I') scanf("%d%d",&x,&y),Splay.Insert(++x,y); if (s[1]=='D') scanf("%d",&x),Splay.Del(++x); if (s[1]=='M') scanf("%d%d",&x,&y),printf("%d\n",Splay.Min_Ans(++x,++y)); } return 0; } |
