LP2336 [SCOI2012] 喵星球上的点名 [SA/树状数组]
Problem
https://www.luogu.org/problemnew/show/P2336
Solution
考虑排序好的询问串左右两边能到达的最远的子串,每个串的 lcp 等于串的长度。
转化为区间问题,一个区间里有多少类数,和一类数被多少个区间包括。
第一问为 HH 的项链,可树状数组处理。
第二问可以不重复的讨论 i 与 lst_i+ 1 之间有多少个 L 到 R 区间包括了 i,同样用树状数组讨论。
代码很丑...
Code
// Code by ajcxsu
// Problem: name on miao star
#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void gn (T &x) {
char ch=getchar(); x=0;
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}
const int N=4e5+10;
int idx=N>>1;
int x[N], y[N], sa[N], c[N];
int fa[N], xl[N], xr[N], col[N], hei[N], rc[N], pos[N], id[N], lst[N], length[N];
typedef pair<int, int> mpair;
vector<mpair> l[N], r[N];
vector<int> qu[N];
int Find(int x) { return fa[x]?fa[x]=Find(fa[x]):x; }
int Union(int a, int b) {
int af=Find(a), bf=Find(b);
fa[af]=bf; xr[bf]=max(xr[bf], xr[af]), xl[bf]=min(xl[bf], xl[af]); return bf;
}
bool cmp(const int &a, const int &b) { return hei[a]>hei[b]; }
int s[N], a1[N], a2[N];
int n, m, len;
void gsa() {
int n=len, m=N-1;
for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=1;i<=n;i++) sa[c[x[i]]--]=i;
int num;
for(int k=1;k<=n;k<<=1) {
num=0;
for(int i=n-k+1;i<=n;i++) y[++num]=i;
for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
fill(c, c+m+1, 0);
for(int i=1;i<=n;i++) c[x[i]]++;
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i], y[i]=0;
swap(x, y), x[sa[1]]=1, num=1;
for(int i=2;i<=n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]?num:++num);
if(num==n) break;
m=num;
}
int k=0, j;
for(int i=1;i<=n;i++) if(x[i]>1) {
if(k) k--; j=sa[x[i]-1];
while(s[j+k]==s[i+k]) k++;
hei[x[i]]=k;
}
}
#define lowbit(x) x&-x
int C[N];
void updata(int x, int d) {
while(x<N) C[x]+=d, x+=lowbit(x);
}
int query(int x) {
int ret=0; while(x) ret+=C[x], x-=lowbit(x);
return ret;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
gn(n), gn(m);
int L, na;
for(int i=1;i<=n;i++) {
gn(L);
for(int j=1;j<=L;j++) gn(na), s[++len]=na, col[len]=i;
s[++len]=N-2, gn(L);
for(int j=1;j<=L;j++) gn(na), s[++len]=na, col[len]=i;
s[++len]=++idx;
}
for(int i=1;i<=m;i++) {
gn(L), col[len+1]=-i, length[i]=L, qu[L].push_back(i), pos[i]=len+1;
for(int j=1;j<=L;j++) gn(na), s[++len]=na;
s[++len]=++idx;
}
for(int i=1;i<=len;i++) s[i]++;
gsa();
for(int i=1;i<=len;i++) xl[i]=xr[i]=i, id[i]=i, rc[i]=col[sa[i]];
sort(id+1, id+1+len, cmp);
int xf;
for(int i=1;i<=len;i++) {
if(i>1 && hei[id[i]]!=hei[id[i-1]]) {
for(int j:qu[hei[id[i-1]]]) {
xf=Find(x[pos[j]]), l[xl[xf]].push_back(mpair(xr[xf], j));
r[xr[xf]].push_back(mpair(xl[xf], j));
}
}
Union(id[i], id[i]-1);
}
for(int i=1;i<=len;i++) {
if(rc[i]>0) {
if(lst[rc[i]]) updata(lst[rc[i]], -1);
updata(i, 1), lst[rc[i]]=i;
}
for(auto x:r[i]) a1[x.second]+=query(i)-query(x.first-1);
}
for(int i=1;i<=m;i++) printf("%d\n", a1[i]);
memset(C, 0, sizeof(C)), memset(lst, 0, sizeof(lst));
for(int i=1;i<=len;i++) {
updata(i, l[i].size());
if(rc[i]>0) {
if(lst[rc[i]]) a2[rc[i]]+=query(i)-query(lst[rc[i]]);
else a2[rc[i]]+=query(i);
lst[rc[i]]=i;
}
for(auto x:r[i]) updata(x.first, -1);
}
for(int i=1;i<=n;i++) printf("%d ", a2[i]);
putchar('\n');
return 0;
}
本文链接:https://pst.iorinn.moe/archives/sol-luogu-2336.html
许可: https://pst.iorinn.moe/license.html若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆
orzorz