并不对劲的复健训练-bzoj5253:loj2479:p4384:[2018多省联考]制胡窜

题目大意

给出一个字符串$S$，长度为$n$（$n\leq 10^5$），$S[l:r]$表示$S_l,S_{l+1}...,S_r$这个子串。有$m$（$m\leq 3\times 10^5$）次询问，每次询问给出$l,r$，问有多少对$(i,j)$（$1\leq i<i+1<j\leq n$），使与$S[l:r]$本质相同的子串出现在$S[1:i]$中或$S[i+1:j-1]$中或$S[j:n]$中。

题解

询问相当于是问有多少种方案在$S$中找两个缝隙切两刀，使两刀不重合，且存在一个与$S[l:r]$本质相同的子串没被切。
这个比较难考虑，可以把它转换成在$n-1$个缝隙中选两个的总方案数-所有与$S[l:r]$本质相同的子串都被切的方案数。
所有与$S[l:r]$本质相同的子串都被切的方案数分以下几种情况考虑：
一、$S$中存在三个与$S[l:r]$本质相同的子串，且其中每两个的交集大小不超过1
会发现此时怎么切两刀都切不全这三个串，方案数为0。
二、$S$中不存在三个与$S[l:r]$本质相同的子串，且其中每两个的交集大小不超过1：假设所有这样的子串的最左的左端点为$ll$，最左的右端点为$lr$，最右的左端点为$rl$，最右的右端点为$rr$，$S[l:r]$长度为$len$，$r_i$表示right集合的第$i$个。
$\space\space\space\space$ 1.$S$中所有与$S[l:r]$本质相同的子串的交集不为空
$\space\space\space\space$ $\space\space\space\space$(1)靠前的一刀没切到与$S[l:r]$本质相同的子串：另一刀必须切在所有这样的子串的交集$[rl,lr]$上。这部分答案=$ll\times (lr-rl)$。注意刀只能切在缝隙上，所以是$(rl-lr)$而不是$(rl-lr+1)$。
$\space\space\space\space$ $\space\space\space\space$(2)靠前的一刀切到了一些与$S[l:r]$本质相同的子串，但没切在所有与$S[l:r]$本质相同的子串的交集上：会发现第二刀肯定要切在第一刀没切到的子串的交集上。所以对于两种方案，当它们第一刀切的串相同时，第二刀可行的取值范围相同。两种方案的第一刀都在$[r_i-len+1,r_{i+1}-len+1)$时，它们切的串都是$[1,i]$这个区间中的,它们第二刀的取值范围都是$[rl,r_{i+1}]$。也就是说，这部分答案=$\sum(r_{i+1}-r_i)\times(r_{i+1}-rl)$
$\space\space\space\space$ $\space\space\space\space$(3)靠前的一刀切到所有与$S[l:r]$本质相同的子串的交集上：其实这部分与(1)合并后就是“存在一刀切在所有与$S[l:r]$本质相同的子串的交集上，但靠前的一刀不是(2)的情况”。两刀都切在交集上的方案数是$C_^2$。对于只有一刀切在交集上的情况，相当于其中一刀不能在$[lr-len+1,lr]$上，另一刀必须在$[lr,rl]$上，所以这部分是 $(n-len)\times(lr-rl)$。也就是说(1)和(3)总共是$C_^{2+(n-len)\times(lr-rl)$。

$\space\space\space\space$ 2. $S$中所有与$S[l:r]$本质相同的子串的交集为空：两刀必须都切到与$S[l:r]$本质相同的子串，且都切不到这些子串的交集，和上一种情况的(2)类似。但是第一刀可能切不到最左的串，$[rl,r_{i+1}]$也可能是空集。发现当$r_i-len+1<lr$且$r_{i+1}>rl$时，第一刀切在$[r_i,r_{i+1})$都是合法的。这种情况的答案是$\sum\limits_{r_{i+1}>rl}}{r_i-len+1<lr}(r_{i+1}-r_i)\times(r_{i+1}-rl)$。还可能有一段$[r_i,r_{i+1})$，满足$lr\in[r_i-len+1,r_{i+1}-len+1)$即$(lr+len-1)\in[r_i,r_{i+1})$，这一段中比较靠前的地方$[r_i-len+1,lr]$可以切，靠后的不可以切。计算这种情况需要求$lr+len-1$左边第一个right集合的元素$r_p$和右边第一个$r_s$。这部分的答案是$(lr-r_p+len-1)\times (r_s-rl)$，需要注意的是，当$r_s\leq rl$时这部分的答案是0。

需要维护right集合和$\sum(r_{i+1}-r_i)\times(r_{i+1}-rl)$，可以拆成$s_1(l,r)=\sum(r_{i+1}-r_i)$和$s_2(l,r)=\sum(r_{i+1}-r_i)\times r_{i+1}$，这样就可以线段树维护区间right集合中最左和最右，合并时$s1(l,r)=s1(l,mid)+s1(mid+1,r)+min(mid+1,r)-max(l,mid)$，$s2(l,r)=s2(l,mid)+s2(mid+1,r)+(min(mid+1,r)-max(l,mid))\times min(mid+1,r)$。
求right集合需要线段树合并。据说不离线的话，“可持久化线段树合并”会MLE。
#####代码

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<iomanip>

#include<iostream>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define rep(i,x,y) for(register int i=(x);i<=(y);++i)

#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)

#define view(u,k) for(int k=fir[u];~k;k=nxt[k])

#define LL long long

#define maxn 100007

#define maxnd 200007

#define maxq 300007

#define maxk 6400007

#define ls son[u][0]

#define rs son[u][1]

#define mi (l+r>>1)

#define Ls(u) son[u][0]

#define Rs(u) son[u][1]

#define pb push_back

#define int long long

using namespace std;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)&&ch!='-')ch=getchar();

    if(ch=='-')f=-1,ch=getchar();

    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

    return x*f;

}

void write(LL x)

{

    if(x==0){putchar('0'),putchar('\n');return;}

    int f=0;char ch[20];

    if(x<0)putchar('-'),x=-x;

    while(x)ch[++f]=x%10+'0',x/=10;

    while(f)putchar(ch[f--]);

    putchar('\n');

    return;

}

int n,ch[maxnd][10],dis[maxnd],rt[maxnd],fa[maxnd],pt[maxn],lst,cnt,rot;

int son[maxk][2],cntnd,m,c[maxn],ord[maxnd],anc[maxnd][20];

char s[maxn];

LL ans[maxq];

struct node{int mx,mn;LL sum[2];}tr[maxk];

struct quest{int l,r,id;};

vector<quest>qt[maxnd];

void gt(node & x,node y){x.mx=y.mx,x.mn=y.mn,x.sum[0]=y.sum[0],x.sum[1]=y.sum[1];return;}

void pu(node & x,node ld,node rd)

{

	x.mx=rd.mx,x.mn=ld.mn,x.sum[0]=ld.sum[0]+rd.sum[0]+(LL)(rd.mn-ld.mx),x.sum[1]=ld.sum[1]+rd.sum[1]+(LL)(rd.mn-ld.mx)*rd.mn;

	return;

}

int build(int u,int l,int r,int x)

{

	if(!u)u=++cntnd;

	if(x<=l&&r<=x){tr[u].mx=tr[u].mn=x,tr[u].sum[0]=tr[u].sum[1]=0;return u;}

	if(x<=mi)ls=build(ls,l,mi,x);

	else rs=build(rs,mi+1,r,x);

	if(!ls||!rs)gt(tr[u],tr[ls|rs]);

	else pu(tr[u],tr[ls],tr[rs]);return u;

}

int merge(int ua,int ub,int l,int r)

{

	if(!ua||!ub)return ua|ub;

	Ls(ua)=merge(Ls(ua),Ls(ub),l,mi);

	Rs(ua)=merge(Rs(ua),Rs(ub),mi+1,r);

	if(!Ls(ua)||!Rs(ua))gt(tr[ua],tr[Ls(ua)|Rs(ua)]);

	else pu(tr[ua],tr[Ls(ua)],tr[Rs(ua)]);return ua;

}

void ask(int u,int l,int r,int x,int y,node & k)

{

	if(!u||x>y)return;

	if(x<=l&&r<=y){if(k.mx==0)gt(k,tr[u]);else pu(k,k,tr[u]);return;}

	if(x<=mi&&ls)ask(ls,l,mi,x,y,k);

	if(y>mi&&rs)ask(rs,mi+1,r,x,y,k);

	return;

}

int pref(int u,int x){node kk;kk.mx=kk.mn=0,ask(u,1,n,1,x,kk);return kk.mx;}

int sufx(int u,int x){node kk;kk.mx=kk.mn=0,ask(u,1,n,x,n,kk);return kk.mn;}

int gx(char c){return c-'0';}

void ext(int i)

{

	int p=lst,v=gx(s[i]),np=++cnt;dis[np]=i,lst=pt[i]=np;rt[np]=build(rt[np],1,n,i);

	for(;p&&!ch[p][v];p=fa[p])ch[p][v]=np;

	if(!p)fa[np]=rot;

	else

	{

		int q=ch[p][v];

		if(dis[p]+1==dis[q])fa[np]=q;

		else

		{

			int nq=++cnt;

			dis[nq]=dis[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[q]));

			fa[nq]=fa[q],fa[q]=fa[np]=nq;

			for(;p&&ch[p][v]==q;p=fa[p])ch[p][v]=nq;

		}

	}

}

int tp[maxq];

LL c2(int x){return (LL)x*(x-1)/2ll;}

signed main()

{

    rot=lst=cnt=1;

    scanf("%d%d%s",&n,&m,s+1);

    rep(i,1,n)ext(i);

    rep(i,1,cnt)c[dis[i]]++;

    rep(i,1,n)c[i]+=c[i-1];

    rep(i,1,cnt)ord[c[dis[i]]--]=i;

    rep(j,1,cnt)

    {

    	int i=ord[j];

    	anc[i][0]=fa[i];

    	rep(k,1,19)anc[i][k]=anc[anc[i][k-1]][k-1];

    }

    rep(i,1,m)

    {

    	int l=read(),r=read(),nd=pt[r];

    	dwn(j,19,0)if(dis[anc[nd][j]]>=r-l+1)nd=anc[nd][j];

		quest q;q.l=l,q.r=r,q.id=i;qt[nd].pb(q);

    }

    dwn(j,cnt,1)

    {

    	int i=ord[j],sz=qt[i].size(),rr=tr[rt[i]].mx,lr=tr[rt[i]].mn;

		rep(k,0,sz-1)

		{

    		int len=qt[i][k].r-qt[i][k].l+1,rl=rr-len+1,nd3=0;

			if(lr+len-1<=n)nd3=sufx(rt[i],lr+len-1);

			if(nd3&&nd3<=rl){tp[qt[i][k].id]=3;continue;}

			if(lr>rl){tp[qt[i][k].id]=1;ans[qt[i][k].id]=-tr[rt[i]].sum[0]*((LL)rl)+tr[rt[i]].sum[1]+c2(lr-rl)+(LL)(lr-rl)*(n-len);}

    		else

    		{

    			int sec,fst=pref(rt[i],rl);

    			node kk;kk.mx=kk.mn=0;if(fst)ask(rt[i],1,n,fst,lr+len-1,kk);

				if(kk.mx)ans[qt[i][k].id]=-(LL)rl*kk.sum[0]+kk.sum[1];

				fst=sec=0;

    			if(lr+len-1<=n)fst=pref(rt[i],lr+len-1),sec=sufx(rt[i],lr+len-1);

				if(sec&&fst&&sec>rl)ans[qt[i][k].id]+=(LL)(lr-fst+len-1)*(sec-rl);

    			tp[qt[i][k].id]=2;

			}

		}

    	rt[fa[i]]=merge(rt[fa[i]],rt[i],1,n);

	}

	rep(i,1,m){write(c2(n-1)-ans[i]);}

	return 0;

}

#####一些感想
写一下调一年，自闭不花一分钱

巴特西

并不对劲的复健训练-bzoj5253:loj2479:p4384:[2018多省联考]制胡窜

题目大意

题解

最新文章

热门文章