[DS记录]P5161 WD与数列
command_block
·
·
个人记录
题意 : 定义两个数组匹配,当且仅当 : 其中一个整体加上某个值之后,两者完全相同。
给出数组 S ,求 S 中有多少对(无序)不相交的区间是匹配的。
------------
首先容易发现 : 两个区间匹配当且仅当其**差分数组完全相等**,且不相交,相邻。
对于只有一个元素的数组,差分数组为空,不便处理,统一在最后计算。
> 当年似乎打过这个公开赛,然而只会签到题,思路到此为止,最后写了个哈希还挂了。
建立`SAM`,注意字符集很大,需要`std::map`。
考虑跨越某个`SAM`点的前缀对 $u,v\ (u<v)$ 的贡献。
设最多能匹配 $d$ 位(后缀),则 $v$ 结尾的串开头是 $v-d+1$ ,必须$>u+1$ 所以有 $1\leq d\leq v-u-1$ ,取值有 $v-u-1$ 种。
而 $d$ 本身受到当前点 $len$ 值的约束,又有 $1\leq d\leq len$ ,所以贡献是 $\min(v-u-1,len)$ 。
在`parent`树上链分治(启发式合并),维护`edp`的线段树,这样能够严格统计到`LCA`恰为当前点的对子的贡献。
对于一个新加入的后缀 $u$ :
- 查询 $[u-len,u)$ 内的后缀 $v$ ,此时的贡献为 $v-u-1$。
- 查询 $[1,u-len)$ 内的后缀 $v$ ,此时的贡献是 $len$。
- 查询 $(u,u+len]$ 内的后缀 $v$ ,此时的贡献为 $u-v-1$。
- 查询 $(u+len,n]$ 内的后缀 $v$ ,此时的贡献是 $len$。
不难发现,只需要维护区间下标和,个数和即可回答。
时间复杂度 $O(n\log^2n)$ ,空间复杂度 $O(n\log n)$。
然后就是码。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#define ll long long
#define MaxN 305000
using namespace std;
int read(){
int X=0;char ch=0,w=0;
while(ch<48||ch>57)ch=getchar(),w|=(ch=='-');
while(ch>=48&&ch<=57)X=X*10+(ch^48),ch=getchar();
return w?-X:X;
}
struct Node
{map<int,int> t;int f,len;}a[MaxN<<1];
int tot,las;
void add(int c)
{
int np=++tot,p=las;las=np;
a[np].len=a[p].len+1;
for (;p&&!a[p].t[c];p=a[p].f)a[p].t[c]=np;
if (!p)a[np].f=1;
else {
int v=a[p].t[c];
if (a[p].len+1==a[v].len)a[np].f=v;
else {
int nv=++tot;a[nv]=a[v];
a[nv].len=a[p].len+1;
for (;p&&a[p].t[c]==v;p=a[p].f)a[p].t[c]=nv;
a[v].f=a[np].f=nv;
}
}
}
vector<int> g[MaxN<<1];
int siz[MaxN<<1],p[MaxN<<1];
void pfs(int u)
{
siz[u]=1;
for (int i=0,v;i<g[u].size();i++){
pfs(v=g[u][i]);
siz[u]+=siz[v];
if (siz[v]>siz[p[u]])p[u]=v;
}
}
struct Data
{int l,r,c;ll s;}t[MaxN*22];
int n,rt[MaxN<<1],tn,to;
void build(int l,int r,int &u)
{
u=++tn;
t[u].c=1;t[u].s=to;
if (l==r)return ;
int mid=(l+r)>>1;
if (to<=mid)build(l,mid,t[u].l);
else build(mid+1,r,t[u].r);
}
int merge(int x,int y)
{
if (!x||!y)return x|y;
t[x].l=merge(t[x].l,t[y].l);
t[x].r=merge(t[x].r,t[y].r);
t[x].c=t[t[x].l].c+t[t[x].r].c;
t[x].s=t[t[x].l].s+t[t[x].r].s;
return x;
}
int wfl,wfr,oc;ll os;
void qry(int l,int r,int u)
{
if (wfl<=l&&r<=wfr){
oc+=t[u].c;os+=t[u].s;
return ;
}int mid=(l+r)>>1;
if (wfl<=mid)qry(l,mid,t[u].l);
if (wfr>mid)qry(mid+1,r,t[u].r);
}
ll ans;
#define pre(l,r) {wfl=max(l,1);wfr=min(r,n);os=oc=0;}
void chk(int x,int rt,int len)
{
pre(x-len,x-1);
if (wfl<=wfr){qry(1,n,rt);ans+=1ll*(x-1)*oc-os;}
pre(1,x-len-1);
if (wfl<=wfr){qry(1,n,rt);ans+=1ll*oc*len;}
pre(x+1,x+len);
if (wfl<=wfr){qry(1,n,rt);ans+=os-1ll*(x+1)*oc;}
pre(x+len+1,n);
if (wfl<=wfr){qry(1,n,rt);ans+=1ll*oc*len;}
}
int tp,tlen,w[MaxN<<1];
void dfs2(int u){
if (w[u])chk(w[u],tp,tlen);
for (int i=0;i<g[u].size();i++)
dfs2(g[u][i]);
}
void dfs(int u)
{
if (!p[u])return ;
dfs(p[u]);
if (w[u])chk(w[u],rt[p[u]],a[u].len);
rt[u]=merge(rt[u],rt[p[u]]);
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=p[u]){
tp=rt[u];tlen=a[u].len;
if (tp&&tlen)dfs2(v);
dfs(v);rt[u]=merge(rt[u],rt[v]);
}
}
int s[MaxN];
int main()
{
n=read();
for (int i=1;i<=n;i++)s[i]=read();
for (int i=1;i<n;i++)s[i]=s[i+1]-s[i];
tot=las=1;n--;
for (int i=1;i<=n;i++)add(s[i]);
for (int i=1,p=1;i<=n;i++){
to=w[p=a[p].t[s[i]]]=i;
build(1,n,rt[p]);
}for (int i=2;i<=tot;i++)
g[a[i].f].push_back(i);
pfs(1);dfs(1);
printf("%lld",ans+1ll*n*(n+1)/2);
return 0;
}
```