外贸网站架构,上海企业网络营销推广服务,深圳前500强企业名单,做旅游网站当地人服务赚钱吗正题
题目链接:https://www.luogu.com.cn/problem/CF587F 题目大意
给出nnn个字符串sss。qqq次询问给出l,r,kl,r,kl,r,k要求输出sl..rs_{l..r}sl..r在sks_ksk中出现了多少次。 1≤n,q,∑∣si∣≤1051\leq n,q,\sum |s_i|\leq 10^51≤n,q,∑∣si∣≤105 解题思路
考虑一…正题
题目链接:https://www.luogu.com.cn/problem/CF587F 题目大意
给出nnn个字符串sss。qqq次询问给出l,r,kl,r,kl,r,k要求输出sl..rs_{l..r}sl..r在sks_ksk中出现了多少次。
1≤n,q,∑∣si∣≤1051\leq n,q,\sum |s_i|\leq 10^51≤n,q,∑∣si∣≤105 解题思路
考虑一个比较暴力的做法先把所有的构出一棵ACACAC自动机一个串SSS有后缀TTT当且仅当在failfailfail树上SSS的节点在TTT的子树内。
所以暴力的做法就是统计sks_ksk的节点有多少在sl..rs_{l..r}sl..r的终止节点子树内的节点。
需要优化因为有L∑∣si∣≤105L\sum |s_i|\leq 10^5L∑∣si∣≤105所以可以考虑根号分治设定值TLT\sqrt{L}TL。
对于长度大于TTT的kkk我们所有的询问统一差分变为前缀问题处理。因为这样的串的个数不会超过L\sqrt LL个所以可以每次暴力O(n)O(n)O(n)处理。
我们把所有sks_ksk路径上的节点权值加一然后暴力扫描nnn个串每次终止节点统计子树内的权值和。
对于长度小于等于TTT的kkk我们差分后按照询问端点排序从左到右扫过nnn个串每次子树内的权值加一然后每次暴力扫描sks_ksk的所有节点统计权值就好了。 使用树状数组时间复杂度O(nnlogn)O(n\sqrt n\log n)O(nnlogn)已经可以通过本题了。但是如果把树状数组改成分块就可以平衡到O(nn)O(n\sqrt n)O(nn)但是我懒 code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includequeue
#includecmath
#define ll long long
#define mp(x,y) make_pair(x,y)
#define lowbit(x) (x-x)
using namespace std;
const ll N1e510;
struct node{ll to,next;
}a[N];
ll n,m,T,tot,dfr,L,top[N],ls[N],l[N],t[N],ans[N];
ll cnt,ch[N][26],fail[N],pos[N],rfn[N],ed[N];
vectorpairll,ll v[N],V[N];
char *s[N],st[N];queuell q;
void Change(ll x,ll val){while(xdfr){t[x]val;xlowbit(x);}return;
}
ll Ask(ll x){ll ans0;while(x){anst[x];x-lowbit(x);}return ans;
}
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
ll Insert(char *s,ll l){ll x0;for(ll i0;il;i){ll cs[i]-a;if(!ch[x][c])ch[x][c]cnt;xch[x][c];}return x;
}
void GetFail(){for(ll i0;i26;i)if(ch[0][i])q.push(ch[0][i]);while(!q.empty()){ll xq.front();q.pop();for(ll i0;i26;i){if(!ch[x][i])ch[x][i]ch[fail[x]][i];else{fail[ch[x][i]]ch[fail[x]][i];q.push(ch[x][i]);}}}for(ll i1;icnt;i)addl(fail[i],i);return;
}
void dfs(ll x,ll fa){rfn[x]dfr;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x);}ed[x]dfr;return;
}
signed main()
{scanf(%lld%lld,n,m);for(ll i1;in;i){s[i]sttop[i];scanf(%s,s[i]);l[i]strlen(s[i]);top[i1]top[i]l[i];pos[i]Insert(s[i],l[i]);}Ltop[n1];Tsqrt(L);GetFail();dfs(0,0);for(ll i1;im;i){ll L,R,K;scanf(%lld%lld%lld,L,R,K);if(l[K]T)v[R].push_back(mp(K,i)),v[L-1].push_back(mp(K,-i));else V[K].push_back(mp(R,i)),V[K].push_back(mp(L-1,-i));}for(ll p1;pn;p)if(l[p]T){memset(t,0,sizeof(t));sort(V[p].begin(),V[p].end());ll x0;for(ll i0;il[p];i){xch[x][s[p][i]-a];Change(rfn[x],1);}ll z0,sum0;while(zV[p].size()!V[p][z].first)z;for(ll i1;in;i){sumAsk(ed[pos[i]])-Ask(rfn[pos[i]]-1);while(zV[p].size()V[p][z].firsti){ll idV[p][z].second,op1;if(id0)id-id,op-op;ans[id]sum*op;z;}}}memset(t,0,sizeof(t));for(ll p1;pn;p){Change(rfn[pos[p]],1);Change(ed[pos[p]]1,-1);for(ll i0;iv[p].size();i){ll kv[p][i].first,idv[p][i].second,op1;if(id0)id-id,op-op;ll x0;for(ll j0;jl[k];j){xch[x][s[k][j]-a];ans[id]op*Ask(rfn[x]);}}}for(ll i1;im;i)printf(%lld\n,ans[i]);return 0;
}
