自动搬运

查看原文

来自洛谷，原作者为

	Froggy 最初的一步，泪水之后再一次，雕刻的风景线，消逝在黄昏中的风，直到梦的最后。—— Clannad

搬运于2025-08-24 21:55:03，当前版本为作者最后更新于2020-01-08 11:49:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

set,动态开点线段树¿¿¿ 为什么不挑战一下动态开点 $\operatorname{FHQ \ Treap}$ ¿¿¿

这样写代码难度很高,但未尝不是锻炼代码能力的一种方法, [大雾] (珂能我写复杂了,常数巨大,吸氧才过)

其实这道题csp2019前一天就写了一上午,写呱了,心态炸了,期末考试完了拐回头重构代码,终于A了

---

由于是动态开点平衡树,所以每个节点记录一个区间 $(l,r)$

len 为该节点代表的区间长度,即 $r-l+1$

siz 为以该节点为根的子树所构成的区间大小 (注意区分上面两个,否则写着写着就混淆了)

询问操作

好办,val 记录该节点被使用的插排个数, sum 以该节点为根的子树被使用的插排个数

更新节点信息的时候这样就好了

t[k].siz=t[ls].siz+t[rs].siz+t[k].len;
t[k].sum=t[ls].sum+t[rs].sum+t[k].val;

询问的时候把区间分裂出来输出sum

---

重点是----

插入/删除操作

要找到长度最大的连续一段空插座 $(mxl,mxr)$

需要维护 maxlen 即 $mxr-mxl+1$

和要插的位置mid 即 $(mxl+mxr+1)/2$

如果维护了这两个,那么就不需要维护mxl和mxr了.

lmax和rmax,即最左/右边连续空插座的个数

举个例子:

比如一段插座长这样:(1表示有电源插入,0表示空)

110100001000

那么lmax=0, rmax=3, maxlen=4 ,mid=(5+8+1)/2

要插入的位置就很显然了: t[root].mid

还需要开个map::vis方便下一次删除

现在考虑如何维护:

维护lmax和rmax很套路,不说了

分别取左右子树的maxlen的最大值

当t[k].val==0的时候还要特殊讨论:

跨节点k的一段空插座长度为 t[k].len+t[ls].rmax+t[rs].lmax

更新一下就好了啦~

inline void update(int k){
	#define ls t[k].ch[0]
	#define rs t[k].ch[1]
	t[k].siz=t[ls].siz+t[rs].siz+t[k].len;
	t[k].maxlen=0;
	t[k].sum=t[ls].sum+t[rs].sum+t[k].val;
	t[k].lmax=t[ls].lmax;
	t[k].rmax=t[rs].rmax;
	if(ls){//从左子树更新
		t[k].maxlen=t[ls].maxlen;
		t[k].mid=t[ls].mid;
	}
	if(t[k].val==0){ //跨左右子树讨论
		if(t[ls].sum==0){
			t[k].lmax=t[ls].lmax+t[k].len+t[rs].lmax;
		}
		if(t[rs].sum==0){
			t[k].rmax=t[ls].rmax+t[k].len+t[rs].rmax;
		}
		int len=t[k].len+t[ls].rmax+t[rs].lmax;
		if(len>=t[k].maxlen){
			t[k].maxlen=len;
			t[k].mid=(t[k].l-t[ls].rmax+t[k].r+t[rs].lmax+1)>>1;
		}
	}
	if(t[rs].maxlen>=t[k].maxlen){ //从右子树更新
		t[k].maxlen=t[rs].maxlen;
		t[k].mid=t[rs].mid;
	}
	#undef ls
	#undef rs
}

code:

#include<iostream>
#include<cstdio>
#include<map>
#include<cstdlib>
using namespace std;
#define N 100010
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
map<int,int> mp,vis;
int n,Q,root,cnt;
struct node{
	int ch[2],key,l,r,val,sum,siz,len;
	int mid,lmax,rmax,maxlen;
}t[N<<3];
inline int NewNode(int l,int r){
	int k=++cnt;
	t[k].key=rand();
	t[k].l=l,t[k].r=r;
	t[k].mid=(l+r+1)>>1;
	t[k].ch[0]=t[k].ch[1]=0;
	t[k].val=t[k].sum=0;
	t[k].maxlen=t[k].siz=t[k].len=t[k].lmax=t[k].rmax=r-l+1;
	mp[r]=k;
	return k; 
}
inline void update(int k){
	#define ls t[k].ch[0]
	#define rs t[k].ch[1]
	t[k].siz=t[ls].siz+t[rs].siz+t[k].len;
	t[k].maxlen=0;
	t[k].sum=t[ls].sum+t[rs].sum+t[k].val;
	t[k].lmax=t[ls].lmax;
	t[k].rmax=t[rs].rmax;
	if(ls){
		t[k].maxlen=t[ls].maxlen;
		t[k].mid=t[ls].mid;
	}
	if(t[k].val==0){
		if(t[ls].sum==0){
			t[k].lmax=t[ls].lmax+t[k].len+t[rs].lmax;
		}
		if(t[rs].sum==0){
			t[k].rmax=t[ls].rmax+t[k].len+t[rs].rmax;
		}
		int len=t[k].len+t[ls].rmax+t[rs].lmax;
		if(len>=t[k].maxlen){
			t[k].maxlen=len;
			t[k].mid=(t[k].l-t[ls].rmax+t[k].r+t[rs].lmax+1)>>1;
		}
	}
	if(t[rs].maxlen>=t[k].maxlen){
		t[k].maxlen=t[rs].maxlen;
		t[k].mid=t[rs].mid;
	}
	#undef ls
	#undef rs
}
int Merge(int l,int r){
	if(!l||!r)return l+r;
	if(t[l].key<t[r].key){
		t[l].ch[1]=Merge(t[l].ch[1],r);
		update(l);
		return l;
	}
	else{
		t[r].ch[0]=Merge(l,t[r].ch[0]);
		update(r);
		return r;
	}
}
void Split(int k,int data,int &l,int &r){
	if(!k){
		l=r=0;
		return;
	}
	if(t[k].r<=data){
		l=k;
		Split(t[k].ch[1],data,t[k].ch[1],r);
	}
	else{
		r=k;
		Split(t[k].ch[0],data,l,t[k].ch[0]);
	}
	update(k);
}
inline void New(int pos){
	int k=mp.lower_bound(pos)->second;
	int x=t[k].l,y=t[k].r;
	if(x==y&&x==pos)return;
	int l,p,r;
	Split(root,y,l,r);
	Split(l,x-1,l,p);
	mp.erase(t[k].r);
	if(pos>x){
		l=Merge(l,NewNode(x,pos-1));
	}
	if(y>pos){
		r=Merge(NewNode(pos+1,y),r);
	} 
	root=Merge(Merge(l,NewNode(pos,pos)),r);
}
inline int Query(int x,int y){
	New(x),New(y);
	int l,p,r;
	Split(root,y,l,r);
	Split(l,x-1,l,p);
	int ans=t[p].sum;
	root=Merge(Merge(l,p),r);
	return ans;
}
inline void Delete(int pos){
	int l,p,r;
	Split(root,pos,l,r);
	Split(l,pos-1,l,p);
	t[p].val=t[p].sum=0;
	t[p].mid=pos,t[p].maxlen=t[p].lmax=t[p].rmax=t[p].len;
	root=Merge(Merge(l,p),r);
}
inline void Change(int pos){
	New(pos);
	int l,p,r;
	Split(root,pos,l,r);
	Split(l,pos-1,l,p);
	t[p].val=t[p].sum=1;
	t[p].mid=t[p].maxlen=t[p].lmax=t[p].rmax=0;
	root=Merge(Merge(l,p),r);
}
int main(){
	n=read(),Q=read();
	root=NewNode(1,n);
	while(Q--){
		int x=read();
		if(x==0){
			int l=read(),r=read();
			printf("%d\n",Query(l,r));
		}
		else{
			if(vis.count(x)){
				Delete(vis[x]);
				vis.erase(x);
			}
			else{
				vis[x]=t[root].mid;
				Change(t[root].mid);
			}
		}
	}
	return 0;
}

Froggy's blog

呱!!