锐客网

  1. 首页 > it技术 > >

比赛题解|2020 杭电多校9 1007 Game （平衡树）

数据结构HDU比赛题解

题意： 给一个方块的序列b i bi bi ，如下图。有q q q 次询问，每次有两种操作，一种操作为( x , y ) (x,y) (x,y) ，表示从第x x x 列的y y y 的方格的位置向左移一格，同时将上面的都会带动，并且若左边有方块则也依次向左移，若y y y 是空的，或者移出边界，则不移动。第二种操作，则是查询第x x x 列的方块个数。
比赛题解|2020 杭电多校9 1007 Game （平衡树）
文章图片

思路： 【比赛题解|2020 杭电多校9 1007 Game （平衡树）】对于1 1 1 操作，若设l l l 为最大的位置使得m i n { b [ l ] 到 b [ x ] } > = y min\{b[l] 到 b[x]\}>=y min{b[l]到b[x]}>=y ，若l = 1 l=1 l=1 则不操作，否则此时b [ l ? 1 ] b[l-1] b[l?1] 的值为b [ l ? 1 ] + b [ l ] ? y + 1 b[l-1]+b[l]-y+1 b[l?1]+b[l]?y+1 ，b [ l ] b[l] b[l] 到b [ x ? 1 ] b[x-1] b[x?1] 的值，应该都等于后面位置的值，b [ x ] b[x] b[x] 的值就变成y ? 1 y-1 y?1 ,相当于将b [ l ] = y ? 1 b[l]=y-1 b[l]=y?1 ，并且将b [ l ] b[l] b[l] 和b [ l + 1 ] b[l+1] b[l+1] 到b [ x ] b[x] b[x] 这一段交换位置。这些操作就可以使用平衡树来实现，下面代码使用f h q t r e a p fhq_treap fhqt?reap 实现，其中s p i l t spilt spilt _r r r _m i n ( ) min() min() 为核心操作，可以得到l l l 的值。
代码：

#include #define ll long long using namespace std; const int N=5e5+10; int T,n,q; int b[N]; int x,y; int ans[N]; mt19937 rnd(13331); struct fhq_treap{ #define ls(x) ch[x][0] #define rs(x) ch[x][1] int sz[N],mi[N],val[N],ch[N][2],key[N]; ll sum[N]; int cnt,root; void init() { //要初始化 for(int i=0; i<=n+1; i++) ls(i)=rs(i)=0; cnt=0; mi[0]=1e9+7; } inline void up(int o) { sz[o]=sz[ls(o)]+sz[rs(o)]+1; sum[o]=sum[ls(o)]+sum[rs(o)]+val[o]; mi[o]=min(val[o],min(mi[ls(o)],mi[rs(o)])); } inline int built(int *a,int l,int r) { //直接构建 if(l>r) return 0; int now=++cnt; int mid=(l+r)/2; sum[now]=mi[now]=val[now]=a[mid]; sz[now]=(r-l+1); key[now]=rnd(); ls(now)=built(a,l,mid-1); rs(now)=built(a,mid+1,r); up(now); return now; } inline void spilt(int o,int siz,int &x,int &y) { //按大小分 if(o==0) {x=y=0; return; } if(sz[ls(o)]) { x=o; spilt(rs(o),siz-sz[ls(o)]-1,rs(o),y); }else { y=o; spilt(ls(o),siz,x,ls(o)); } up(o); } inline void spilt_r_min(int o,int v,int &x,int &y) { //重要操作，将大于等于v的分到y树上，其余分到x树上 if(o==0) {x=y=0; return ; } if(mi[rs(o)]key[y]) { rs(x)=merge(rs(x),y); up(x); return x; }else { ls(y)=merge(x,ls(y)); up(y); return y; } return -1; } inline int getnum(int pos) { int now=root; while(sz[ls(now)]+1!=pos) { if(pos>sz[ls(now)]+1) { pos-=sz[ls(now)]+1; now=rs(now); }else now=ls(now); } return val[now]; } inline ll getsum(int x,int y) { if(getnum(x)=y) { root=merge(t1,t2); return 0; } spilt_r_min(t1,y,t1,t3); ll res=sum[t3]-1ll*(y-1)*sz[t3]; //统计移动个数 spilt(t1,sz[t1]-1,t1,t4); //t1+t4+t3+t5+t2 spilt(t3,1,t3,t5); val[t4]+=val[t3]-y+1; mi[t4]=sum[t4]=val[t4]; val[t3]=mi[t3]=sum[t3]=y-1; //t1+t4+t5+t3+t2 root=merge(merge(merge(merge(t1,t4),t5),t3),t2); return res; } }treap; int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&q); treap.init(); for(int i=1; i<=n; i++) scanf("%d",&b[i]); treap.root=treap.built(b,1,n); while(q--) { int op; scanf("%d",&op); if(op==1) { scanf("%d%d",&x,&y); printf("%lld\n",treap.getsum(x,y)); }else { scanf("%d",&x); int gs=treap.getnum(x); printf("%d\n",gs); } } for(int i=1; i<=n; i++) printf("%d%c",treap.getnum(i),i==n?'\n':' '); } }

    推荐阅读


    上一篇：QT|QT面试

    下一篇：RSA原理