JZOJ 3351.【NOI2013模拟】神牛养成计划2

题目大意

给定一些字符串,集合为S,( |S|2000 )给出m组询问 m200000
每组询问有2个串s1,s2,问在S中有几个字符串满足以下的要求:s1为之前缀,s2为之后缀。
强制在线。

题解

题目条件

①S中的字符固定
②强制在线
③要问两个集合的交集(什么是两个集合这很显然)
④s1是第一个集合里面的字符串的前缀,s2是第二个集合里面的字符串的后缀。

突破口

综合条件①④,按照S来建Trie。
根据条件④,可以得出如果S中的串有序,那么满足④中第一个条件的一定在一个区间[l1,r1]内。第二个条件同理。
综合条件②③,需要用到可持久化数据结构。

具体解法

①按照字符串排序,得到排名L1[i],R1[i]。
②正着和反着各建一棵Trie,那么Trie上的点显然可以表示选择的字符串的一个区间
③强制在线询问,那么第r棵树-第l-1棵树的值就能够表示这一边排名为[l,r]的另外一边的排名的个数。

心得

①在打码农题之前,一定先写好框架,然后再打程序。
②原始快排中,mid是个定值,不能更改,在qsort中的主循环中也如此。
③主席树等数据结构码速有待提高。
总的来说,打这题花的时间很多,但是调这题用时很少,不错。
听说还有字符串哈希解法(想到这个那么做起来更显然了,时间复杂度乍一看 O(nlog2n) )。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define N 2000010
#define M 2010
#define P(a) putchar(a)
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
struct note{
    int ls,rs,sum;
};note tr[N];
int i,j,k,k1,la,n,m,x,ans,g1,g2;
int tot,trie[N][26];
int tot1,trie1[N][26];
char ch,s[N],s1[N],s2[N];
int L[M],R[M],len[M],L1[M],R1[M],ol[M];
int bz[N],pre[N],o[N],o1[N];
int l1[N],r1[N],l2[N],r2[N];
int LL1,LL2,RR1,RR2;
int root[N],gs;
bool ia;
queue<int>qu;
int read(){
    int fh=1,res=0;char ch;
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
void write(int x){if(x>9)write(x/10);P(x%10+'0');}
void mi(int &x,int y){x=x<y?x:y;}
void ma(int &x,int y){x=x>y?x:y;}
int cl(int l1,int l2){
    l1=L1[l1];
    int i,l=len[l1]<len[l2]?len[l1]:len[l2];
    fo(i,1,l)
        if(s[L[l1]+i-1]>s[L[l2]+i-1])return 2;else
        if(s[L[l1]+i-1]<s[L[l2]+i-1])return 1;
    if(len[l1]>len[l2])return 2;
    if(len[l1]<len[l2])return 1;
    return 0;
}
int cr(int l1,int l2){
    l1=R1[l1];
    int i,l=len[l1]<len[l2]?len[l1]:len[l2];
    fo(i,1,l)
        if(s[R[l1]-i+1]>s[R[l2]-i+1])return 2;else
        if(s[R[l1]-i+1]<s[R[l2]-i+1])return 1;
    if(len[l1]>len[l2])return 2;
    if(len[l1]<len[l2])return 1;
    return 0;
}
void ql(int l,int r){
    int i=l,j=r,mid=L1[(l+r)/2];
    while(i<j){
        while(cl(i,mid)==1)i++;
        while(cl(j,mid)==2)j--;
        if(i<=j)swap(L1[i],L1[j]),i++,j--;
    }
    if(l<j)ql(l,j);
    if(i<r)ql(i,r);
}
void qr(int l,int r){
    int i=l,j=r,mid=R1[(l+r)/2];
    while(i<j){
        while(cr(i,mid)==1)i++;
        while(cr(j,mid)==2)j--;
        if(i<=j)swap(R1[i],R1[j]),i++,j--;
    }
    if(l<j)qr(l,j);
    if(i<r)qr(i,r);
}
void update(int ps){tr[ps].sum=tr[tr[ps].ls].sum+tr[tr[ps].rs].sum;}
void ins(int &px,int py,int l,int r,int x){
    px=++gs;
    tr[px]=tr[py];tr[px].sum=0;
    if(l==r){
        tr[px].sum++;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)ins(tr[px].ls,tr[py].ls,l,mid,x);
         else ins(tr[px].rs,tr[py].rs,mid+1,r,x);
    update(px);
}
void query(int px,int py,int l,int r,int _l,int _r){
    if(!px && !py)return;
    if(l==_l && r==_r){
        ans+=tr[px].sum-tr[py].sum;
        return;
    }
    int mid=(l+r)>>1;
    if(_r<=mid)query(tr[px].ls,tr[py].ls,l,mid,_l,_r);else
    if(_l>mid)query(tr[px].rs,tr[py].rs,mid+1,r,_l,_r);else{
        query(tr[px].ls,tr[py].ls,l,mid,_l,mid);
        query(tr[px].rs,tr[py].rs,mid+1,r,mid+1,_r);
    }
}
int main(){
    n=read();
    fo(i,1,n){
        L[i]=R[i]=R[i-1]+1;R[i]--;
        ch=getchar();
        while(ch<'a'||ch>'z')ch=getchar();
        while(ch>='a'&&ch<='z')s[++R[i]]=ch,ch=getchar();
        len[i]=R[i]-L[i]+1;
        L1[i]=R1[i]=i; 
    }
    ql(1,n);
    qr(1,n);
    tot=0;
    fo(i,1,n){
        k=0;
        fo(j,1,len[L1[i]]){
            x=s[L[L1[i]]+j-1]-'a';
            if(trie[k][x])k=trie[k][x];
            else{
                trie[k][x]=++tot;
                pre[tot]=k;
                o[k]++;
                k=tot;
            }
            if(j==len[L1[i]])bz[i]=k;
        }
    }
    memset(l1,127,sizeof(l1));
    fo(i,1,n)qu.push(bz[i]),l1[bz[i]]=r1[bz[i]]=i;
    while(!qu.empty()){
        x=qu.front();qu.pop();
        mi(l1[pre[x]],l1[x]);
        ma(r1[pre[x]],r1[x]);
        o[pre[x]]--;
        if(!o[pre[x]])qu.push(pre[x]);
    }
    fo(i,1,n)ol[R1[i]]=i;
    fo(i,1,n)o1[i]=ol[L1[i]];
    fo(i,1,n)
        ins(root[i],root[i-1],1,n,o1[i]);
    memset(pre,0,sizeof(pre));
    memset(bz,0,sizeof(bz));
    tot=0;
    fo(i,1,n){
        k=0;
        fo(j,1,len[R1[i]]){
            x=s[R[R1[i]]-j+1]-'a';
            if(trie1[k][x])k=trie1[k][x];
            else{
                trie1[k][x]=++tot;
                pre[tot]=k;
                o[k]++;
                k=tot;
            }
            if(j==len[R1[i]])bz[i]=k;
        }
    }
    memset(l2,127,sizeof(l2));
    fo(i,1,n)qu.push(bz[i]),l2[bz[i]]=r2[bz[i]]=i;
    while(!qu.empty()){
        x=qu.front();qu.pop();
        mi(l2[pre[x]],l2[x]);
        ma(r2[pre[x]],r2[x]);
        o[pre[x]]--;
        if(!o[pre[x]])qu.push(pre[x]);
    }
    m=read();la=0;
    while(m--){
        g1=g2=0;
        ch=getchar();
        while(ch<'a'||ch>'z')ch=getchar();
        while(ch>='a'&&ch<='z')s1[++g1]=ch,ch=getchar();
        ch=getchar();
        while(ch<'a'||ch>'z')ch=getchar();
        while(ch>='a'&&ch<='z')s2[++g2]=ch,ch=getchar();
        ia=0;k=0;
        fo(i,1,g1){
            x=(s1[i]-'a'+la)%26;
            if(trie[k][x])k=trie[k][x];else{
                ia=1;
                break;
            }
        }
        LL1=l1[k];RR1=r1[k];
        if(!ia){k1=0;
        fo(i,1,g2){
            x=(s2[g2-i+1]-'a'+la)%26;
            if(trie1[k1][x])k1=trie1[k1][x];else{
                ia=1;
                break;
            }
        }}
        if(ia==1){write(0);P('\n');la=0;continue;}
        LL2=l2[k1];RR2=r2[k1];
        ans=0;
        query(root[RR1],root[LL1-1],1,n,LL2,RR2);
        write(ans);P('\n');
        la=ans;
    }
    return 0;
}
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院