P4384 [八省联考 2018] 制胡窜
考虑先将问题转化为切断两个位置使得没有任何一段中包含 \(t\)。则最终的答案为 \(\dbinom{n}{2}-\text{ans}\)。
计 \(t\) 按左端点排序后所有出现的段为 \([l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]\)。
-
若有三个及三个以上不相交的段，答案为 \(0\)。
-
若开头段与结尾段相交，即 \(l_k \le r_1\)。
- 若第一次断在 \([1,l_1)\)，则第二次必须断在 \((l_k,r_1]\)，共有 \((l_1-1)\times (r_1-l_k)\) 种满足条件的情况。
- 若第一次断在 \([l_i,l_{i+1})(i+1 \le k)\)，第二次必须断在 \((l_k,r_{i+1}]\)，即 \(\sum_{i=1}^{k-1} (l_{i+1}-l_i)\times (r_{i+1}-l_k)\)。
- 若第一次断在 \([l_k,r_1)\)，第二次可以断在右面的任意一个位置，则贡献为 \((n-l_k)+(n-(l_k+1))+...+(n-(r1-1))=\frac{(n+n-l_k-r_1-1)\times (r_1-l_k)}{2}\)。
- 若第一次断在 \([r_1,n]\)，第二次断在哪里 \([l_1,r_1]\) 都已经在 \(s\) 中出现，无解。
-
若开头段与结尾段不相交，即 \(l_k > r_1\)。容易发现第一次一定断在 \([1,r_1)\)，第二次一定断在 \((r_1,n]\)。找到最大的 \(i\) 满足 \(r_i \le r_1- \text{len}_t +1\)，记为 \(p\)。
-
若第一次断在 \([1,l_{p})\)，第二次断在哪里右边都会多出来一个无法切断的段，无解。
-
若第一次断在 \([l_p,r_1)\)，找到最大的 \(i\) 使得 \(l_i \le r_1\)，将其记为 \(q\)。
- 若第一次断在 \([l_i,l_{i+1})(p \le i< q)\)，第二次必须断在 \((l_k,r_{i+1}]\)，此时贡献为 \(\sum_{i=p}^{q-1} (l_{i+1}-l_i)\times (r_{i+1}-l_k)\)。
- 若第一次断在 \([l_q,r_1)\)，第二次必须断在 \((l_k,r_{q+1}]\)，贡献为 \((r_1-l_q)\times (r_{q+1}-l_k)\)。
-
若第一次断在 \([r_1,n]\)，前面的部分一定会包含 \(t\)，无解。
-
将情况 \(2\) 中带有求和号的式子化简，容易得到
\[\begin{aligned} \sum_{i=1}^{k-1}(l_{i+1}-l_i)\times (r_{i+1}-l_k)&=\sum_{i=1}^{k-1}(r_{i+1}-r_i)\times (r_{i+1}-l_k)\\ &=\sum_{i=1}^{k-1} (r_{i+1}^2-r_i\times r_{i+1}-l_{k}\times r_{i+1}+l_k\times r_i)\\ &=\sum_{i=1}^{k-1} r_{i+1}^2-\sum_{i=1}^{k-1} r_i\times r_{i+1}-(r_k-r_1)\times l_k \end{aligned} \]可以得到情况 \(3\) 中的式子为
\[\sum_{i=p}^{q-1} r_{i+1}^2-\sum_{i=p}^{q-1} r_i\times r_{i+1}-(r_q-r_p)\times l_k \]#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>inline bool read(T &x){
x=0;
char ch=getchar();
bool flag=0,ret=0;
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
x=flag?-x:x;
return ret;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
return read(a)&&read(args...);
}
template<typename T>void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
if(x<0) putchar('-'),x=-x;
prt(x);
putchar(ch);
}
template<typename T,typename ...Args>inline void put(T a,Args ...args){
put(a);
put(args...);
}
template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
put(ch,a);
put(ch,args...);
}
inline void put(string s){
for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
}
inline void put(const char* s){
for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
}
}
using namespace IO;
#define N 200005
#define int long long
#define inf 0x3f3f3f3f
#define ll long long
struct data{
ll maxn,minn,sum1,sum2;
data(){maxn=sum1=sum2=0,minn=inf;}
data(ll _maxn,ll _minn,ll _sum1,ll _sum2){
maxn=_maxn,minn=_minn,sum1=_sum1,sum2=_sum2;
}
inline data operator+(const data &b)const{
data res=data();
res.maxn=max(maxn,b.maxn);
res.minn=min(minn,b.minn);
res.sum1=sum1+b.sum1;
res.sum2=sum2+b.sum2+(ll)maxn*(b.minn<inf?b.minn:0);
return res;
}
};
struct Segment{
int idx;
Segment():idx(0){}
struct node{
int ls,rs;
data val;
}t[N<<5];
#define lc(x) t[x].ls
#define rc(x) t[x].rs
inline void push_up(int x){
t[x].val=t[lc(x)].val+t[rc(x)].val;
}
inline void update(int &x,int l,int r,int pos){
if(!x) x=++idx;
if(l==r) return t[x].val=data(l,l,(ll)l*l,0),void();
int mid=l+r>>1;
if(pos<=mid) update(lc(x),l,mid,pos);
else update(rc(x),mid+1,r,pos);
push_up(x);
}
inline int merge(int x,int y,int l,int r){
if(!x||!y) return x|y;
int z=++idx;
if(l==r){
t[z].val=data(l,l,(ll)l*l,0);
return z;
}
int mid=l+r>>1;
lc(z)=merge(lc(x),lc(y),l,mid);
rc(z)=merge(rc(x),rc(y),mid+1,r);
push_up(z);
return z;
}
inline data query(int x,int l,int r,int ql,int qr){
if(!x||qr<l||ql>r||ql>qr) return data();
if(ql<=l&&qr>=r) return t[x].val;
int mid=l+r>>1;
return query(lc(x),l,mid,ql,qr)+query(rc(x),mid+1,r,ql,qr);
}
#undef lc
#undef rc
}T;
int rt[N],n,m;
struct SAM{
int idx,lst,pos[N],f[N][23];
SAM():idx(1),lst(1){}
struct node{
int fa,len,ch[10];
}t[N];
inline void extend(int c){
int p=lst,np=lst=++idx;
t[np].len=t[p].len+1;
for(;p&&!t[p].ch[c];p=t[p].fa) t[p].ch[c]=np;
if(!p) t[np].fa=1;
else{
int q=t[p].ch[c];
if(t[p].len+1==t[q].len) t[np].fa=q;
else{
int nq=++idx;
t[nq]=t[q],t[nq].len=t[p].len+1;
t[np].fa=t[q].fa=nq;
for(;p&&t[p].ch[c]==q;p=t[p].fa) t[p].ch[c]=nq;
}
}
}
inline void insert(char *s){
for(int i=1;i<=n;i++){
extend(s[i]-'0');
pos[i]=lst;
T.update(rt[lst],1,n,i);
}
}
int id[N],c[N];
inline void topo_sort(){
for(int i=1;i<=idx;i++) c[t[i].len]++;
for(int i=1;i<=n;i++) c[i]+=c[i-1];
for(int i=1;i<=idx;i++) id[c[t[i].len]--]=i;
for(int i=1;i<=idx;i++) f[i][0]=t[i].fa;
for(int j=1;j<=20;j++)
for(int i=1;i<=idx;i++)
f[i][j]=f[f[i][j-1]][j-1];
for(int i=idx;i;i--){
int x=id[i],f=t[id[i]].fa;
rt[f]=T.merge(rt[f],rt[x],1,n);
}
}
inline int jump(int x,int k){
for(int i=20;~i;i--)
if(t[f[x][i]].len>=k) x=f[x][i];
return x;
}
inline int query(int L,int R){
int p=pos[R],len=R-L+1;
p=jump(p,len);
data now=T.query(rt[p],1,n,1,n);
ll r1=now.minn,l1=r1-len+1,rk=now.maxn,lk=rk-len+1;
ll ans=(ll)(n-1)*(n-2)/2;
if(lk<=r1){
ans-=(l1-1)*(r1-lk);
ans-=(r1-lk)*(n+n-lk-r1-1)/2;
ans-=now.sum1-r1*r1-now.sum2-(rk-r1)*lk;
return ans;
}
data nowp=T.query(rt[p],1,n,1,rk-len);
ll lp=nowp.maxn-len+1,rp=nowp.maxn;
if(r1+len<=rp) return ans;
data nowq=T.query(rt[p],1,n,rp,r1+len-1);
int lq=nowq.maxn-len+1,rq=nowq.maxn;
data nowq1=T.query(rt[p],1,n,rq+1,n);
int rq1=nowq1.minn;
ans-=(nowq.sum1-rp*rp)-nowq.sum2-(rq-rp)*lk;
ans-=(r1-lq)*(rq1-lk);
return ans;
}
}S;
char s[N];
signed main(){
read(n,m);
scanf("%s",s+1);
S.insert(s);
S.topo_sort();
for(int i=1,l,r;i<=m;i++)
read(l,r),put('\n',S.query(l,r));
return 0;
}