ABC-403-E - Forbidden Prefix · znzryb

## 思路讲解

也是体验了一把学霸的感觉，一编译就本地AC，然后交上去就一次AC了。

比那个D题还要顺，只能说我的字符串哈希还是比较熟练的。

这个如果Hx里有比该前缀更小的单元，直接放弃。

```cpp
			FOR(i,0,SZ(s)-1){
				hax+=s[i]*Base[i];
				// 如果Hx里有比该前缀更小的单元，直接放弃
				if(Hx.find(hax)!=Hx.end()){
					needOp=false;
					break;
				}
			}
```

## AC代码

[https://atcoder.jp/contests/abc403/submissions/65404782](https://atcoder.jp/contests/abc403/submissions/65404782)



::: 源代码

```cpp
// Problem: E - Forbidden Prefix
// Contest: AtCoder - AtCoder Beginner Contest 403
// URL: https://atcoder.jp/contests/abc403/tasks/abc403_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(5e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;

ll N,M,K,Q,T;
set<arr> g[MAXN];
bool vis[MAXN];
ll Base[MAXN];

// 自然溢出取模

inline void solve(){
	cin>>Q;
	set<ll> Hx;
	Base[0]=1;
	FOR(i,1,MAXN/2){
		Base[i]=Base[i-1]*131;
	}
	ll ans=0;
	FOR(q,1,Q){
		ll t;string s;
		cin>>t>>s;
		// the number of strings in Y that have no element of X as a prefix
		if(t==1){
			ll hax=0;
			bool needOp=true;
			FOR(i,0,SZ(s)-1){
				hax+=s[i]*Base[i];
				// 如果Hx里有比该前缀更小的单元，直接放弃
				if(Hx.find(hax)!=Hx.end()){
					needOp=false;
					break;
				}
			}
			ll len=SZ(s);
			if(needOp){
				auto itb=g[len-1].lower_bound({hax,0});
				auto ite=g[len-1].lower_bound({hax,INF});
				for(auto it=itb;it!=ite;++it){
					ll que=(*it)[1];
					if(vis[que]) continue;
					vis[que]=true;
					--ans;
				}
				Hx.insert(hax);
			}
			cout<<ans<<"\n";
		}else{
			ll hax=0;
			bool needAdd=true;
			FOR(i,0,SZ(s)-1){
				hax+=s[i]*Base[i];
				if(Hx.find(hax)!=Hx.end()){
					needAdd=false;
					break;
				}
			}
			if(needAdd){
				++ans;
				ll hax=0;
				FOR(i,0,SZ(s)-1){
					hax+=s[i]*Base[i];
					g[i].insert({hax,q});
				}
			}
			cout<<ans<<"\n";
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/
```


:::


## 心路历程（WA，TLE，MLE……）