题解：AT_abc403_e [ABC403E] Forbidden Prefix
aulive
·
·
题解
省流：学 DS 学傻了。
题意
有 m 次操作。\
每次往集合 A 或集合 B 中加入一个字符串 S。\
每次插入完后查询 B 中没有 A 中元素作为前缀的字符串数。
## solution
看到前缀匹配，不难想到字典树。\
先离线下来建出字典树。\
如果插入到集合 $B$ 中，就是树上单点加。\
如果插入到集合 $A$ 中，就是给子树标号，也就是这一子树以后的值一直都只能为 $0$。\
直接把字典树拍到 DFS 序上维护子树信息即可。
## code
```cpp
#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {//我向众神祈祷，回应我的只有心跳
#define IOsiz 100000
char ibuf[IOsiz], obuf[IOsiz], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOsiz,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOsiz)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
inline void print(char x) { putchar(x); }
inline void print(char *x) { while (*x) putchar(*x++); }
inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
inline void print(bool b) { putchar(b+48); }
template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
#define int long long
const int maxn=1e6;
struct node{
int ch[26];
}trie[maxn+5];
int q,pos[maxn+5];
int op[maxn+5],rt,tot,dfn[maxn+5],siz[maxn+5],idx;
string s[maxn+5];
void insert(string &s,int id){
int now=1;
for(int i=0;i<s.size();i++){
int c=s[i]-'a';
int &v=trie[now].ch[c];
if(!v)v=++tot;
now=v;
}
pos[id]=now;
}
void dfs(int now){
siz[now]=1;
dfn[now]=++idx;
for(int i=0;i<26;i++){
int to=trie[now].ch[i];
if(!to)continue;
dfs(to);
siz[now]+=siz[to];
}
}
struct segmenttree{
struct node{
int lef,rig,tag,sum;
}tree[maxn<<2|1];
void pushup(int now){
tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
if(tree[now].tag)tree[now].sum=0;
}
void build(int now,int lef,int rig){
tree[now].lef=lef,tree[now].rig=rig;
if(lef==rig)return;
int mid=lef+rig>>1;
build(now<<1,lef,mid);
build(now<<1|1,mid+1,rig);
pushup(now);
}
void modify(int now,int lef,int rig){
if(lef<=tree[now].lef&&tree[now].rig<=rig)return tree[now].tag=1,tree[now].sum=0,void();
int mid=tree[now].lef+tree[now].rig>>1;
if(lef<=mid)modify(now<<1,lef,rig);
if(mid<rig)modify(now<<1|1,lef,rig);
pushup(now);
}
void update(int now,int to){//注意可能有重复的串
if(tree[now].tag)return;
if(tree[now].lef==tree[now].rig)return tree[now].sum=(tree[now].tag?0:tree[now].sum+1),void();
int mid=tree[now].lef+tree[now].rig>>1;
if(to<=mid)update(now<<1,to);
else update(now<<1|1,to);
pushup(now);
}
}tr;
signed main(){
rt=tot=1;
cin>>q;
for(int i=1;i<=q;i++)cin>>op[i]>>s[i],insert(s[i],i);
dfs(rt);
tr.build(1,1,idx);
for(int i=1;i<=q;i++){
int x=pos[i];
if(op[i]==1){
tr.modify(1,dfn[x],dfn[x]+siz[x]-1);
}else{
tr.update(1,dfn[x]);
}
cout<<tr.tree[1].sum<<"\n";
}
return 0;
}
```