东莞模板网站好,包装设计网站排行榜前十名,wordpress 微信 抓取,wordpress采集微信文章正题
题目链接:https://www.luogu.com.cn/problem/P2336 题目大意 nnn个名字(每个名字两个串)#xff0c;mmm次点名#xff0c;如果一次点名里是一个名字两个串中的子串该人就要答到。
对于每次点名求多少个人答到#xff0c;每个名字求答到多少次。 解题思路
先考虑第一…正题
题目链接:https://www.luogu.com.cn/problem/P2336 题目大意
nnn个名字(每个名字两个串)mmm次点名如果一次点名里是一个名字两个串中的子串该人就要答到。
对于每次点名求多少个人答到每个名字求答到多少次。 解题思路
先考虑第一问我们将所有串串在一起(中间加大数)然后跑出SASASA和所有的LCPLCPLCP。
然后对于每个点名串起始位置kkk我们寻找一个区间[l,r][l,r][l,r]使得LCP(k,i)≥len(i∈[l,r])LCP(k,i)\geq len(i\in[l,r])LCP(k,i)≥len(i∈[l,r])
这个区间我们求出heightheightheight后用STSTST表二分可以求出
这样如果任意一个名字串的在这个区间内就会被点到。因为有名有姓我们把同一个名字的SASASA染成同一种颜色这样问题就变为了在[l,r][l,r][l,r]这个区间内有多少种颜色
而第二问也变为了有多少个区间包含该种颜色我们直接用树状数组做就好了。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includevector
#define lowbit(x) (x-x)
using namespace std;
const int N5e510;
struct node{int l,r,id;
}q[N];
int n,m,num,Q,s[N];
int col[N],len[N],head[N];
int sa[N],c[N],x[N],y[N];
int rk[N],height[N];
int st[N][20],lg[N];
int pre[N],last[N],qq[N];
int ans1[N],ans2[N];
struct Tree_Array{int t[N];void Change(int x,int val){if(!x) return;while(xn){t[x]val;xlowbit(x);}return;}int Ask(int x){int ans0;while(x){anst[x];x-lowbit(x);}return ans;}
}T1,T2;
void Init(){scanf(%d%d,num,Q);m1e4;for(int i1;inum;i){for(int j0;j2;j){int x,c;scanf(%d,x);while(x--){scanf(%d,c);s[n]c;col[n]i;}s[n]m;}}for(int i1;iQ;i){int x;head[n1]i;scanf(%d,len[i]);for(int j1;jlen[i];j){scanf(%d,x);s[n]x;col[n]-i;}s[n]m;}
}
void Qsort(){for(int i1;im;i)c[i]0;for(int i1;in;i)c[x[i]];for(int i1;im;i)c[i]c[i-1];for(int in;i1;i--)sa[c[x[y[i]]]--]y[i],y[i]0;return;
}
void Get_SA(){for(int i1;in;i)x[i]s[i],y[i]i;Qsort();for(int w1;wn;w1){int p0;for(int in-w1;in;i) y[p]i;for(int i1;in;i)if(sa[i]w) y[p]sa[i]-w;Qsort();swap(x,y);x[sa[1]]p1;for(int i2;in;i)x[sa[i]](y[sa[i]]y[sa[i-1]]y[sa[i]w]y[sa[i-1]w])?p:p;if(pn) break;mp;}return;
}
void Get_Height(){int k0;for(int i1;in;i)rk[sa[i]]i;for(int i1;in;i){//if(rk[i]1) continue;if(k) k--;int jsa[rk[i]-1];while(iknjkns[ik]s[jk]) k;height[rk[i]]k;}return;
}
void Get_ST(){lg[0]-1;for(int i1;in;i)st[i][0]height[i],lg[i]lg[i1]1;for(int j1;j19;j)for(int i1;i(1j-1)n;i)st[i][j]min(st[i][j-1],st[i(1j-1)][j-1]);return;
}
int LCP(int l,int r){if(lr) return 1e97;if(lr) swap(l,r);l;int zlg[r-l1];return min(st[l][z],st[r1-(1z)][z]);
}
bool cmp(node x,node y)
{return x.ry.r;}
void Get_Pre(){for(int i1;in;i){if(col[sa[i]]0){pre[i]last[col[sa[i]]];last[col[sa[i]]]i;}if(head[i]){int l1,rrk[i];while(lr){int mid(lr)1;if(LCP(mid,rk[i])len[head[i]]) rmid-1;else lmid1;}q[head[i]].ll;lrk[i];rn;while(lr){int mid(lr)1;if(LCP(rk[i],mid)len[head[i]]) lmid1;else rmid-1;}q[head[i]].rr;q[head[i]].idhead[i];qq[q[head[i]].l];}}sort(q1,q1Q,cmp);
}
void Get_Ans(){int h1,z1;for(int i1;in;i){T2.Change(i,qq[i]);if(col[sa[i]]0){T1.Change(pre[i],-1);T1.Change(i,1);ans2[col[sa[i]]]T2.Ask(i)-T2.Ask(pre[i]);}while(hQq[h].ri){ans1[q[h].id]T1.Ask(q[h].r)-T1.Ask(q[h].l-1);T2.Change(q[h].l,-1);h;}}return;
}
int main()
{Init();Get_SA();Get_Height();Get_ST();Get_Pre();Get_Ans();for(int i1;iQ;i)printf(%d\n,ans1[i]);for(int i1;inum;i)printf(%d ,ans2[i]);
}
