15011418730 LV 7 @ 2025-8-24 23:09:52

自动搬运

来自洛谷，原作者为

	dAniel_lele 当你在幻想上天会给你开一扇窗的时候，你已经输一半了。

搬运于2025-08-24 23:09:52，当前版本为作者最后更新于2025-04-15 17:11:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

真不是给人写的。

先思考操作 3 怎么做。考虑求出每个字符串反串的 SA，然后分别找 $s$ 前面加上 $l-1$ 和 $r$ 在 SA 中的 lower_bound，相减即为答案。

再考虑操作 0，也就是说我们需要在反串的末尾加入字符的同时维护 SA。考虑使用平衡树维护之，每次需要比较两个前缀的大小，可以使用二分哈希比较，这里我们使用更为快捷好写的自然溢出，是可以通过的，可以发现本题出题人还是十分良心的，不像某题解审核组 i 姓同学一天到晚想着卡哈希。

然后是操作 1，本操作跟操作 3 本质相同，唯一的问题是 $k$ 次操作后 $y$ 字符串是什么。显然其应该是一个 $y$ 字符串的前缀，我们记录一下即可。

最后考虑操作 2，由于我们需要字符串赋值，我们显然不能重新构建一遍后缀平衡树。考虑将所有字符串放到一个 Trie 上，那么字符串对应的就是一个节点到根（操作 1 同样可以记录），这样赋值的问题就解决了。至于平衡树第一个想法便是对其进行可持久化，这样复杂度已经对了！然而这样大概会 MLE 且难写。考虑将 Trie 上所有节点对应的 SA 扔到一棵平衡树中，同时维护每个平衡树节点包含了多少个在每个字符串中的 Trie 上节点。对于赋值操作，可以记录一个 $to_x$ 数组表示 $x$ 字符串是赋值前的 $to_x$ 字符串。这样就可以空间线性了。

总复杂度 $O((len+q)(\log(len+q)+n)\log(len+q))$ ，可以通过。

#include <bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
using namespace std;
const unsigned int mul=200467;
unsigned int pw[1000005];
unsigned int shash[20][1000005];
int sval[1000005],slen;
int aimpos,aimadd;
int n;
namespace Trie{
	unordered_map<signed,signed> f[500005];
	signed up[20][500005],dep[500005],val[500005];
	unsigned int hsh[20][500005];
	int cnt;
	void init(){
		for(int i=1;i<=cnt;i++){
			for(int j=0;j<20;j++) up[j][i]=0;
			f[i].clear();
		}
		val[1]=-1;
		cnt=1;
	}
	int add(int x,int y){
		if(f[x][y]) return f[x][y];
		f[x][y]=++cnt; dep[cnt]=dep[x]+1,val[cnt]=y;
		up[0][cnt]=x; hsh[0][cnt]=y+1;
		for(int j=1;j<=19;j++){
			up[j][cnt]=up[j-1][up[j-1][cnt]];
			hsh[j][cnt]=hsh[j-1][cnt]+hsh[j-1][up[j-1][cnt]]*pw[1<<(j-1)];
		}
		return cnt;
	}
}
void gethash(vector<int> s){
	slen=s.size(); sval[0]=-1;
	for(int i=1;i<=slen;i++){
		shash[0][i]=s[i-1]+1; sval[i]=s[i-1];
		for(int j=1;(1<<j)<=i;j++) shash[j][i]=shash[j-1][i]+shash[j-1][i-(1<<(j-1))]*pw[1<<(j-1)];
	}
}
int cmp(int x,int y){
	if(x<0){
		if(x==-1){
			x=slen;
			for(int i=19;i>=0;i--){
				if((1<<i)<=min((int)Trie::dep[y],x)){
					if(Trie::hsh[i][y]==shash[i][x]){
						y=Trie::up[i][y];
						x-=(1<<i);
					}
				}
			}
			return (sval[x]<Trie::val[y])?0:((Trie::val[y]==sval[x])?1:2);
		}
		else{
//			cout<<aimpos<<" "<<aimadd<<" "<<y<<"\n";
			x=aimpos;
			for(int i=19;i>=0;i--){
				if((1<<i)<=min(Trie::dep[x],Trie::dep[y])){
					if(Trie::hsh[i][x]==Trie::hsh[i][y]){
						x=Trie::up[i][x];
						y=Trie::up[i][y];
					}
				}
			}
//			cout<<x<<" "<<y<<"\n";
			if(x!=1) return (Trie::val[x]<Trie::val[y])?0:((Trie::val[x]==Trie::val[y])?1:2);
			if(Trie::val[y]==aimadd){
				y=Trie::up[0][y];
				if(Trie::val[y]==-1) return 1;
				return 0; 
			}
			return (aimadd<Trie::val[y])?0:2;
		}
	}
	else{
//		bool rep=0;
//		if(x==7&&y==2) cout<<Trie::hsh[0][7]<<" "<<Trie::hsh[0][2]<<" OK\n",rep=1;
		for(int i=19;i>=0;i--){
			if((1<<i)<=min(Trie::dep[x],Trie::dep[y])){
				if(Trie::hsh[i][x]==Trie::hsh[i][y]){
					x=Trie::up[i][x];
					y=Trie::up[i][y];
				}
			}
		}
//		if(rep) cout<<x<<" "<<y<<"\n";
		return (Trie::val[x]<Trie::val[y])?0:((Trie::val[x]==Trie::val[y])?1:2);
	}
}
int res[5],root;
namespace Tree{
	const double alpha=0.75;
	const int N=2000005;
	int ver[N],tsz[N][5],sz[N][5],L[N],R[N],tag[N][5];
	int buffer_size,buffer[N],tmp_size[N][5];
	int ntsz[5],nsz[5],ntag[5];
	void init(){
		root=1;
	}
	void new_node(int &rt,int p){
		rt=p; ver[rt]=1;
		for(int i=0;i<n;i++) tsz[rt][i]=sz[rt][i]=0,tag[rt][i]=i;
		L[rt]=R[rt]=0;
	}
	void pushup(int rt){
		if(!rt) return ;
		for(int i=0;i<n;i++) tsz[rt][i]=tsz[L[rt]][i]+sz[rt][i]+tsz[R[rt]][i];
		ver[rt]=ver[L[rt]]+ver[R[rt]]+1;
	}
	void addtrans(int rt,int to[5]){
		for(int i=0;i<n;i++){
			ntsz[i]=tsz[rt][to[i]];
			nsz[i]=sz[rt][to[i]];
			ntag[i]=tag[rt][to[i]];
		}
		for(int i=0;i<n;i++){
			tsz[rt][i]=ntsz[i];
			sz[rt][i]=nsz[i];
			tag[rt][i]=ntag[i];
		}
	}
	void pushdown(int rt){
		if(L[rt]) addtrans(L[rt],tag[rt]);
		if(R[rt]) addtrans(R[rt],tag[rt]);
		for(int i=0;i<n;i++) tag[rt][i]=i;
	}
	bool balance(int rt){
		return alpha*ver[rt]>max(ver[L[rt]],ver[R[rt]]);
	}
	void flatten(int rt){
		if(!rt) return ;
		pushdown(rt);
		flatten(L[rt]);
		buffer[++buffer_size]=rt;
		for(int i=0;i<n;i++) tmp_size[buffer_size][i]=sz[rt][i];
		flatten(R[rt]);
	}
	void build(int &rt,int l,int r){
		if(l>r){
			rt=0; return ;
		}
		rt=buffer[mid];
		for(int i=0;i<n;i++) sz[rt][i]=tmp_size[mid][i];
		build(L[rt],l,mid-1),build(R[rt],mid+1,r);
		pushup(rt);
	}
	void rebuild(int &rt){
		buffer_size=0;
		flatten(rt);
		build(rt,1,buffer_size);
	}
	void add(int &rt,int p,int cg){
//		cout<<rt<<" "<<p<<" "<<cg<<"\n";
		if(!rt){
			new_node(rt,p);
			tsz[rt][cg]=sz[rt][cg]=1;
			return ;
		}
		int sta=cmp(p,rt);
		if(sta==1){
			tsz[rt][cg]++,sz[rt][cg]++;
			return ;
		}
		pushdown(rt);
		if(sta==0) add(L[rt],p,cg);
		if(sta==2) add(R[rt],p,cg);
		pushup(rt);
		if(!balance(rt)) rebuild(rt);
	}
	void qry1(int &rt,int p){ // <p
		if(!rt) return ;
		int sta=cmp(p,rt);
		pushdown(rt);
		if(sta==0){
			qry1(L[rt],p);
			return ;
		}
		if(sta==1){
			for(int i=0;i<n;i++) res[i]+=tsz[L[rt]][i];
			return ;
		}
		if(sta==2){
			for(int i=0;i<n;i++) res[i]+=tsz[L[rt]][i]+sz[rt][i];
			qry1(R[rt],p);
		}
	}
	void qry2(int &rt,int p){ // <=p
		if(!rt) return ;
		int sta=cmp(p,rt);
		pushdown(rt);
		if(sta==0){
			qry2(L[rt],p);
			return ;
		}
		for(int i=0;i<n;i++) res[i]+=tsz[L[rt]][i]+sz[rt][i];
		if(sta==2) qry2(R[rt],p);
	}
	void debug(int &rt){
		if(!rt) return ;
		cout<<rt<<" "<<L[rt]<<" "<<R[rt]<<"\n";
		for(int i=0;i<n;i++) cout<<sz[rt][i]<<" "<<tsz[rt][i]<<" "<<tag[rt][i]<<"  "; cout<<"\n";
		debug(L[rt]),debug(R[rt]);
	}
}
int nowed[5];
int remed[200005][5];
signed main(){
	pw[0]=1; for(int i=1;i<=1000000;i++) pw[i]=pw[i-1]*mul;
	Trie::init(),Tree::init();
	int m,ty; cin>>n>>m>>ty;
	int lsta=0;
	for(int i=0;i<n;i++){
		int len; cin>>len;
		nowed[i]=1;
		for(int j=1;j<=len;j++){
			int v; cin>>v;
			nowed[i]=Trie::add(nowed[i],v);
//			cout<<nowed[i]<<" ";
			Tree::add(root,nowed[i],i);
		}
//		Tree::debug(root);
//		cout<<"\n";
	}
	for(int i=0;i<n;i++) remed[0][i]=nowed[i];
	int q; cin>>q;
	for(int i=1;i<=q;i++){
//		Tree::debug(root);
		int tr=lsta*ty;
		int opt; cin>>opt; opt^=tr;
		if(opt==0){
			int x,c; cin>>x>>c; x^=tr,c^=tr; x--;
			nowed[x]=Trie::add(nowed[x],c);
//			cout<<x<<" "<<nowed[x]<<"\n";
			Tree::add(root,nowed[x],x);
		}
		else if(opt==1){
			int x,y,k,l,r; cin>>x>>y>>k>>l>>r; x^=tr,y^=tr,k^=tr,l^=tr,r^=tr; x--,y--;
//			cout<<remed[y][k]<<"\n";
			int ans[5]; memset(ans,0,sizeof(ans));
			memset(res,0,sizeof(res));
			aimpos=remed[k][y]; aimadd=l;
			Tree::qry1(root,-2);
			for(int i=0;i<n;i++) ans[i]-=res[i];//cout<<res[i]<<" "; cout<<"\n";
			memset(res,0,sizeof(res));
			aimpos=remed[k][y]; aimadd=r+1;
			Tree::qry1(root,-2);
			for(int i=0;i<n;i++) ans[i]+=res[i];//cout<<res[i]<<" "; cout<<"\n";
			cout<<(lsta=ans[x])<<"\n";
		}
		else if(opt==2){
			int x,y; cin>>x>>y; x^=tr,y^=tr; x--,y--;
			nowed[x]=nowed[y];
			int to[5]; for(int j=0;j<n;j++) to[j]=j; to[x]=y;
			Tree::addtrans(root,to);
		}
		else{
			int l,r; cin>>l>>r>>slen; l^=tr,r^=tr,slen^=tr;
			vector<int> vc;
			for(int i=1;i<=slen;i++){
				int v; cin>>v; v^=tr; vc.push_back(v);
			}
			vector<int> ex;
			int ans[5]; memset(ans,0,sizeof(ans));
			ex.clear(); ex.push_back(l); for(auto v:vc) ex.push_back(v); gethash(ex);
			memset(res,0,sizeof(res));
			Tree::qry1(root,-1);
			for(int i=0;i<n;i++) ans[i]-=res[i];//cout<<res[i]<<" "; cout<<"\n";
			ex.clear(); ex.push_back(r+1); for(auto v:vc) ex.push_back(v); gethash(ex);
			memset(res,0,sizeof(res));
			Tree::qry1(root,-1);
			for(int i=0;i<n;i++) ans[i]+=res[i];//cout<<res[i]<<" "; cout<<"\n";
			for(int i=0;i<n;i++) cout<<(lsta=ans[i])<<" "; cout<<"\n";
		}
		for(int j=0;j<n;j++) remed[i][j]=nowed[j];
	}
	return 0;
}

ID

11507

时间

5000ms

内存

512MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

[集训队互测 2015] ydc 的字符串

信息

1 条题解

自动搬运

以下是正文

[集训队互测 2015] ydc 的字符串

信息

还没有账户？

登录