2016年2月27日 星期六

[COCI 2014/2015 contest #5]DIVLJAK

這題目不好找,附上題目連結

簡單來說,就是給你一個固定的字串集合$A$和不固定的字串集合$B$
操作$1$就是把一個字串加入$B$
操作$2$就是給你$i$,問你$A_{i}$是$B$中幾個$B_{k}$的子字串

首先,我們可以把$A$建成一個$AC$自動機
這樣當$B$加入一個新字串之後,就可以馬上和$A$進行匹配,找出$A$中哪幾個是這個新字串的子字串了

當然,不能直接沿著失配函數$fail$ (也有人稱作$next$) 直接更新$A$中每個$A_{i}$的計數器
我們必須想到一個巧妙的方法,讓所有被匹配到的$A_{i}$和其沿著$fail$往上的所有$A_{k}$一起被加$1$ (因為$A_{i}$匹配意味著其沿著$fail$往上的所有$A_{k}$也會匹配成功)

可以發現,如果將所有的$u\rightarrow fail[u]$邊反向成$fail[u]\rightarrow u$,然後建圖
我們會得到一棵根為$0$的樹 (稱作$fail\ tree$好了)
而上述操作就是將一堆節點和它們的祖先們全部加$1$

利用線段樹維護樹壓平的序列,就可以實現$O(\log N)$查詢某個節點的值、$O(\log N)$一次將某個節點和其所有的祖先們加$1$了
(方法是查尋的時候直接查詢整棵子樹加$1$的總次數,修改只需單點修改即可)

可是這樣有可能會造成某個祖先被多次加$1$的情況
可以發現,當某個節點被加$1$第二次,那麼這個節點的祖先們也都會被這個多加的$1$影響到
那就把多加的扣回來就好啦

我們可以將這一堆要讓自己和祖先們都加$1$的節點依照$fail\ tree$的$dfs$順序排序
假設排序完的序列是$\{v_{1},v_{2},v_{3},...,v_{n}\}$
對於每個$1\leq i\leq n$,將所有$v_{i}$及其祖先們都加$1$
對於每個$2\leq i\leq n$,將所有$LCA(v_{i-1},v_{i})$ ($Lowest\ Common\ Ancestor$) 及其祖先們都減$1$
這樣就剛好讓每個被影響到的點都恰好加$1$了

($\left|A\right|$代表集合$A$裡面所有的字串長度總和)
在$B$中加入一個字串$s$的複雜度:$O(\left|s\right|\log\left|A\right|)$
查詢的時間複雜度:$O(\log\left|A\right|)$

p.s.這個code沒有特別優化,在自己的電腦實測是$8$秒 (如下圖),而時限是$4$秒
2016/2/27 15:54更新:後來找到judge可以傳了,這份code不意外地獲得了TLE,優化後的code在這裡


時間複雜度:$O(Q\log\left|A\right|+\left|B_{final}\right|\log\left|A\right|)$

code:
#include<cstdio>
#include<cassert>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<ctime>
using namespace std;
struct SegTree
{
    int n;
    vector<int>sum;
    void Build(const int id,const int l,const int r)
    {
        while(id>=(int)sum.size())sum.push_back(0);
        sum[id]=0;
        if(l<r)
        {
            const int mid=(l+r)/2;
            Build(id*2,l,mid),Build(id*2+1,mid+1,r);
        }
    }
    void Build(const int _n){n=_n;Build(1,0,n-1);}
    void Modify(const int id,const int l,const int r,const int loc,const int val)
    {
        sum[id]+=val;
        if(l<r)
        {
            const int mid=(l+r)/2;
            if(loc<=mid)Modify(id*2,l,mid,loc,val);
            else Modify(id*2+1,mid+1,r,loc,val);
        }
    }
    void Modify(const int loc,const int val){Modify(1,0,n-1,loc,val);}
    int Query(const int id,const int l,const int r,const int bl,const int br)
    {
        if(r<bl||br<l)return 0;
        if(bl<=l&&r<=br)return sum[id];
        const int mid=(l+r)/2;
        return Query(id*2,l,mid,bl,br)+Query(id*2+1,mid+1,r,bl,br);
    }
    int Query(const pair<int,int>&p){return Query(1,0,n-1,p.first,p.second);}
};
struct TreeSequence
{
    vector<vector<int> >et,parents;
    vector<pair<int,int> >segs;
    vector<int>deps;
    void Clear(const int n)
    {
        et.clear(),segs.clear(),parents.clear(),deps.clear();
        et.resize(n),segs.resize(n),parents.resize(n),deps.resize(n);
    }
    void Build(const int u,const int parent,const int dep,int &clock)
    {
        deps[u]=dep;
        parents[u].clear();
        if(parent!=-1)
        {
            for(int cur=parent,i=0;;cur=parents[cur][i++])
            {
                parents[u].push_back(cur);
                if(i>=(int)parents[cur].size())break;
            }
        }
        segs[u].first=clock;
        for(const int nxt:et[u])Build(nxt,u,dep+1,clock);
        segs[u].second=clock++;
    }
    int LowestCommonAncestor(int a,int b)
    {
        if(deps[a]<deps[b])swap(a,b);
        for(int i=30,dis=deps[a]-deps[b];i>=0;i--)if(dis&(1<<i))a=parents[a][i];
        assert(deps[a]==deps[b]);
        if(a==b)return a;
        for(int i=30;i>=0;i--)if((1<<i)<=deps[a]&&parents[a][i]!=parents[b][i])a=parents[a][i],b=parents[b][i];
        assert(parents[a][0]==parents[b][0]);
        return parents[a][0];
    }
    const pair<int,int>&operator[](const int i)const{return segs[i];}
};
struct AC_Automaton
{
    int sz;
    vector<map<char,int> >ch;
    vector<bool>is_end;
    void Clear(){sz=0;ch.clear(),is_end.clear();Expand();}
    void Expand(){ch.push_back(map<char,int>()),is_end.push_back(false);sz++;}
    int GetNxt(const int u,const char c)
    {
        const auto &it=ch[u].find(c);
        if(it==ch[u].end()){Expand();return ch[u][c]=sz-1;}
        else return it->second;
    }
    int Insert(const char *str)
    {
        int u=0;
        for(int i=0;str[i];i++)u=GetNxt(u,str[i]);
        is_end[u]=true;
        return u;
    }
    vector<int>fail;
    void BuildFail()
    {
        fail.clear(),fail.resize(sz,0);
        queue<int>q;
        for(const auto &it:ch[0])q.push(it.second);
        while(!q.empty())
        {
            const int u=q.front();q.pop();
            for(const auto &it:ch[u])
            {
                int &f=fail[it.second]=fail[u];
                while(f&&ch[f].find(it.first)==ch[f].end())f=fail[f];
                if(true)
                {
                    const auto &iu=ch[f].find(it.first);
                    if(iu!=ch[f].end())f=iu->second;
                }
                if(is_end[f])is_end[it.second]=true;
                q.push(it.second);
            }
        }
    }
    TreeSequence seq;
    SegTree seg_tree;
    void BuildFailTree()
    {
        seq.Clear(sz);
        for(int i=1;i<sz;i++)seq.et[fail[i]].push_back(i);
        int clock=0;
        seq.Build(0,-1,0,clock);
        assert(clock==sz);
        seg_tree.Build(sz);
    }
    void Match(const char *str)
    {
//        static int kase=0;kase++;
        int u=0;
        vector<int>nodes;
        for(int i=0;str[i];i++)
        {
            while(u&&ch[u].find(str[i])==ch[u].end())u=fail[u];
            const auto it=ch[u].find(str[i]);
            if(it!=ch[u].end())u=it->second;
            if(is_end[u])nodes.push_back(u);
        }
        if(nodes.empty())return;
        sort(nodes.begin(),nodes.end(),[this](const int a,const int b)->bool{return seq[a].second<seq[b].second;});
        seg_tree.Modify(seq[nodes[0]].second,1);
        for(int i=1;i<(int)nodes.size();i++)
        {
            seg_tree.Modify(seq[nodes[i]].second,1);
            seg_tree.Modify(seq[seq.LowestCommonAncestor(nodes[i-1],nodes[i])].second,-1);
        }
    }
    int Query(const int u){return seg_tree.Query(seq[u]);}
}AC;
int N;
int main()
{
    freopen("inn.txt","r",stdin);
    freopen("out.txt","w",stdout);
//    clock_t start_time;
    while(scanf("%d",&N)==1)
    {
//        start_time=clock();
        AC.Clear();
        vector<int>nodes;
        for(int i=0;i<N;i++)
        {
            static char str[2000001];
            scanf("%s",str);
            nodes.push_back(AC.Insert(str));
        }
        AC.BuildFail();
        AC.BuildFailTree();
        int querycount;scanf("%d",&querycount);
        for(int type,val;querycount--;)
        {
            scanf("%d",&type);
            if(type==1)
            {
                static char str[2000001];
                scanf("%s",str);
                AC.Match(str);
            }
            else if(type==2)
            {
                scanf("%d",&val);
                printf("%d\n",AC.Query(nodes[--val]));
            }
            else assert(0);
        }
//        printf("run time = %.3f s.\n",(double)(clock()-start_time)/CLOCKS_PER_SEC);
    }
    return 0;
}

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原