首页 > 代码库 > BZOJ1895: Pku3580 supermemo
BZOJ1895: Pku3580 supermemo
1895: Pku3580 supermemo
Time Limit: 15 Sec Memory Limit: 64 MBSubmit: 77 Solved: 47
[Submit][Status]
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执行"INSERT24"会得到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。
Source
题解：
又被输入坑了。。。
splay裸题。。。T了5.6次，最后把每次的字符串清空然后就A了。。。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 2000000+5 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,q,tot,fa[maxn],c[maxn][2],rt,t1,t2,s[maxn],tag[maxn],mi[maxn],v[maxn]; 61 bool rev[maxn]; 62 inline void pushup(int x) 63 { 64 if(!x)return; 65 int l=c[x][0],r=c[x][1]; 66 s[x]=s[l]+s[r]+1; 67 mi[x]=min(v[x],min(mi[l],mi[r])); 68 } 69 inline void rotate(int x,int &k) 70 { 71 int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 72 if(y!=k)c[z][c[z][1]==y]=x;else k=x; 73 fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 74 c[y][l]=c[x][r];c[x][r]=y; 75 pushup(y);pushup(x); 76 } 77 inline void splay(int x,int &k) 78 { 79 while(x!=k) 80 { 81 int y=fa[x],z=fa[y]; 82 if(y!=k) 83 { 84 if((c[z][0]==y)^(c[y][0]==x))rotate(x,k);else rotate(y,k); 85 } 86 rotate(x,k); 87 } 88 } 89 inline void add(int x,int z) 90 { 91 if(!x)return; 92 mi[x]+=z;tag[x]+=z;v[x]+=z; 93 } 94 inline void rever(int x) 95 { 96 if(!x)return; 97 rev[x]^=1; 98 swap(c[x][0],c[x][1]); 99 }100 inline void pushdown(int x)101 {102 if(!x)return;103 if(tag[x]){add(c[x][0],tag[x]);add(c[x][1],tag[x]);tag[x]=0;}104 if(rev[x]){rever(c[x][0]);rever(c[x][1]);rev[x]=0;}105 }106 inline int find(int x,int k)107 {108 pushdown(x);109 int l=c[x][0],r=c[x][1];110 if(s[l]+1==k)return x;111 else if(s[l]>=k)return find(l,k);112 else return find(r,k-s[l]-1);113 }114 inline void split(int l,int r)115 {116 t1=find(rt,l);t2=find(rt,r);117 splay(t1,rt);splay(t2,c[rt][1]);118 }119 inline void build(int l,int r,int f)120 {121 if(l>r)return;122 int x=(l+r)>>1;123 fa[x]=f;c[f][x>f]=x;124 if(l==r){mi[x]=v[x];s[x]=1;return;}125 build(l,x-1,x);build(x+1,r,x);126 pushup(x);127 }128 129 int main()130 131 {132 133 n=read();134 for2(i,2,n+1)v[i]=read();135 v[1]=v[n+2]=mi[0]=2147483647;tot=n+2;136 build(1,n+2,0);rt=(1+n+2)>>1;137 q=read();char ch[10];138 while(q--)139 {140 memset(ch,0,sizeof(ch));141 scanf("%s",ch);int x=read();142 if(ch[0]==‘D‘)split(x,x+2),c[t2][0]=0;143 else if(ch[0]==‘I‘)split(x+1,x+2),fa[c[t2][0]=++tot]=t2,s[tot]=1,v[tot]=mi[tot]=read();144 else if(ch[4]==‘L‘)145 {146 int y=read(),t=read()%(y-x+1);if(!t)continue;147 split(y+2-t-1,y+2);int tmp=c[t2][0];c[t2][0]=0;148 pushup(t2);pushup(t1);149 split(x,x+1);c[t2][0]=tmp;fa[tmp]=t2;150 }151 else152 {153 int y=read();split(x,y+2);int z=c[t2][0];154 if(ch[0]==‘A‘)add(z,read());155 else if(ch[0]==‘M‘)printf("%d\n",mi[z]);156 else rever(z);157 }158 pushup(t2);pushup(t1);159 }160 161 return 0;162 163 }
splay直接暴力往上居然还快了1s233‘
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 2000000+5 26 27 #define maxm 500+100 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,q,tot,fa[maxn],c[maxn][2],rt,t1,t2,s[maxn],tag[maxn],mi[maxn],v[maxn]; 61 bool rev[maxn]; 62 inline void pushup(int x) 63 { 64 if(!x)return; 65 int l=c[x][0],r=c[x][1]; 66 s[x]=s[l]+s[r]+1; 67 mi[x]=min(v[x],min(mi[l],mi[r])); 68 } 69 inline void rotate(int x,int &k) 70 { 71 int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; 72 if(y!=k)c[z][c[z][1]==y]=x;else k=x; 73 fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 74 c[y][l]=c[x][r];c[x][r]=y; 75 pushup(y);pushup(x); 76 } 77 inline void splay(int x,int &k) 78 { 79 while(x!=k)rotate(x,k); 80 } 81 inline void add(int x,int z) 82 { 83 if(!x)return; 84 mi[x]+=z;tag[x]+=z;v[x]+=z; 85 } 86 inline void rever(int x) 87 { 88 if(!x)return; 89 rev[x]^=1; 90 swap(c[x][0],c[x][1]); 91 } 92 inline void pushdown(int x) 93 { 94 if(!x)return; 95 if(tag[x]){add(c[x][0],tag[x]);add(c[x][1],tag[x]);tag[x]=0;} 96 if(rev[x]){rever(c[x][0]);rever(c[x][1]);rev[x]=0;} 97 } 98 inline int find(int x,int k) 99 {100 pushdown(x);101 int l=c[x][0],r=c[x][1];102 if(s[l]+1==k)return x;103 else if(s[l]>=k)return find(l,k);104 else return find(r,k-s[l]-1);105 }106 inline void split(int l,int r)107 {108 t1=find(rt,l);t2=find(rt,r);109 splay(t1,rt);splay(t2,c[rt][1]);110 }111 inline void build(int l,int r,int f)112 {113 if(l>r)return;114 int x=(l+r)>>1;115 fa[x]=f;c[f][x>f]=x;116 if(l==r){mi[x]=v[x];s[x]=1;return;}117 build(l,x-1,x);build(x+1,r,x);118 pushup(x);119 }120 121 int main()122 123 {124 125 freopen("input.txt","r",stdin);126 127 freopen("output.txt","w",stdout);128 129 n=read();130 for2(i,2,n+1)v[i]=read();131 v[1]=v[n+2]=mi[0]=2147483647;tot=n+2;132 build(1,n+2,0);rt=(1+n+2)>>1;133 q=read();char ch[10];134 while(q--)135 {136 memset(ch,0,sizeof(ch));137 scanf("%s",ch);int x=read();138 if(ch[0]==‘D‘)split(x,x+2),c[t2][0]=0;139 else if(ch[0]==‘I‘)split(x+1,x+2),fa[c[t2][0]=++tot]=t2,s[tot]=1,v[tot]=mi[tot]=read();140 else if(ch[4]==‘L‘)141 {142 int y=read(),t=read()%(y-x+1);if(!t)continue;143 split(y+2-t-1,y+2);int tmp=c[t2][0];c[t2][0]=0;144 pushup(t2);pushup(t1);145 split(x,x+1);c[t2][0]=tmp;fa[tmp]=t2;146 }147 else 148 {149 int y=read();split(x,y+2);int z=c[t2][0];150 if(ch[0]==‘A‘)add(z,read());151 else if(ch[0]==‘M‘)printf("%d\n",mi[z]);152 else rever(z);153 }154 pushup(t2);pushup(t1);155 }156 157 return 0;158 159 }
BZOJ1895: Pku3580 supermemo
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。