题意： 给一个方块的序列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 （平衡树）】对于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':' ');
}
}
推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔