●贅述題目

四種操作：

○Reset：將整個(gè)內(nèi)存序列清空。

○New a：在盡量靠左的位置新建一個(gè)長(zhǎng)度為a的內(nèi)存塊，并輸出改內(nèi)存塊起始位置。（各個(gè)內(nèi)存塊即使相鄰也不會(huì)合并。。）

○Free a：將a點(diǎn)所在的內(nèi)存塊清空，并輸出清空的內(nèi)存區(qū)間的左右端點(diǎn)。

○Get a：輸出從左往右數(shù)的第a個(gè)內(nèi)存塊的起始位置。

●題解

方法：Splay在線維護(hù)

(○本來(lái)想的將序列中的每個(gè)點(diǎn)看作Splay樹(shù)中的一個(gè)節(jié)點(diǎn)，然后進(jìn)行區(qū)間操作。。但似乎比較麻煩。。)

○正解(erge大佬提出的思路)：考慮到每個(gè)內(nèi)存塊不會(huì)合并的性質(zhì)，將每一個(gè)內(nèi)存塊看作Splay樹(shù)中的一個(gè)節(jié)點(diǎn)，且中序遍歷各個(gè)節(jié)點(diǎn)的順序即對(duì)應(yīng)內(nèi)存序列中各個(gè)內(nèi)存塊的從左至右的順序（如下圖）（區(qū)間化點(diǎn)）。然后剩下便是Splay的單點(diǎn)操作。

○為方便一些操作，先就加入兩個(gè)邊界點(diǎn)。

?

●代碼

(注意NEW(insert)函數(shù)啊，有點(diǎn)坑坑。。)

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 50005 #define ls tr[k][0] #define rs tr[k][1] using namespace std; int fa[MAXN],tr[MAXN][2]; int l[MAXN],r[MAXN],ll[MAXN],rr[MAXN],ma[MAXN],siz[MAXN]; int tot,root; void pushup(int k) {ll[k]=ls?ll[ls]:l[k]; rr[k]=rs?rr[rs]:r[k];ma[k]=max(max(ls?ma[ls]:0,rs?ma[rs]:0),max(ls?l[k]-rr[ls]-1:0,rs?ll[rs]-r[k]-1:0));siz[k]=1+(ls?siz[ls]:0)+(rs?siz[rs]:0); } void rotate(int x,int &k) {int y=fa[x],z=fa[y];int l=tr[y][1]==x,r=1^l;if(y==k) k=x;else tr[z][tr[z][1]==y]=x;fa[tr[x][r]]=y; fa[y]=x; fa[x]=z;tr[y][l]=tr[x][r]; tr[x][r]=y;pushup(y); } void splay(int x,int &k) {int y,z;while(x!=k){y=fa[x]; z=fa[y];if(y!=k) ((tr[z][0]==y)^(tr[y][0]==x)) ? rotate(x,k):rotate(y,k);rotate(x,k);}pushup(x); } int NEW(int &k,int last,int len,int fg,int sl) {if(!k){k=++tot;fa[k]=last;l[k]=sl; r[k]=l[k]+len-1;tr[k][0]=tr[k][1]=0;splay(k,root);return l[root];} if(fg==0) return NEW(rs,k,len,0,r[k]+1);else if(fg==1) return NEW(ls,k,len,1,sl);else if(ls&&ma[ls]>=len) return NEW(ls,k,len,-1,sl);else if(ls&&l[k]-rr[ls]-1>=len) return NEW(ls,k,len,0,r[k]+1);else if(rs&&ll[rs]-r[k]-1>=len) return NEW(rs,k,len,1,r[k]+1);else if(rs&&ma[rs]>=len) return NEW(rs,k,len,-1,sl);return 0; } int find(int k,int x) {if(ll[ls]<=x&&x<=rr[ls]) return find(ls,x);else if(l[k]<=x&&x<=r[k]) return k;else if(ll[rs]<=x&&x<=rr[rs]) return find(rs,x);return 0; } int FREE(int x) {int k=find(root,x);if(!k) return 0;splay(k,root);if(ls*rs==0) root=ls+rs,fa[root]=0;else{int p=rs;while(tr[p][0]) p=tr[p][0];tr[p][0]=ls;fa[ls]=p;root=rs;fa[root]=0;splay(ls,root);}return k; } int GET(int k,int x) {if(siz[ls]>=x) return GET(ls,x); x-=siz[ls];if(x==1) return l[k]; x-=1;if(siz[rs]>=x) return GET(rs,x);return 0; } void pre(int n) {root=1; tot=2;tr[1][0]=0; tr[1][1]=2; tr[2][0]=0; tr[2][1]=0;fa[2]=1;l[1]=r[1]=0; l[2]=r[2]=n+1;pushup(2); pushup(1); } int main() {int n,m,a,b; char s[10]; while(~scanf("%d%d",&n,&m)){pre(n);while(m--){scanf(" %s",s);if(s[0]=='R') pre(n),printf("Reset Now\n");else if(s[0]=='N') scanf("%d",&a),1<=a&&a<=n?b=NEW(root,0,a,-1,-1):b=0,b?printf("New at %d\n",b):printf("Reject New\n");else if(s[0]=='F') scanf("%d",&a),1<=a&&a<=n?b=FREE(a):b=0,b?printf("Free from %d to %d\n",l[b],r[b]):printf("Reject Free\n");else if(s[0]=='G') scanf("%d",&a),siz[root]-2>=a?b=GET(root,a+1):b=0,b?printf("Get at %d\n",b):printf("Reject Get\n"); }printf("\n");}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/zj75211/p/7251160.html

總結(jié)

以上是生活随笔為你收集整理的●HDU 2871 Memory Control（Splay）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。