网站后台密码忘记了怎么办 ftp进不去,绿色 网站 源码,西安网站维保公司,网站大全软件Foreword\text{Foreword}Foreword 人都道正难则反#xff0c;我偏说正也不难。 这里介绍一种正面直接统计的做法。 和补集做法相比#xff0c;没有那么多的分类讨论#xff0c;更多的是对问题的正向分析和逐层化简、转化#xff0c;也并不麻烦。 由于需要写很多线段树的操作…Foreword\text{Foreword}Foreword 人都道正难则反我偏说正也不难。 这里介绍一种正面直接统计的做法。 和补集做法相比没有那么多的分类讨论更多的是对问题的正向分析和逐层化简、转化也并不麻烦。 由于需要写很多线段树的操作码量较大本人在210行左右但都是较为基础的操作写起来很舒适。 本来这就是一道码农题不是吗 我们开始吧。
Solution\text{Solution}Solution
前置规定 以下设截下的串的两端点即题面描述 i1,j−1i1,j-1i1,j−1为 x,yx,yx,yx,y∈(1,n)x,y\in(1,n)x,y∈(1,n)。 设询问串长度为 lenlenlen。 设 s(a,b)∑iabis(a,b)\sum_{ia}^bis(a,b)∑iabiababab 时规定 s(a,b)0s(a,b)0s(a,b)0。
以下基本模拟我做本题的思维过程
SA 和本题感觉不是很搭那基本就是 SAM 了。 给的限制乍一看非常恶心但细想想还挺有话说的。
Part 1
设询问串第一次出现的右端点 位置为 aaa最后一次出现左端点 位置为 bbb那么当中间截下的字符串 xaxaxa 或 ybybyb 的时候必然是合法的。 SAM 反串先建出后缀树记录出现的最早和最晚位置并向父亲传递即可维护这两个值。 容易统计这个时候的答案应该是 s(1,n−a−1)s(1,b−2)−s(1,(b−1)−(a1)1)s(1,n-a-1)s(1,b-2)-s(1,(b-1)-(a1)1)s(1,n−a−1)s(1,b−2)−s(1,(b−1)−(a1)1) 最后减去的是为了容斥掉左右端点同时满足条件算重的方案数。
Part 2
那么现在的问题就转化为了 求 x≤a,y≥bx\le a,y\ge bx≤a,y≥b 且包含询问串的字符串 (x,y)(x,y)(x,y) 对数。 这个东西并太不好做。 暴力怎么做 暴力是不是我们固定一个 xxx然后设左端点在 xxx 右侧的最靠左的字符串的右端点为 pospospos那么 rrr 的取值范围就是 [max(b,pos),n−1][\max(b,pos),n-1][max(b,pos),n−1]。 随着左端点右移 pospospos 单调不升右端点可以取到的范围肯定是逐渐变大最后变成 [b,n−1][b,n-1][b,n−1]。 我们尝试掐头去尾的计算这部分的答案。
Part 2.1
我们找到满足 r≤br\le br≤b 的最靠左询问串设其左端点为 uuu那么当 x≤ux\le ux≤u 时yyy 的取值范围就变成了 [b,n−1][b,n-1][b,n−1]。 这部分的贡献是 (u−1)(n−b)(u-1)(n-b)(u−1)(n−b) 需要注意一些边界情况如果 u≥au\ge au≥a那么整个 part2 的贡献就是 (a−1)(n−b)(a-1)(n-b)(a−1)(n−b)加上后直接返回即可。
Part 2.2
设 lalala 的最靠左的询问串的左端点为 sufsufsufl≤al\le al≤a 的最靠右的询问串左端点为 preprepre那么当 x∈(pre,a]x\in(pre,a]x∈(pre,a] 时yyy 一直是在受 sufsufsuf 这个串约束其范围是 [suflen−1,n−1][suflen-1,n-1][suflen−1,n−1]。 这部分的贡献就是 (a−pre)(n−suf)(a-pre)(n-suf)(a−pre)(n−suf)
Part 2.3
现在我们只剩下 x∈[u1,pre]x\in[u1,pre]x∈[u1,pre] 这一段的贡献了。
我们想想最理想的情况每个位置都有一个询问串的左端点那么答案显然就是 ∑iu1pren−(ilen−1)s(n−(prelen−1),n−(u1len−1))\sum_{iu1}^{pre}n-(ilen-1)s(n-(prelen-1),n-(u1len-1))iu1∑pren−(ilen−1)s(n−(prelen−1),n−(u1len−1)) 但是现实很骨感真实答案可能会取不到这么多那么会少多少呢 举个栗子设左端点出现集合为 101001101001101001考虑它和 111111111111111111 相比少了多少答案。 不难发现第一段长度为 111 的 000 串使答案减少了 111第二段答案为 222 的 000 串使答案减少了 123123123。 一般的一段长度为 LLL 的极长 000 串会使答案减少 s(1,L)s(1,L)s(1,L)。 那么问题就变成求 [u1,pre][u1,pre][u1,pre] 这部分 000 串减少的答案之和利用线段树合并 startposstartposstartpos 集合即可轻松维护。 (startpos这个名字是我瞎起的就是正常SAM的endpos)
然后本题就做完了。 时间复杂度 O((nm)logn)O((nm)\log n)O((nm)logn)。
Code\text{Code}Code
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N4e5100;
const int C10;inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m,k;int tag[N],mn[N],mx[N];
int pos[N];
int pl[N][20];
vectorintv[N];#define calc(x) (1ll*(x)*((x)1)/2)
struct node{int llen,rlen,siz;ll sum;
};
node operator (const node a,const node b){node o;o.siza.sizb.siz;o.llena.llena.siz?a.sizb.llen:a.llen;o.rlenb.rlenb.siz?b.siza.rlen:b.rlen;o.suma.sumb.sum;o.sumcalc(a.rlenb.llen)-calc(a.rlen)-calc(b.llen);return o;
}
inline node emp(int len){return (node){len,len,len,calc(len)};
}struct tree{int ls,rs;node o;
};
int rt[N],tot;
struct Seg{tree tr[N*20];#define mid ((lr)1)inline void pushup(int k,int l,int r){node xtr[k].ls?tr[tr[k].ls].o:emp(mid-l1);node ytr[k].rs?tr[tr[k].rs].o:emp(r-mid);tr[k].oxy;return;}inline int copy(int x){tr[tot]tr[x];return tot;}void upd(int k,int l,int r,int p){kcopy(k);if(lr){tr[k].o(node){0,0,1,0};return;}if(pmid) upd(tr[k].ls,l,mid,p);else upd(tr[k].rs,mid1,r,p);pushup(k,l,r);}int merge(int x,int y,int l,int r){if(!x||!y) return x|y;int nowcopy(x);tr[now].lsmerge(tr[now].ls,tr[y].ls,l,mid);tr[now].rsmerge(tr[now].rs,tr[y].rs,mid1,r);pushup(now,l,r);return now;}int findsuf(int k,int l,int r,int p){if(!k) return 0;if(lr) return (lp)?l:0;if(pmid) return findsuf(tr[k].rs,mid1,r,p);else{int resfindsuf(tr[k].ls,l,mid,p);if(res) return res;else return findsuf(tr[k].rs,mid1,r,p);}}int findpre(int k,int l,int r,int p){if(!k) return 0;if(lr) return (lp)?l:0;if(pmid) return findpre(tr[k].ls,l,mid,p);else{int resfindpre(tr[k].rs,mid1,r,p);if(res) return res;else return findpre(tr[k].ls,l,mid,p);}}node query(int k,int l,int r,int x,int y){if(!k) return emp(min(r,y)-max(l,x)1);if(xlry) return tr[k].o;if(ymid) return query(tr[k].ls,l,mid,x,y);else if(xmid) return query(tr[k].rs,mid1,r,x,y);else return query(tr[k].ls,l,mid,x,y)query(tr[k].rs,mid1,r,x,y);}
}seg;void dfs(int x,int fa){pl[x][0]fa;for(int k1;pl[x][k-1];k) pl[x][k]pl[pl[x][k-1]][k-1];for(int to:v[x]){dfs(to,x);mn[x]min(mn[x],mn[to]);mx[x]max(mx[x],mx[to]);rt[x]seg.merge(rt[x],rt[to],1,n);}if(tag[x]){seg.upd(rt[x],1,n,tag[x]);}return;
}struct SAM{int tr[N][C],fa[N],len[N],tot,lst;SAM(){totlst1;}inline void ins(int c,int id){c-0;int curtot,plst;lsttot;len[cur]len[p]1;pos[id]cur;tag[cur]id;mn[cur]mx[cur]id;for(;p!tr[p][c];pfa[p]) tr[p][c]cur;if(!p) fa[cur]1;else{int qtr[p][c];if(len[q]len[p]1) fa[cur]q;else{int nqtot;mn[nq]n1;mx[nq]0;len[nq]len[p]1;fa[nq]fa[q];for(int i0;iC;i) tr[nq][i]tr[q][i];fa[cur]fa[q]nq;for(;ptr[p][c]q;pfa[p]) tr[p][c]nq;}}return;}void build(){for(int i2;itot;i) v[fa[i]].push_back(i);dfs(1,0);}int find(int l,int r){int xpos[l],Lr-l1;for(int k18;k0;k--){if(len[pl[x][k]]L) xpl[x][k];}return x;}
}sam;inline ll Sum(ll x,ll y){if(xy) return 0;else return (xy)*(y-x1)/2;
}
ll work(int l,int r){int xsam.find(l,r),lenr-l1;int amn[x]len-1,bmx[x];ll ansSum(1,n-a-1)Sum(1,b-2);int w(b-1)-(a1)1;if(w1) ans-calc(w);amin(a,b);int preseg.findpre(rt[x],1,n,a),sufseg.findsuf(rt[x],1,n,a1);int useg.findpre(rt[x],1,n,b-len1);if(ua){ans1ll*(a-1)*(n-b);return ans;}if(suf){ans1ll*(a-pre)*(n-(suflen-1));}if(u) ans1ll*(u-1)*(n-b);//calc: [u1,pre]umax(u,1);if(u1pre){ansSum(n-(prelen-1),n-(u1len-1)); node oseg.query(rt[x],1,n,u1,pre);ans-o.sum;}return ans;
}char s[N];
signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifnread();mread();scanf( %s,s1);for(int in;i1;i--) sam.ins(s[i],i);sam.build();for(int i1;im;i){int lread(),rread();printf(%lld\n,work(l,r));}return 0;
}
/*
*/
