首页 > 代码库 > 【BZOJ1895】Pku3580 supermemo Splay
【BZOJ1895】Pku3580 supermemo Splay
【BZOJ1895】Pku3580 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
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。
题解：裸的Splay不解释
个人比较懒，对于区间平移操作直接改为翻转3次，结果因为没取模而狂TLE不止，改完后常数大得惊人。。
#include <cstdio>#include <cstring>#include <iostream>using namespace std;int tot,root,n,m;struct node{ int rev,tag,ch[2],fa,v,siz,sm;}s[600010];char str[10];int rd(){ int ret=0; char gc=getchar(); while(gc<‘0‘||gc>‘9‘) gc=getchar(); while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar(); return ret;}void pushup(int x){ s[x].siz=s[s[x].ch[0]].siz+s[s[x].ch[1]].siz+1; s[x].sm=min(min(s[x].v,s[s[x].ch[0]].sm),s[s[x].ch[1]].sm);}void pushdown(int x){ if(s[x].ch[0]) s[s[x].ch[0]].v+=s[x].tag,s[s[x].ch[0]].sm+=s[x].tag,s[s[x].ch[0]].tag+=s[x].tag; if(s[x].ch[1]) s[s[x].ch[1]].v+=s[x].tag,s[s[x].ch[1]].sm+=s[x].tag,s[s[x].ch[1]].tag+=s[x].tag; s[x].tag=0; if(s[x].rev) { swap(s[x].ch[0],s[x].ch[1]); if(s[x].ch[0]) s[s[x].ch[0]].rev^=1; if(s[x].ch[1]) s[s[x].ch[1]].rev^=1; s[x].rev=0; }}void build(int l,int r,int last){ if(l>r) return ; int mid=l+r>>1; s[mid].fa=last,s[last].ch[mid>last]=mid; build(l,mid-1,mid),build(mid+1,r,mid); pushup(mid);}void rotate(int x,int &k){ int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]); if(z) s[z].ch[y==s[z].ch[1]]=x; if(y==k) k=x; s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1]; if(s[x].ch[d^1]) s[s[x].ch[d^1]].fa=y; s[x].ch[d^1]=y; pushup(y),pushup(x);}int find(int x,int y){ pushdown(x); if(y<=s[s[x].ch[0]].siz) return find(s[x].ch[0],y); if(y==s[s[x].ch[0]].siz+1) return x; return find(s[x].ch[1],y-s[s[x].ch[0]].siz-1);}void splay(int x,int &k){ while(x!=k) { int y=s[x].fa,z=s[y].fa; if(y!=k) { if((x==s[y].ch[0])^(y==s[z].ch[0])) rotate(x,k); else rotate(y,k); } rotate(x,k); }}int main(){ n=rd(); s[0].sm=1<<30; int i,a,b,c; for(i=1;i<=n;i++) scanf("%d",&s[i+1].v); tot=n+2,root=(tot+1)/2; build(1,root-1,root),build(root+1,n+2,root); pushup(root); scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%s",str); if(str[0]==‘A‘) { a=rd()+1,b=rd()+1,c=rd(); splay(find(root,a-1),root),splay(find(root,b+1),s[root].ch[1]); s[s[s[root].ch[1]].ch[0]].tag+=c; s[s[s[root].ch[1]].ch[0]].v+=c; s[s[s[root].ch[1]].ch[0]].sm+=c; pushup(s[root].ch[1]),pushup(root); } if(str[0]==‘R‘&&str[3]==‘E‘) { a=rd()+1,b=rd()+1; splay(find(root,a-1),root),splay(find(root,b+1),s[root].ch[1]); s[s[s[root].ch[1]].ch[0]].rev^=1; } if(str[0]==‘R‘&&str[3]==‘O‘) { a=rd()+1,b=rd()+1,c=rd()%(b-a+1); if(c==0) continue; splay(find(root,a-1),root),splay(find(root,b+1),s[root].ch[1]); s[s[s[root].ch[1]].ch[0]].rev^=1; splay(find(root,a-1),root),splay(find(root,a+c),s[root].ch[1]); s[s[s[root].ch[1]].ch[0]].rev^=1; splay(find(root,a+c-1),root),splay(find(root,b+1),s[root].ch[1]); s[s[s[root].ch[1]].ch[0]].rev^=1; } if(str[0]==‘I‘) { a=rd()+1,b=rd(); splay(find(root,a),root),splay(find(root,a+1),s[root].ch[1]); s[s[root].ch[1]].ch[0]=++tot; s[tot].v=s[tot].sm=b,s[tot].siz=1,s[tot].fa=s[root].ch[1]; pushup(s[root].ch[1]),pushup(root); } if(str[0]==‘D‘) { a=rd()+1; splay(find(root,a-1),root); splay(find(root,a+1),s[root].ch[1]); s[s[root].ch[1]].ch[0]=0; pushup(s[root].ch[1]),pushup(root); } if(str[0]==‘M‘) { a=rd()+1,b=rd()+1; splay(find(root,a-1),root),splay(find(root,b+1),s[root].ch[1]); printf("%d\n",s[s[s[root].ch[1]].ch[0]].sm); } } return 0;}
【BZOJ1895】Pku3580 supermemo Splay
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。