神秘猎奇跑不满做法爆踩 ACAM

猎奇做法。

记

(s_{i,1},s_{i,2})

或

(t_{i,1},t_{i,2})

第一个不相等位置为

l

，最后一个为

r

。

对于每一对

(s_{i,1},s_{i,2})

，将整段

s_{[1,r]}

拉出来分组（这里用哈希），剩下的部分建 Trie。

询问的时候枚举左端点

x\ (x\le l)

，问题变成在

t_{[x,r]}

对应的 Trie 上查询最大的

y

满足 Trie 上存在

t_{[r+1,y]}

。

考虑对每个 Trie 建立哈希表/map，然后直接二分即可。

复杂度

O(L\log L)

或

O(L\log^2 L)

，后者不刻意卡根本跑不满（森林中每个 Trie 没多少点）。

code

由赛场代码修改而来，跑官方数据比赛后自写的 ACAM 做法略快。

CPP

#include <bits/stdc++.h>
#define ED cerr<<'\n';
#define TS cerr<<"I AK IOI\n";
#define cr(x) cerr<<x<<'\n';
#define cr2(x,y) cerr<<x<<" "<<y<<'\n';
#define cr3(x,y,z) cerr<<x<<" "<<y<<" "<<z<<'\n';
#define cr4(x,y,z,w) cerr<<x<<" "<<y<<" "<<z<<" "<<w<<'\n';
#define pr(a,l,r) for(int iii=l;iii<=r;++iii) cerr<<a[iii]<<" ";ED
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
using namespace std;
const int N=5e6+5,M=2e5+5,mod1=998244353,mod2=1e9+7,B=13331,INF=2e9;
int T,n,m,k,idx=0,idx2=0;
bool Mst;
unordered_map<ull,int> mp[M],rt;int pp[M],mx[M];
ull g1[N],g2[N];
int tr[N][26],cnt[N];pair<ull,ull> val[N];
char s1[N],s2[N];ull v1[N],v2[N];
bool Med;

inline ull f(char x,char y) {
	return (x-'a'+1)*26+(y-'a'+1);
}

void insert(int rt,char s[],int st) {
	int u=pp[rt];
	for(int i=st;s[i];++i) {
		int to=s[i]-'a';
		if(!tr[u][to]) {
			tr[u][to]=++idx;ull qwq=f(s[i],s[i]);
			val[idx].fi=(val[u].fi*B+qwq)%mod1;
			val[idx].se=(val[u].se*B+qwq)%mod2;
			mp[rt][val[idx].fi*INF+val[idx].se]=idx;
		}
		u=tr[u][to];
	}
	++cnt[u];
}

void dfs(int u) {
	for(int i=0;i<26;++i) {
		if(tr[u][i]) {
			cnt[tr[u][i]]+=cnt[u],dfs(tr[u][i]);
		}
	}
}

void init() {
	g1[0]=g2[0]=1;
	for(int i=1;i<N;++i) {
		g1[i]=g1[i-1]*B%mod1;
		g2[i]=g2[i-1]*B%mod2;
	}
}

ull getval(int l,int r) {
	ull x1=(v1[r]-v1[l-1]*g1[r-l+1]%mod1+mod1)%mod1;
	ull x2=(v2[r]-v2[l-1]*g2[r-l+1]%mod2+mod2)%mod2;
	return x1*INF+x2;
}

int main() {
	freopen("replace.in","r",stdin);
	freopen("replace.out","w",stdout);
	init();
	scanf("%d%d",&n,&m);
	vector<int> rts;
	for(int i=1;i<=n;++i) {
		scanf("%s%s",s1+1,s2+1);
		int sz=strlen(s1+1),lst=0;
		for(int j=1;j<=sz;++j) {
			if(s1[j]!=s2[j]) lst=j;
		}
		if(!lst) continue;
		for(int j=1;j<=lst;++j) {
			v1[j]=(v1[j-1]*B+f(s1[j],s2[j]))%mod1;
			v2[j]=(v2[j-1]*B+f(s1[j],s2[j]))%mod2;
		}
		ull qwq=v1[lst]*INF+v2[lst];
		if(!rt.count(qwq)) {
			rt[qwq]=++idx2,pp[idx2]=++idx;
			rts.emplace_back(idx),mp[idx2][0]=idx;
		}
		int u=rt[qwq];
		mx[u]=max(mx[u],sz-lst),insert(u,s1,lst+1);
	}
	for(auto it:rts) dfs(it);
	for(int t=1;t<=m;++t) {
		scanf("%s%s",s1+1,s2+1);
		int sz=strlen(s1+1),fst=0,lst=0,ans=0;
		int sz2=strlen(s2+1);
		if(sz!=sz2) {
			puts("0");continue;
		}
		for(int j=1;j<=sz;++j) {
			if(s1[j]!=s2[j]) {
				if(!fst) fst=j;
				lst=j;
			}
			v1[j]=(v1[j-1]*B+f(s1[j],s2[j]))%mod1;
			v2[j]=(v2[j-1]*B+f(s1[j],s2[j]))%mod2;
		}
		for(int j=1;j<=fst;++j) {
			ull res=getval(j,lst);
			if(rt.count(res)) {
				int u=rt[res];
				int l=lst+1,r=min(lst+mx[u],sz),res=lst;
				while(l<=r) {
					int mid=l+r>>1;
					if(mp[u].count(getval(lst+1,mid))) {
						l=mid+1,res=mid;
					}
					else r=mid-1;
				}
				ull res2=getval(lst+1,res);
				ans+=cnt[mp[u][res2]];
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

神秘猎奇跑不满做法爆踩 ACAM

文章操作

code

相关推荐

评论

神秘猎奇跑不满做法爆踩 ACAM