洛咕 P2336 [SCOI2012]喵星球上的点名
先求出SA和height，一个点名串对应的就是一段区间，还有很多个点，就转化成了
有很多个区间，很多个点集，对每个区间计算和多少个点集有交，对每个点集计算和多少个区间有交。
第一个，HH的项链的树状数组做法
第二个，因为是点集所以要去重，假设点集有\(a_1,a_2,\cdots,a_k\)，可以对每个区间只再覆盖的第一个点做记录
就是记录\(\sum_{i=1}^k\sum_{\texttt{interval }[l,r]}\left[l\in[a_{i-1}+1,a_i],r\geq a_i\right]\)
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
std::vector<int>A[100010],B[100010],C[100010],S,P;
int len,x[400010],y[400010],t[400010],SA[400010],rk[400010];
int ht[400010];
il bool cmp(int a,int b,int k){return y[a]==y[b]&&y[a+k]==y[b+k];}
int ans1[100010],ans2[100010];
int lg[400010],st[19][400010];
il int query(int l,int r){
int g=lg[r-l+1];
return std::min(st[g][l],st[g][r-(1<<g)+1]);
}
std::vector<int>ins[400010],del[400010],p_del[400010];
int Tree[400010],Tree2[400010],lst[400010],LL[400010],RR[400010];
il vd update(int*t,int p,int x){while(p<=len)t[p]+=x,p+=p&-p;}
il int query(int*t,int r){int ret=0;while(r)ret+=t[r],r-=r&-r;return ret;}
int main(){
int n=gi(),m=gi();
for(int i=1;i<=n;++i){
len=gi();
while(len--)A[i].push_back(gi()+200000);
len=gi();
while(len--)B[i].push_back(gi()+200000);
}
for(int i=1;i<=m;++i){
len=gi();
while(len--)C[i].push_back(gi()+200000);
}
S.push_back(233333);
P.push_back(0);
int sep=0;
for(int i=1;i<=n;++i){
S.insert(S.end(),A[i].begin(),A[i].end());
S.push_back(++sep);
for(int j=0;j<A[i].size();++j)P.push_back(i);
P.push_back(0);
}
for(int i=1;i<=n;++i){
S.insert(S.end(),B[i].begin(),B[i].end());
S.push_back(++sep);
for(int j=0;j<B[i].size();++j)P.push_back(i);
P.push_back(0);
}
for(int i=1;i<=m;++i){
S.insert(S.end(),C[i].begin(),C[i].end());
S.push_back(++sep);
P.push_back(-i);
for(int j=0;j<C[i].size();++j)P.push_back(0);
}
len=S.size()-1;
int tot=400000;
for(int i=1;i<=len;++i)++t[x[i]=S[i]];
for(int i=1;i<=tot;++i)t[i]+=t[i-1];
for(int i=len;i;--i)SA[t[x[i]]--]=i;
for(int k=1;k<=len;k<<=1){
int p=0;
for(int i=0;i<=tot;++i)y[i]=0;
for(int i=len-k+1;i<=len;++i)y[++p]=i;
for(int i=1;i<=len;++i)if(SA[i]>k)y[++p]=SA[i]-k;
for(int i=0;i<=tot;++i)t[i]=0;
for(int i=1;i<=len;++i)++t[x[y[i]]];
for(int i=1;i<=tot;++i)t[i]+=t[i-1];
for(int i=len;i;--i)SA[t[x[y[i]]]--]=y[i];
std::swap(x,y),x[SA[1]]=p=1;
for(int i=2;i<=len;++i)x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;
if(p>=len)break;tot=p;
}
for(int i=1;i<=len;++i)rk[SA[i]]=i;
int k=0;
for(int i=1;i<=len;++i){
if(rk[i]==len)continue;
if(k)--k;
int j=SA[rk[i]+1];
while(S[i+k]==S[j+k])++k;
ht[rk[i]]=k;
}
for(int i=2;i<=len;++i)lg[i]=lg[i>>1]+1;
for(int i=1;i<len;++i)st[0][i]=ht[i];
for(int i=1;i<=lg[len];++i)
for(int j=1;j+(1<<i)-1<len;++j)
st[i][j]=std::min(st[i-1][j],st[i-1][j+(1<<i-1)]);
for(int i=1;i<=len;++i)
if(P[SA[i]]<0){
int l=1,r=i,mid,sz=C[-P[SA[i]]].size();
while(l<r){
mid=(l+r)>>1;
if(query(mid,i-1)<sz)l=mid+1;
else r=mid;
}
int L=l;
ins[l].push_back(L);
LL[-P[SA[i]]]=l;
l=i,r=len;
while(l<r){
mid=(l+r)>>1;
if(query(i,mid)>=sz)l=mid+1;
else r=mid;
}
del[l+1].push_back(L);
p_del[l+1].push_back(-P[SA[i]]);
RR[-P[SA[i]]]=l;
}
for(int i=1;i<=len;++i){
if(P[SA[i]]>0){
update(Tree2,i,1);
if(lst[P[SA[i]]])update(Tree2,lst[P[SA[i]]],-1);
}
for(int j=0;j<ins[i].size();++j)update(Tree,ins[i][j],1);
for(int j=0;j<del[i].size();++j)update(Tree,del[i][j],-1);
if(P[SA[i]]>0){
ans1[P[SA[i]]]+=query(Tree,i)-query(Tree,lst[P[SA[i]]]);
lst[P[SA[i]]]=i;
}
for(int j=0;j<del[i+1].size();++j)ans2[p_del[i+1][j]]=query(Tree2,RR[p_del[i+1][j]])-query(Tree2,LL[p_del[i+1][j]]-1);
}
for(int i=1;i<=m;++i)printf("%d\n",ans2[i]);
for(int i=1;i<=n;++i)printf("%d ",ans1[i]);
puts("");
return 0;
}