題解：

一道練代碼能力的題目。。

首先很顯然他是一道平衡樹裸題

第5個操作是勢能分析維護最大值最小值就可以了

另外設置虛點和noip2017隊列那題一樣（不過我只寫過線段樹）

具體細節：

1.內存池，要直接判斷(!x) 因為可能進去就是0

2.輸出的時候有重復的要都輸出

3.search的時候要down

4.為了簡單我寫的down是更新自己的，而這個標記會對updata產生影響，所以updata的時候要down兩個兒子

5.splay虛點變變三個點要判斷點數，分三種情況 1個點，2個點，>2個點

這個洛谷評測是什么鬼。。數據測出來是對的顯示wa

另外本題也可以用分塊做。。以后寫下試試

代碼：

?

#include <bits/stdc++.h> using namespace std; #define rint register int #define IL inline #define rep(i,h,t) for (rint i=h;i<=t;i++) #define dep(i,t,h) for (rint i=t;i>=h;i--) #define me(x) memset(x,0,sizeof(x)) #define ll long long const int INF=1e9; const int N=4e6; queue<int> q; int s[N],count2[N],count3[N],data[N],maxa[N],mina[N],rs[N],ls[N],lazy[N],fa[N],root; #define max(a,b) (a)>(b)?(a):(b) #define min(a,b) (a)<(b)?(a):(b) int cnt,minxx=INF; struct phs{IL void down(rint x){if (lazy[x]==INF) return;maxa[x]=mina[x]=data[x]=lazy[x];if (ls[x]) lazy[ls[x]]=lazy[x];if (rs[x]) lazy[rs[x]]=lazy[x];lazy[x]=INF;}IL void updata(rint x){rint l=ls[x],r=rs[x],tmp=data[x];down(l); down(r);count2[x]=count2[l]+count2[r]+count3[x];maxa[x]=max(tmp,max(maxa[l],maxa[r]));mina[x]=min(tmp,min(mina[l],mina[r]));}IL void rotate(int x,int y){int fa1=fa[x];if (y==1){if (ls[x]) fa[ls[x]]=fa1;rs[fa1]=ls[x];} else{if (rs[x]) fa[rs[x]]=fa1;ls[fa1]=rs[x];}fa[x]=fa[fa1];if(fa[fa1]){if (ls[fa[fa1]]==fa1) ls[fa[fa1]]=x;else rs[fa[fa1]]=x;}fa[fa1]=x;if (y==1) ls[x]=fa1; else rs[x]=fa1;updata(fa1); updata(x);}void dfs(int x){if (fa[x]) dfs(fa[x]);down(x);}IL void splay(int x,int goal){dfs(x);int fa1=fa[x];while (fa1!=goal){if (fa[fa1]==goal){if (x==ls[fa1]) rotate(x,2); else rotate(x,1);} elseif (fa1==ls[fa[fa1]])if (x==ls[fa1])rotate(fa1,2),rotate(x,2);else rotate(x,1),rotate(x,2);else if (x==rs[fa1])rotate(fa1,1),rotate(x,1);else rotate(x,2),rotate(x,1);fa1=fa[x];}if (goal==0) root=x;}IL int search(rint k){rint x=root;while (x){down(x); if (s[x]){rint l=ls[x],r=rs[x];rint tmp=count3[x];count3[x]=1;rint now=ls[x]=q.front(); q.pop();fa[now]=x;if ((count3[ls[x]]=tmp/2)!=1) s[now]=1;ls[now]=l; fa[l]=now; data[now]=data[x]; updata(now); if (tmp>2){now=rs[x]=q.front(); q.pop(); data[rs[x]]=data[x];fa[now]=x;if ((count3[now]=tmp-(tmp/2)-1)!=1) s[now]=1;rs[now]=r; fa[r]=now; updata(now);}down(x);s[x]=0;}if (count2[ls[x]]+1==k) return(x);if (count2[ls[x]]+1<k) k-=count2[ls[x]]+1,x=rs[x];else x=ls[x];}}void dfs2(int x){if (!x) return;cnt++;q.push(x);dfs2(ls[x]);dfs2(rs[x]);ls[x]=rs[x]=count2[x]=s[x]=data[x]=fa[x]=maxa[x]=mina[x]=0;count3[x]=1;lazy[x]=INF; }IL void split(int x,int y){splay(x,0); splay(y,x);}IL void cl(int x){down(x);int k1=sqrt(maxa[x]); int k2=sqrt(mina[x]);if (k1==k2){lazy[x]=k1; down(x);return;}data[x]=sqrt(data[x]);if (ls[x]) cl(ls[x]);if (rs[x]) cl(rs[x]);updata(x);}IL void ycl(){root=1; rs[1]=2; fa[2]=1; count2[1]=2; count2[2]=1;}IL void ou(int x){down(x);if (ls[x]) ou(ls[x]);if (x!=1&&x!=2)rep(i,1,count3[x]) printf("%d ",data[x]); if (rs[x]) ou(rs[x]);} }S; int main() {freopen("1.in","r",stdin);freopen("1.out","w",stdout);ios::sync_with_stdio(false);int m;cin>>m;maxa[0]=-INF; mina[0]=INF;int len=0;rep(i,3,N-1) q.push(i);rep(i,0,N-1) lazy[i]=INF,count3[i]=1;S.ycl();rep(i,1,m){minxx=min(minxx,q.size());int x,y,z,k;cin>>k;if (k==1){cin>>x>>y;rint now=S.search(len+1);S.splay(2,0); S.splay(now,2);rint now2=rs[now]=q.front(); q.pop();count3[now2]=x; data[now2]=y; fa[now2]=now; if (x!=1) s[now2]=1;S.splay(now2,0);len+=x;}if (k==2){int x;cin>>x;len-=x;x=S.search(x+2);S.split(1,x); // S.dfs2(ls[x]);ls[x]=0;S.splay(x,0);}if (k==3){int kk;cin>>x>>y>>z>>kk;rint t=y-x+1;rint ans=1;while(z){if (z&1) ans=(1ll*ans*t)%kk;t=(1ll*t*t)%kk;z>>=1;}int l=S.search(x);int r=S.search(y+2); S.split(l,r);lazy[ls[r]]=ans;S.splay(ls[r],0);}if (k==4){int x,y;cin>>x>>y;//cout<<x<<" "<<y<<endl;len-=y-x; x=S.search(x),y=S.search(y+2);S.split(x,y);S.down(ls[y]);int now=ls[y];int mm=maxa[now];// S.dfs2(ls[now]); S.dfs2(rs[now]);ls[now]=rs[now]=0; lazy[now]=INF; count3[now]=1; s[now]=0;data[now]=mm; S.splay(now,0);printf("%d\n",mm);}if (k==5){cin>>x>>y;x=S.search(x),y=S.search(y+2);S.split(x,y);int now=ls[y];S.cl(now); }}S.ou(root); // printf("\n%d\n%d",cnt,minxx);return 0; }

?

轉載于:https://www.cnblogs.com/yinwuxiao/p/9497398.html

總結

以上是生活随笔為你收集整理的Chino的数列的全部內容，希望文章能夠幫你解決所遇到的問題。

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