产看网站权重,wordpress点击文章跳转外站,朔州网站建设价格低,网站后台管理默认密码正题
题目链接:http://noi.ac/problem/2144 题目大意
给出一个字符串sss和一个序列aaa。将字符串sss的所有本质不同子串降序排序后#xff0c;求有多少个区间[l,r][l,r][l,r]使得子串sl,rs_{l,r}sl,r排名等于al∼ra_{l\sim r}al∼r的和。 1≤n≤21051\leq n\leq 2\times…正题
题目链接:http://noi.ac/problem/2144 题目大意
给出一个字符串sss和一个序列aaa。将字符串sss的所有本质不同子串降序排序后求有多少个区间[l,r][l,r][l,r]使得子串sl,rs_{l,r}sl,r排名等于al∼ra_{l\sim r}al∼r的和。
1≤n≤2×1051\leq n\leq 2\times 10^51≤n≤2×105 解题思路
因为是降序排序所以每加一个字符排名是在下降的而aia_iai的和又是不降的所以对于每个左端点最多只有一个右端点且可以考虑二分求出这个位置。
如何快速得到子串排名开始不会还去LA\text{LA}LA群问了一下才知道。
SAMSAMSAM的一个节点代表多个串不能通过节点来得到排名。后缀树上的一个节点也是代表多个串但是这些串的排名是连续的因为这些串都有相同的前缀。
所以我们可以根据后缀树上确定每个节点的最小排名然后用倍增找出子串sl,rs_{l,r}sl,r的节点再根据长度确定具体排名。此时我们可以做到O(nlog2n)O(n\log^2 n)O(nlog2n)可以通过本题了。
但还可以继续优化发现我们倍增的过程有大量重复越往上排名越后所以我们类似二分的判断方法直接用倍增跳到答案节点然后在答案节点处再二分就好了。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4e510,T20;
ll n,cnt,num,last,tot,len[N],fa[N],ch[N][26],pos[N],id[N];
ll w[N],dep[N],f[N][T1],t[N][26],rk[N],p1[N],p2[N];
char s[N];
void Insert(ll c){ll plast,nplastcnt;len[np]len[p]1;for(;p!ch[p][c];pfa[p])ch[p][c]np;if(!p)fa[np]1;else{ll qch[p][c];if(len[p]1len[q])fa[np]q;else{ll nqcnt;len[nq]len[p]1;pos[nq]pos[q];memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]fa[q];fa[q]fa[np]nq;for(;pch[p][c]q;pfa[p])ch[p][c]nq;}}return;
}
void dfs(ll x){for(ll i25;i0;i--){ll yt[x][i];if(!y)continue;dep[y]dep[x]1;f[y][0]x;dfs(y);}rk[x]tot;totlen[x]-len[fa[x]];return;
}
signed main()
{scanf(%s,s1);nstrlen(s1);for(ll i1;in;i)scanf(%lld,w[i]),w[i]w[i-1];lastcnt1;for(ll in;i1;i--)Insert(s[i]-a),pos[last]i,id[i]last;for(ll i2;icnt;i)t[fa[i]][s[pos[i]len[fa[i]]]-a]i;dfs(1);for(ll j1;jT;j)for(ll i1;icnt;i)f[i][j]f[f[i][j-1]][j-1];for(ll p1;pn;p){ll xid[p];for(ll iT;i0;i--){ll yf[x][i];if(y1)continue;if(rk[y]1w[plen[y]-1]-w[p-1])xy;}ll llen[fa[x]]1,rlen[x];while(lr){ll mid(lr)1;if(rk[x]len[x]-mid1w[pmid-1]-w[p-1])rmid-1;else lmid1;}if(rk[x]len[x]-l1w[pl-1]-w[p-1])num,p1[num]p,p2[num]pl-1;}printf(%lld\n,num);for(ll i1;inum;i)printf(%lld %lld\n,p1[i],p2[i]);return 0;
}
