題目點這里

漏寫博客好多天了，趕快來補

這道題是一個裸的模擬題，注意到紙片總長度不會增加，所以用一個帶翻轉的splay來維護一下

每次將前半段翻轉和后一段做加法合并就好了，均攤logn

#pragma GCC opitmize("O3") #pragma G++ opitmize("O3") #include<stdio.h> #include<string.h> #include<algorithm> #define N 100010 #define son(x) (s[f[x]][1]==x) using namespace std; int f[N],s[N][2],sz[N],v[N],t[N]; int n,m,cnt=0,rt=0,tp=0,stk[N],r[N]; inline int newnode(int p){++cnt; sz[cnt]=1;t[cnt]=v[cnt]=p;return cnt; } inline int ps(int x){sz[x]=sz[s[x][0]]+sz[s[x][1]]+1;t[x]=t[s[x][0]]+v[x]+t[s[x][1]]; } inline void reverse(int x){swap(s[x][0],s[x][1]);r[s[x][0]]^=1; r[s[x][1]]^=1; r[x]=0; } inline void rot(int x){int p=f[x],g=f[p],d=son(x);s[p][d]=s[x][!d]; f[s[p][d]]=p;s[x][!d]=p; f[p]=x; f[x]=g;if(g) s[g][p==s[g][1]]=x; ps(p); ps(x); } inline void splay(int x,int rt=0){for(int y=x;y;y=f[y]) stk[++tp]=y;for(;tp;--tp) if(r[stk[tp]]) reverse(stk[tp]);for(int p;(p=f[x])!=rt;rot(x))if(f[p]!=rt && son(x)==son(p)) rot(p);if(!rt) ::rt=x; } inline int select(int x,int k){for(int w;;){if(r[x]) reverse(x);w=sz[s[x][0]]+1;if(w==k) return x;if(k<w) x=s[x][0];else k-=w,x=s[x][1];} } inline int rank(int x){int r=sz[s[x][0]]+1;for(;x;x=f[x])if(son(x)) r+=sz[s[f[x]][0]]+1;return r; } inline int merge(int x,int y){if(sz[x]>sz[y]) swap(x,y);for(int i=1;sz[x];++i){splay(x=select(x,1));splay(y=select(y,i));v[y]+=v[x]; ps(y); x=s[x][1];}return y; } void print(int x){if(!x) return;print(s[x][0]);printf("[%d]",v[x]);print(s[x][1]); } int main(){scanf("%d%d",&n,&m);for(int x,i=1;i<=n;++i){x=newnode(1);if(i-1) f[i-1]=x,s[x][0]=i-1,ps(x);}rt=cnt; int t1=newnode(0),t2=newnode(0); f[t1]=t2; s[t2][0]=t1;for(int o,x,y;m--;){scanf("%d%d",&o,&x);if(o==1){splay(x=select(rt,x));y=s[x][1]; s[x][1]=0; f[y]=0; ps(x); r[x]=1;rt=merge(x,y);} else {scanf("%d",&y); s[t1][1]=rt; f[rt]=t1; ps(t1); ps(t2);splay(select(t2,++x));splay(select(rt,y+2),rt);printf("%d\n",t[s[s[rt][1]][0]]);splay(t2); splay(t1,rt); f[rt=s[t1][1]]=0; s[t1][1]=0;}//print(rt); puts(""); } }

轉載于:https://www.cnblogs.com/Extended-Ash/p/9477117.html

總結

以上是生活随笔為你收集整理的51Nod1502 苹果曼和纸的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。