CodeForces 85D

洛谷题目页面传送门 & CodeForces题目页面传送门

有一个集合(s)，你需要支持以下(3)种(q)次操作：

1. ( exttt{add} x)：令(s=scup{x})，保证在执行之前(x otin s)，(xinleft[1,10^9 ight])；
2. ( exttt{del} x)：令(s=s-{x})，保证在执行之前(xin s)，(xinleft[1,10^9 ight])；
3. ( exttt{sum})：设将(s)中所有元素排序后得到1-indexed序列(a)，查询(sumlimits_{iin[1,|a|],imod5=3}a_i)。

(qinleft[1,10^5 ight])。

这其实是一个比较简单的DS题，毕竟难度只有(^*2200)。只不过这题比较nb，一题四解。

解法(1)：离散化+线段树

考虑建一棵值域线段树，设节点(i)表示区间([l_i,r_i])，那么节点(i)存储([l_i,r_i])内(in s)的数的数量(cnt_i)，和(forall jin[0,5))，区间([l_i,r_i])内所有(in s)的元素排序后所有下标(mod5=j)的数的和(sum_{i,j})。那么上传时令(cnt_i=cnt_{lson_i}+cnt_{rson_i},sum_{i,j}=sum_{lson_i,j}+sum_{rson_i,left(j-cnt_{lson_i} ight)mod5})即可。一次上传时间复杂度(mathrm O(1))。

由于值域大小为(10^9)，我们可以将所有操作离线下来并离散化所有数值。

此时( exttt{add}, exttt{del})操作都是简单的单点修改，(mathrm O(log q))；( exttt{sum})操作是整体查询，直接调用(sum_{root,3})即可，(mathrm O(1))。

总空间复杂度(mathrm O(q))，时间复杂度(mathrm O(qlog q))。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int QU=100000;
int qu;//操作数 
struct query{int tp,x;}qry[QU+1];//操作 
vector<int> nums;//离散化数组 
void discrete(){//离散化 
	sort(nums.begin(),nums.end());
	nums.resize(unique(nums.begin(),nums.end())-nums.begin());
	for(int i=1;i<=qu;i++)if(qry[i].tp!=2)qry[i].x=lower_bound(nums.begin(),nums.end(),qry[i].x)-nums.begin();
}
struct segtree{//线段树 
	struct node{int l,r,sum[5],cnt;}nd[QU<<2];
	#define l(p) nd[p].l
	#define r(p) nd[p].r
	#define sum(p) nd[p].sum
	#define cnt(p) nd[p].cnt
	void bld(int l=0,int r=(int)(nums.size())-1,int p=1){//建树 
		if(l>r)return;
		l(p)=l;r(p)=r;sum(p)[0]=sum(p)[1]=sum(p)[2]=sum(p)[3]=sum(p)[4]=cnt(p)=0;
		if(l==r)return;
		int mid=l+r>>1;
		bld(l,mid,p<<1);bld(mid+1,r,p<<1|1);
	} 
	void init(){bld();}//线段树初始化 
	void sprup(int p){//上传 
		cnt(p)=cnt(p<<1)+cnt(p<<1|1);
		for(int i=0;i<5;i++)sum(p)[i]=sum(p<<1)[i]+sum(p<<1|1)[(((i-cnt(p<<1))%5)+5)%5];
	}
	void add(int x,int p=1){//add操作 
		if(l(p)==r(p))return sum(p)[1]=nums[x],cnt(p)=1/*此数in s*/,void();
		int mid=l(p)+r(p)>>1;
		add(x,p<<1|(x>mid));
		sprup(p);
	}
	void del(int x,int p=1){//del操作 
		if(l(p)==r(p))return sum(p)[1]=cnt(p)=0/*此数notin s*/,void();
		int mid=l(p)+r(p)>>1;
		del(x,p<<1|(x>mid));
		sprup(p);
	}
	int _sum()/*sum操作*/{return nums.size()?sum(1)[3]:0;} 
}segt;
signed main(){
	cin>>qu;
	for(int i=1;i<=qu;i++){//离线 
		string tp;
		cin>>tp;
		if(tp=="add")qry[i].tp=0,cin>>qry[i].x,nums.pb(qry[i].x);
		else if(tp=="del")qry[i].tp=1,cin>>qry[i].x,nums.pb(qry[i].x);
		else qry[i].tp=2;
	}
	discrete();//离散化 
	segt.init();//线段树初始化 
	for(int i=1;i<=qu;i++){ 
		int tp=qry[i].tp,x=qry[i].x;
		if(tp==0)segt.add(x);
		else if(tp==1)segt.del(x);
		else cout<<segt._sum()<<"
";
	}
	return 0;
}

解法(2)：动态开点线段树

线段树部分的思路与解法(1)完全一样，不过此方法利用动态开点来处理值域过大问题，实现了在线执行操作。

总空间复杂度(mathrm O(qlog q))，时间复杂度(mathrm O(qlog q))。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int QU=100000,A_I=1000000000,LOG_A_I=30;
int qu;//操作数 
struct segtree{//动态开点线段树 
	int sz;//点数 
	struct node{int l,r,lson,rson,sum[5],cnt;}nd[QU*LOG_A_I+1];
	#define l(p) nd[p].l
	#define r(p) nd[p].r
	#define lson(p) nd[p].lson
	#define rson(p) nd[p].rson
	#define sum(p) nd[p].sum
	#define cnt(p) nd[p].cnt
	int nwnd(int l=1,int r=A_I){return nd[++sz]=node({l,r,0,0,{0,0,0,0,0},0}),sz;}//新建节点 
	void init(){nd[0]=node({0,0,0,0,{0,0,0,0,0},0});sz=0;nwnd();}//线段树初始化 
	void sprup(int p){//上传 
		cnt(p)=cnt(lson(p))+cnt(rson(p));
		for(int i=0;i<5;i++)sum(p)[i]=sum(lson(p))[i]+sum(rson(p))[(((i-cnt(lson(p)))%5)+5)%5];
	}
	void add(int x,int p=1){//add操作 
		if(l(p)==r(p))return sum(p)[1]=x,cnt(p)=1/*此数in s*/,void();
		int mid=l(p)+r(p)>>1;
		if(x<=mid)add(x,lson(p)=lson(p)?lson(p):nwnd(l(p),mid));
		else add(x,rson(p)=rson(p)?rson(p):nwnd(mid+1,r(p)));
		sprup(p);
	}
	void del(int x,int p=1){//del操作 
		if(l(p)==r(p))return sum(p)[1]=cnt(p)=0/*此数notin s*/,void();
		int mid=l(p)+r(p)>>1;
		if(x<=mid)del(x,lson(p)=lson(p)?lson(p):nwnd(l(p),mid));
		else del(x,rson(p)=rson(p)?rson(p):nwnd(mid+1,r(p)));
		sprup(p);
	}
	int _sum()/*sum操作*/{return sum(1)[3];} 
}segt;
signed main(){
	cin>>qu;
	segt.init();//线段树初始化 
	while(qu--){
		string tp;int x;
		cin>>tp;
		if(tp=="add")cin>>x,segt.add(x);
		else if(tp=="del")cin>>x,segt.del(x);
		else cout<<segt._sum()<<"
";
	}
	return 0;
}

解法(3)：分块

分块是无所不能的

其实上面那句话在某种程度上是正确的

考虑对(s)中所有元素排序后得到的1-indexed序列(a)分块。由于有插入、删除操作，所以这是一个动态调整块内元素的分块。

考虑维护set(s)。块(i)内存(a)的某一个子段(a'_i)，和(forall jin[0,5))，该1-indexed子段(a'_i)内所有下标(mod5=j)的数的和(sum_{i,j})。

• 扫描：调整所有块内元素使得每块内元素数量不超过(sz1)。从左往右依次扫描每个块(i)，如果(|a'_i|>sz1)（此时必然有(|a'_i|=sz1+1)，因为每次( exttt{add})操作之后都进行扫描），那么将(a'_{i,|a'_i|})放到(a'_{i+1})的前面，并(mathrm O(1))重算(sum_i,sum_{i+1})。由于要在两端操作，所以(a'_i)应该定义为deque<int>。时间复杂度(mathrm O!left(dfrac q{sz1} ight))。

• 对于( exttt{add})操作：通过(s)二分找到距离(x)最近的(in s)的元素(x')，找到(x')所在块并将(x)插入该块且维护有序性。暴力重算该块内的(sum)。更新(s)。扫描一遍。时间复杂度(mathrm O!left(log q+sz1+dfrac q{sz1} ight))。

• 对于( exttt{del})操作：找到(x)所在块并将(x)删除。暴力重算该块内的(sum)。更新(s)。扫描一遍。时间复杂度(mathrm O!left(sz1+dfrac q{sz1} ight))。

• 对于( exttt{sum})操作：从左往右让每个块贡献答案即可，这样是(mathrm O!left(dfrac q{sz1} ight))的。然鹅其实可以优化到(mathrm O(1))，就是每次扫描时顺便算出答案并记录下来，这样就可以直接调用。

令(sz1=leftlfloor sqrt q ight floor)，这样总时间复杂度(mathrm O(qsqrt q))。空间复杂度(mathrm O(q))。

然后开开森森的交上去，T了？是因为这巨大的复杂度乘上巨大的常数。于是开始卡常。

先将( exttt{add}, exttt{del})内的“暴力重算该块内的(sum)”用指针寻址优化一下（因为deque的随机访问很慢）。此时( exttt{add}, exttt{del})前面一部分的常数与最后的扫描的常数形成了鲜明的对比，因为扫描还带一个(5)的常数。于是调参要从娃娃抓起，我们将(sz1)稍微调大一点，来实现常数上的尽量平衡。令(sz1=3leftlfloor sqrt q ight floor)即可AC。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pf push_front
#define ppb pop_back
#define pb push_back
const int QU=100000,DB_SZ=500;
int qu;
struct dvdblk{//分块 
	int sz1,ans/*任意时刻的答案*/;
	struct block{
		deque<int> a;int sum[5];
		block(){sum[0]=sum[1]=sum[2]=sum[3]=sum[4]=0;}
	}blk[DB_SZ];
	#define a(p) blk[p].a
	#define sum(p) blk[p].sum
	set<int> all;
	void init(){ans=0;sz1=3*sqrt(qu);}//分块初始化 
	void scn(){//扫描 
		int now=0;
		ans=0;
		for(int i=1;i<=(qu+sz1-1)/sz1;i++){
			if(a(i).size()>sz1){
				a(i+1).pf(a(i).back());//将此块的最后一个元素放到后面一块 
				int tmp[]={sum(i+1)[0],sum(i+1)[1],sum(i+1)[2],sum(i+1)[3],sum(i+1)[4]};
				for(int j=0;j<5;j++)sum(i+1)[j]=tmp[(j-1+5)%5];
				sum(i+1)[1]+=a(i+1)[0];//O(1)调整sum[i+1] 
				sum(i)[a(i).size()%5]-=a(i).back();//O(1)调整sum[i] 
				a(i).ppb();//将此块的最后一个元素放到后面一块  
			}
			ans+=sum(i)[((3-now)%5+5)%5];//计算当前的答案 
			now+=a(i).size();
		}
	}
	void add(int x){//add操作 
		if(all.empty())a(1).pb(x),sum(1)[1]=x;//特判s为空的情况 
		else{
			set<int>::iterator fd=all.lower_bound(x);
			if(fd==all.end())fd--;
			int p;
			for(int i=1;;i++)if(a(i)[0]<=*fd&&*fd<=a(i).back()){p=i;break;}//找到即将插入的块 
			a(p).insert(lower_bound(a(p).begin(),a(p).end(),x),x);//插入 
			sum(p)[0]=sum(p)[1]=sum(p)[2]=sum(p)[3]=sum(p)[4]=0;
			int now=1;
			deque<int>::iterator end=a(p).end();
			for(deque<int>::iterator i=a(p).begin();i!=end;++i,++now,now==5&&(now=0))sum(p)[now]+=*i;//暴力重算sum[p]（寻址优化后） 
		}
		all.insert(x);//维护s 
		scn();//扫描 
	}
	void del(int x){//del操作 
		int p;
		for(int i=1;;i++)if(a(i)[0]<=x&&x<=a(i).back()){p=i;break;}//找到即将插入的块 
		a(p).erase(lower_bound(a(p).begin(),a(p).end(),x));//删除 
		sum(p)[0]=sum(p)[1]=sum(p)[2]=sum(p)[3]=sum(p)[4]=0;
		int now=1;
		deque<int>::iterator end=a(p).end();
		for(deque<int>::iterator i=a(p).begin();i!=end;++i,++now,now==5&&(now=0))sum(p)[now]+=*i;//暴力重算sum[p]（寻址优化后） 
		all.erase(x);//维护s 
		scn();//扫描 
	}
	int _sum()/*sum操作*/{return ans;}
}db;
signed main(){
	cin>>qu;
	db.init();//分块初始化 
	for(int i=1;i<=qu;i++){ 
		string tp;int x;
		cin>>tp;
		if(tp=="add")cin>>x,db.add(x);
		else if(tp=="del")cin>>x,db.del(x);
		else cout<<db._sum()<<"
";
	}
	return 0;
}

解法(4)：平衡树

看到往集合里添加、删除，不难想到平衡树。这里使用fhq-Treap。

节点(i)存储此节点的权值(v_i)，以(i)为根的子树的大小(sz_i)，和(forall jin[0,5))，以(i)为根的子树内所有元素排序后所有下标(mod5=j)的数的和(sum_{i,j})。那么上传时令(sz_i=sz_{lson_i}+1+sz_{rson_i},sum_{i,j}=sum_{lson_i,j}+left[j=(sz_{lson_i}+1)mod5 ight]v_i+sum_{rson_i,left(j-cnt_{lson_i}-1 ight)mod5})即可。一次上传时间复杂度(mathrm O(1))。

此时( exttt{add}, exttt{del})操作都是简单的单点插入/删除，(mathrm O(log q))；( exttt{sum})操作是整体查询，直接调用(sum_{root,3})即可，(mathrm O(1))。

总空间复杂度(mathrm O(q))，时间复杂度(mathrm O(qlog q))。

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define X first
#define Y second
mt19937 rng(20060617/*信仰优化*/);
const int QU=100000;
int qu;//操作数
struct fhq_treap{//fhq-Treap 
	int sz/*点数*/,root/*根*/;
	struct node{unsigned key;int lson,rson,sz,v,sum[5];}nd[QU+1];
	#define key(p) nd[p].key
	#define lson(p) nd[p].lson
	#define rson(p) nd[p].rson
	#define sz(p) nd[p].sz
	#define v(p) nd[p].v
	#define sum(p) nd[p].sum
	void init(){nd[sz=root=0]=node({0,0,0,0,0,{0,0,0,0,0}});}//fhq-Treap初始化 
	void sprup(int p){//上传 
		sz(p)=sz(lson(p))+1+sz(rson(p));
		for(int i=0;i<5;i++)sum(p)[i]=sum(lson(p))[i]+sum(rson(p))[(((i-sz(lson(p))-1)%5)+5)%5];
		sum(p)[(sz(lson(p))+1)%5]+=v(p);
	}
	pair<int,int> split(int x,int p=-1){~p||(p=root); 
		if(!x)return mp(0,p);
		pair<int,int> sp;
		if(x<=sz(lson(p)))return sp=split(x,lson(p)),lson(p)=sp.Y,sprup(p),mp(sp.X,p);
		return sp=split(x-sz(lson(p))-1,rson(p)),rson(p)=sp.X,sprup(p),mp(p,sp.Y);
	}
	int mrg(int p,int q){
		if(!p||!q)return p|q;
		if(key(p)<key(q))return rson(p)=mrg(rson(p),q),sprup(p),p;
		return lson(q)=mrg(p,lson(q)),sprup(q),q;
	}
	int lss(int v,int p=-1)/*比v小的数的个数*/{~p||(p=root); 
		if(!p)return 0;
		if(v(p)<v)return sz(lson(p))+1+lss(v,rson(p));
		return lss(v,lson(p));
	}
	int nwnd(int v){return nd[++sz]=node({rng(),0,0,1,v,{0,v,0,0,0}}),sz;}//新建节点 
	void add(int v){//add操作 
		pair<int,int> sp=split(lss(v));
		root=mrg(mrg(sp.X,nwnd(v)),sp.Y);
	}
	void del(int v){//del操作 
		pair<int,int> sp=split(lss(v)),sp0=split(1,sp.Y);
		root=mrg(sp.X,sp0.Y);
	}
	int _sum()/*sum操作*/{return sum(root)[3];}
}trp;
signed main(){
	cin>>qu;
	trp.init();//fhq-Treap初始化 
	while(qu--){
		string tp;int x;
		cin>>tp;
		if(tp=="add")cin>>x,trp.add(x);
		else if(tp=="del")cin>>x,trp.del(x);
		else cout<<trp._sum()<<"
";
	}
	return 0;
}

(4)种解法的比较

	离散化+线段树	动态开点线段树	分块	平衡树
操作响应时间	离线	在线	在线	在线
时间复杂度	(mathrm O(qlog q))	(mathrm O(qlog q))	(mathrm O(qsqrt q))	(mathrm O(qlog q))
空间复杂度	(mathrm O(q))	(mathrm O(qlog q))	(mathrm O(q))	(mathrm O(q))
最慢的点运行时长	(996mathrm{ms})	(1340mathrm{ms})	(2494mathrm{ms})	(1746mathrm{ms})

看起来平衡树全方位吊打其他所有解法，但是它的常数还是比不过线段树。