首页 > 代码库 > poj 3580 SuperMemo (Splay)
poj 3580 SuperMemo (Splay)
poj 3580
好恶心的题目，真是各种操作都来了个遍 。。。
不过Splay树真是一种神奇的东西，通过旋转就能实现各种操作，而且方法也都相差不大 。
题意：
给出一个数字序列，有6种操作：
（1） ADD x y d： 第x个数到第y个数加d 。
（2） REVERSE x y ： 将区间[x,y]中的数翻转 。
（3） REVOLVE x y t ：将区间[x,y]旋转t次，如1 2 3 4 5 旋转2次后就变成4 5 1 2 3 。
（4） INSERT x p ：在第x个数后面插入p 。
（5）DELETE x ：删除第x个数 。
（6） MIN x y ： 查询区间[x,y]中的最小值 。
解法：
关于第三点，一开始想难道是一个数一个数从后面取出放到最前面？但这样复杂度太大 。后来仔细一想，既然一个数一个数弄可以，为啥不直接切出一个区间放到最前面呢，然后，就没有然后了 。。。
注意t可能很大，所以要先取模 。（至于有没有可能出现负数，我是没试过，反正做了处理就是了 。。。）
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cmath> 5 #include <cstring> 6 #include <queue> 7 #include <set> 8 #include <vector> 9 #include <map> 10 #define ll long long 11 12 using namespace std; 13 14 const int N=200000+7; 15 const int INF=0x3f3f3f3f; 16 17 struct tree{ 18 int key,size,fa,MIN,add,son[2]; 19 bool flag; 20 }t[N]; 21 int tot,root; 22 23 24 inline void vis(int x){ // Debug 25 if (!x) return; 26 printf("节点:%2d : 左儿子 %2d 右儿子 %2d key值 %2d size值 %2d filp: %d\n",x,t[x].son[0],t[x].son[1],t[x].key,t[x].size,t[x].flag); 27 printf("节点:%2d : 最小值 %2d \n",x,t[x].MIN); 28 vis(t[x].son[0]); 29 vis(t[x].son[1]); 30 } 31 32 int A[N]; 33 int n; 34 35 inline void pushup(int x){ 36 t[x].size=t[t[x].son[0]].size+t[t[x].son[1]].size+1; 37 t[x].MIN=t[x].key; 38 if (t[x].son[0]) 39 t[x].MIN=min(t[x].MIN,t[t[x].son[0]].MIN); 40 if (t[x].son[1]) 41 t[x].MIN=min(t[x].MIN,t[t[x].son[1]].MIN); 42 } 43 44 inline void pushdown(int x){ 45 if (t[x].flag){ 46 t[x].flag=false; 47 swap(t[x].son[0],t[x].son[1]); 48 t[t[x].son[0]].flag^=1; 49 t[t[x].son[1]].flag^=1; 50 } 51 52 if (t[x].add>0){ 53 if (t[x].son[0]){ 54 t[t[x].son[0]].key+=t[x].add; 55 t[t[x].son[0]].add+=t[x].add; 56 t[t[x].son[0]].MIN+=t[x].add; 57 } 58 if (t[x].son[1]){ 59 t[t[x].son[1]].key+=t[x].add; 60 t[t[x].son[1]].add+=t[x].add; 61 t[t[x].son[1]].MIN+=t[x].add; 62 } 63 t[x].add=0; 64 } 65 } 66 67 inline void rotate(int x,int p){ 68 int y=t[x].fa; 69 pushdown(y); 70 pushdown(x); 71 t[y].son[!p]=t[x].son[p]; 72 t[t[x].son[p]].fa=y; 73 t[x].fa=t[y].fa; 74 if (t[x].fa) 75 t[t[x].fa].son[t[t[x].fa].son[1]==y]=x; 76 t[x].son[p]=y; 77 t[y].fa=x; 78 pushup(y); 79 pushup(x); 80 } 81 82 inline void Splay(int x,int to){ 83 while (t[x].fa!=to){ 84 if (t[t[x].fa].fa==to) 85 rotate(x,t[t[x].fa].son[0]==x); 86 else { 87 int y=t[x].fa,z=t[y].fa; 88 int p=(t[z].son[0]==y); 89 if (t[y].son[p]==x) 90 rotate(x,!p),rotate(x,p); 91 else 92 rotate(y,p),rotate(x,p); 93 } 94 } 95 if (to==0) root=x; 96 } 97 98 inline int newnode(int key,int fa){ 99 ++tot;100 t[tot].key=key;101 t[tot].fa=fa;102 t[tot].size=1;103 t[tot].MIN=key;104 t[tot].add=0;105 t[tot].flag=false;106 t[tot].son[0]=t[tot].son[1]=0;107 return tot;108 }109 110 inline int get_kth(int k){111 int x=root;112 for(;;){113 pushdown(x);114 if (k==t[t[x].son[0]].size+1)115 break;116 if (k>t[t[x].son[0]].size+1){117 k-=t[t[x].son[0]].size+1;118 x=t[x].son[1];119 }120 else 121 x=t[x].son[0];122 }123 return x;124 }125 126 inline int bulidtree(int L,int R,int fa){127 if (L>R) return 0;128 129 int mid=(L+R)>>1,x;130 x=newnode(A[mid],fa);131 t[x].son[0]=bulidtree(L,mid-1,x);132 t[x].son[1]=bulidtree(mid+1,R,x);133 pushup(x);134 135 return x;136 }137 138 inline void add(int L,int R,int d){139 L=get_kth(L);140 R=get_kth(R+2);141 Splay(L,0);142 Splay(R,L); 143 t[t[R].son[0]].key+=d;144 t[t[R].son[0]].MIN+=d;145 t[t[R].son[0]].add+=d;146 pushup(R);147 pushup(L);148 }149 150 inline void reverse(int L,int R){151 L=get_kth(L);152 R=get_kth(R+2);153 Splay(L,0);154 Splay(R,L);155 t[t[R].son[0]].flag^=1;156 }157 158 inline void revolve(int L,int R,int k){159 k=(k%(R-L+1)+(R-L+1))%(R-L+1);160 if (!k) return;161 162 int x=get_kth(R-k+1);163 int y=get_kth(R+2);164 Splay(x,0);165 Splay(y,x);166 int tmp=t[y].son[0];167 t[y].son[0]=0; 168 pushup(y);169 pushup(x);170 171 x=get_kth(L);172 y=get_kth(L+1);173 Splay(x,0);174 Splay(y,x);175 t[y].son[0]=tmp;176 t[tmp].fa=y;177 pushup(y);178 pushup(x);179 }180 181 inline void insert(int x,int p){182 Splay(get_kth(x+1),0);183 Splay(get_kth(x+2),root);184 t[t[root].son[1]].son[0]=newnode(p,t[root].son[1]);185 pushup(t[root].son[1]);186 pushup(root);187 }188 189 inline void del(int x){190 Splay(get_kth(x),0);191 Splay(get_kth(x+2),root);192 t[t[root].son[1]].son[0]=0;193 pushup(t[root].son[1]);194 pushup(root);195 }196 197 inline int query(int L,int R){198 int x=get_kth(L);199 int y=get_kth(R+2);200 Splay(x,0);201 Splay(y,x);202 return t[t[y].son[0]].MIN;203 }204 205 int main(){206 scanf("%d",&n);207 for (int i=1;i<=n;i++) scanf("%d",&A[i]);208 A[0]=A[n+1]=INF;209 210 root=bulidtree(0,n+1,0);211 // 由于取点的时候很多是取该点的前一个点或者后一个点，所以要加多两个虚节点212 213 int m,x,y,z;214 char ch[20];215 scanf("%d",&m);216 while (m--){217 scanf("%s",ch);218 switch (ch[0]){219 case ‘A‘:220 scanf("%d %d %d",&x,&y,&z);221 add(x,y,z);222 break;223 case ‘R‘:224 if (ch[3]==‘E‘) {225 scanf("%d %d",&x,&y);226 reverse(x,y);227 }228 else {229 scanf("%d %d %d",&x,&y,&z);230 revolve(x,y,z);231 }232 break;233 case ‘I‘:234 scanf("%d %d",&x,&y);235 insert(x,y);236 break;237 case ‘D‘:238 scanf("%d",&x);239 del(x);240 break;241 case ‘M‘:242 scanf("%d %d",&x,&y);243 printf("%d\n",query(x,y));244 break;245 }246 }247 248 return 0;249 }
poj 3580 SuperMemo (Splay)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。