CF899F Letters Removing 题解

CF899F Letters Removing 题解

这好像是个典题。

解法

一个很自然的想法。

考虑开 $62$ 颗平衡树，即每一种字符都开一颗平衡树，维护的是每种字符出现的位置，每次操作就把对应的平衡树区间删去即可，是很基础的非旋 treap 操作。

实现就是按值分裂。

inline std::pair<fhq_node *,fhq_node *> split(fhq_node *rt,const int k)
{
	std::pair<fhq_node *,fhq_node *> ret;
	if(rt==nullptr) return std::make_pair(nullptr,nullptr);
	if(k<rt->val) ret=split(rt->lc,k),rt->lc=ret.second,rt->pushup(),ret.second=rt;
	else ret=split(rt->rc,k),rt->rc=ret.first,rt->pushup(),ret.first=rt;
	return ret;
}

当我搓完平衡树后发现过不了样例，仔细看样例才发现，字符的标号是随着删除操作而变化的。所以我们需要动态的维护每个数的标号，这也是很典的问题。考虑用一个树状数组，初始值都是 $1$，表示所有字符都没有被删除，之后每删除一个字符，我们就在树状数组的对应位置减 $1$，树状数组中第 $k$ 大的数的位置就是删除后的第 $k$ 个字符在原序列中的位置。最朴素的想法就是在树状数组上二分。

当然，有比树状数组上二分复杂度更优的做法，就是树状数组上倍增。

注意到树状数组上的节点 $c_i$ 表示 $\sum _{j=i-lowbit(i)+1}^i{a}_j$，所以我们从高位向低位枚举答案的每个二进制位即可。

inline int kth(int k)
{
	int sum=0,ret=0;
	for(int i=lgn;i>=0;i--)
	{
		ret+=1<<i;
		if(ret>=n || sum+c[ret]>=k) ret-=1<<i;
		else sum+=c[ret];
	}
	return ret+1;
}

时间复杂度：$\mathcal{O}(n\log n)$，即树状数组初始化、平衡树区间删除、树状数组获取第 $k$ 小值、树状数组单点修改的复杂度。

代码

#include<bits/stdc++.h>
namespace fast_IO
{
	/**
	 * 快读快写
	*/
};
using namespace fast_IO;
int n,m;
char ans[200010],now;
class BIT
{
	#define N 200010
private:
	int c[N],lgn;
	inline int lowbit(const int &x)
	{
		return x&(-x);
	}
public:
	inline void init()
	{
		lgn=log2(n);
	}
	inline void fix(int pos,int x)
	{
		while(pos<=n) c[pos]+=x,pos+=lowbit(pos);
	}
	inline int kth(int k)
	{
		int sum=0,ret=0;
		for(int i=lgn;i>=0;i--)
		{
			ret+=1<<i;
			if(ret>=n || sum+c[ret]>=k) ret-=1<<i;
			else sum+=c[ret];
		}
		return ret+1;
	}
};
BIT fenwik_tree;
template<typename T>
inline void swap(T &_x,T &_y)
{
	T tmp=_x;
	_x=_y,_y=tmp;
}
struct fhq_node
{
	int val,w,siz;
	fhq_node *lc,*rc;
	inline fhq_node(int val)
	{
		this->val=val,w=rand(),siz=1,lc=rc=nullptr;
	}
	inline void pushup()
	{
		siz=(lc==nullptr?0:lc->siz)+(rc==nullptr?0:rc->siz)+1;
	}
};
class fhq_treap
{
	#define ls l,mid-1
	#define rs mid+1,r
private:
	fhq_node *root;
	std::vector<int> v;
	inline fhq_node *merge(fhq_node *l,fhq_node *r)
	{
		if(l==nullptr && r==nullptr) return nullptr;
		if(l==nullptr) return r;
		if(r==nullptr) return l;
		if(l->w<r->w)
		{
			l->rc=merge(l->rc,r),l->pushup();
			return l;
		}else
		{
			r->lc=merge(l,r->lc),r->pushup();
			return r;
		}
	}
	inline std::pair<fhq_node *,fhq_node *> split(fhq_node *rt,const int k)
	{
		std::pair<fhq_node *,fhq_node *> ret;
		if(rt==nullptr) return std::make_pair(nullptr,nullptr);
		if(k<rt->val) ret=split(rt->lc,k),rt->lc=ret.second,rt->pushup(),ret.second=rt;
		else ret=split(rt->rc,k),rt->rc=ret.first,rt->pushup(),ret.first=rt;
		return ret;
	}
	inline fhq_node *build(int l,int r)
	{
		if(l>r) return nullptr;
		if(l==r) return new fhq_node(v[l-1]);
		int mid=(l+r)/2;
		fhq_node *rt=new fhq_node(v[mid-1]);
		rt->lc=build(ls),rt->rc=build(rs);
		rt->pushup();
		return rt;
	}
	inline void print(fhq_node *rt)
	{
		if(rt==nullptr) return;
		if(rt->lc!=nullptr) print(rt->lc);
		ans[rt->val]=now;
		if(rt->rc!=nullptr) print(rt->rc);
	}
	inline void del(fhq_node *rt)
	{
		if(rt==nullptr) return;
		if(rt->lc!=nullptr) del(rt->lc);
		fenwik_tree.fix(rt->val,-1);
		if(rt->rc!=nullptr) del(rt->rc);
		delete rt;
	}
public:
	inline void push_back(const int x)
	{
		v.push_back(x);
	}
	inline void build()
	{
		root=build(1,(int)v.size());
	}
	inline void del(const int L,const int R)
	{
		std::pair<fhq_node *,fhq_node *> a,b;
		a=split(root,R),b=split(a.first,L-1),del(b.second);
		root=merge(b.first,a.second);
	}
	inline void print()
	{
		print(root);
	}
};
fhq_treap tree[70];
std::unordered_map<char,int> mp;
std::unordered_map<int,char> imp;
char ch;
int main()
{
	srand(time(0));
	for(int i=1;i<=26;i++) mp['a'+i-1]=i,imp[i]='a'+i-1;
	for(int i=27;i<=52;i++) mp['A'+i-27]=i,imp[i]='A'+i-27;
	for(int i=53;i<=62;i++) mp['0'+i-53]=i,imp[i]='0'+i-53;
	in>>n>>m,fenwik_tree.init();
	for(int i=1;i<=n;i++) in>>ch,tree[mp[ch]].push_back(i),fenwik_tree.fix(i,1);
	for(int i=1;i<=62;i++) tree[i].build();
	for(int i=1,x,y;i<=m;i++)
	{
		in>>x>>y>>ch;
		x=fenwik_tree.kth(x),y=fenwik_tree.kth(y);
		tree[mp[ch]].del(x,y);
	}
	for(int i=1;i<=62;i++) now=imp[i],tree[i].print();
	for(int i=1;i<=n;i++) if(ans[i]) out<<ans[i];
	fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
	return 0;
}