首页 > 代码库 > BZOJ 3881: [Coci2015]Divljak

BZOJ 3881: [Coci2015]Divljak

Description

有两个集合\(ST\),\(S\)集合已知。
有两个操作
添加一个字符串到\(T\)
询问T中有多少\(S_i\)

\(n,q\leqslant 10^5,len(|S|),len(|T|)\leqslant 2\times 10^5\)

Solution

Trie树+DFS序.

添加一个字符串就要把Trie树上经过的节点及其fail树上的祖先+1
将他差分一下,每次询问出现次数就变成了询问子树和。
然后就是几条树梿的+1操作,因为差分过了,所以每个节点+1,相邻LCA-1

Code

/**************************************************************    Problem: 3881    User: BeiYu    Language: C++    Result: Accepted    Time:16216 ms    Memory:514652 kb****************************************************************/ #include <bits/stdc++.h>using namespace std; const int N = 2000050;const int M = 26; namespace Bit {    int d[N],n;         void init(int x) { n=x; }    void Add(int x,int v) { for(;x<=n;x+=x&-x) d[x]+=v; }    int Qur(int x,int r=0) { for(;x;x-=x&-x) r+=d[x];return r; }} namespace Tree {    vector<int> g[N];    int cnt;    int b[N],f[N][M],d[N],t1[N],t2[N];         void AddEdge(int u,int v) { g[u].push_back(v),g[v].push_back(u); }    void DFS(int rt) {        stack<int> stk;        stk.push(rt),f[rt][0]=rt,d[rt]=1;        for(int x;!stk.empty();) {            x=stk.top();            if(b[x]) { t2[x]=cnt,stk.pop();continue; }            b[x]=1,t1[x]=++cnt;            for(int i=0,v;i<(int)g[x].size();i++)                 if((v=g[x][i])!=f[x][0]) f[v][0]=x,d[v]=d[x]+1,stk.push(v);        }    }    void init() {        for(int j=1;j<M;j++) for(int i=1;i<=cnt;i++)            f[i][j]=f[f[i][j-1]][j-1];    }    int LCA(int u,int v) {        if(d[u]<d[v]) swap(u,v);        int l=d[u]-d[v];        if(l) for(int i=M-1;~i;i--) if(l&(1<<i)) u=f[u][i];        if(u==v) return u;        for(int i=M-1;~i;--i) if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];        return f[u][0];    }};  namespace AC {    int cnt,rt;    int f[N],ch[N][M],ed[N];         void init() { rt=cnt=0; }    void insert(char* s,int id) {        int l=strlen(s),x=rt;        for(int i=0;i<l;i++) {            int v=s[i]-‘a‘;            if(!ch[x][v]) ch[x][v]=++cnt;            x=ch[x][v];        }ed[id]=x;    }    void Build() {        queue<int> q;        f[rt]=rt;        for(int i=0;i<M;i++) if(ch[rt][i]) q.push(ch[rt][i]),f[ch[rt][i]]=rt;        for(int x;!q.empty();) {            x=q.front(),q.pop();            for(int i=0;i<M;i++) {                if(!ch[x][i]) { ch[x][i]=ch[f[x]][i];continue; }                int v=ch[x][i];                f[v]=ch[f[x]][i],q.push(v);            }        }    }    void get_f() {        for(int i=1;i<=cnt;i++) Tree::AddEdge(i,f[i]);        Tree::DFS(0);        Tree::init();         //      for(int i=1;i<=cnt;i++) cout<<i<<" "<<f[i]<<endl;//      for(int i=1;i<=cnt;i++) cout<<Tree::d[i]<<" ";cout<<endl;//      for(int i=1;i<=cnt;i++) cout<<Tree::t1[i]<<" ";cout<<endl;//      for(int i=1;i<=cnt;i++) cout<<Tree::t2[i]<<" ";cout<<endl;    }}; int cmp(int x,int y) { return Tree::t1[x]<Tree::t1[y]; }vector<int> a;void add_str(char* s) {    int l=strlen(s),x=AC::rt;    a.clear();    for(int i=0;i<l;i++) {        int v=s[i]-‘a‘;        x=AC::ch[x][v];        a.push_back(x);    }    sort(a.begin(),a.end(),cmp);    x=a.size();//  for(int i=0;i<x;i++) cout<<a[i]<<" ";cout<<endl;    Bit::Add(Tree::t1[a[0]],1);    for(int i=1;i<x;i++) {        Bit::Add(Tree::t1[Tree::LCA(a[i],a[i-1])],-1);        Bit::Add(Tree::t1[a[i]],1);    }} int n,q;char s[N]; int main() {//  freopen("in.in","r",stdin);    scanf("%d",&n);    AC::init();    for(int i=1;i<=n;i++) {        scanf("%s",s);        AC::insert(s,i);    }    AC::Build();    AC::get_f();    Bit::init(AC::cnt+1);//  int oo,ooo;//  while(cin>>oo>>ooo) cout<<Tree::LCA(oo,ooo)<<endl;    scanf("%d",&q);    for(int opt,x;q--;) {        scanf("%d",&opt);        if(opt==1) {            scanf("%s",s);            add_str(s);        } else {            scanf("%d",&x);            printf("%d\n",Bit::Qur(Tree::t2[AC::ed[x]])-Bit::Qur(Tree::t1[AC::ed[x]]-1));        }    }return 0;}

  

BZOJ 3881: [Coci2015]Divljak