做爰全过程免费的视频凤凰网站,在线微信小程序,企业做网站公司排名口碑,网页qq怎么登录界面正题 题目大意
给出一个长度为nnn的字符串#xff0c;两个串相似当且仅当可以通过每种字符置换使得它们相同。 qqq次询问这个字符串所有子串中和这个串中sl,rs_{l,r}sl,r子串有多少个相似的。 1≤n≤105,1≤q≤51051\leq n\leq 10^5,1\leq q\leq 5\times 10^51≤n≤105,1≤…正题 题目大意
给出一个长度为nnn的字符串两个串相似当且仅当可以通过每种字符置换使得它们相同。
qqq次询问这个字符串所有子串中和这个串中sl,rs_{l,r}sl,r子串有多少个相似的。
1≤n≤105,1≤q≤5×1051\leq n\leq 10^5,1\leq q\leq 5\times 10^51≤n≤105,1≤q≤5×105
字符集是数字0∼90\sim 90∼9 解题思路
请问我是在阴间吗 首先对于相似的比较相信很常见维护每个数字上一个和它相同的数字的距离然后没有上一个就定为000就好了。
但是这题的问题在于我们提取出区间构成的数组时前面有些要变成000。
同样的这也是个提示因为字符集大小只有10我们也可以从这里入手对于一个后缀我们把第一个出现的数字的位置挖空后我们至多会把这个后缀以这些位置分成101010份我们将这个字符串序列称之为这个后缀的值。
然后我们需要的就是这些后缀值的“LCP”而这样我们需要我们能快速求这些后缀中字符串的LCP。
子串的LCP直接上SARMQ就好了。
这样我们把弄出来的后缀的值排好序然后维护一个相邻的两两之间的LCP计入一个类似height的数组的东西。
然后对于询问我们就直接二分在RMQ上查询就好了。
时间复杂度O(10nlognqlogn)O(10n\log nq\log n)O(10nlognqlogn) code
#includecstdio
#includecstring
#includealgorithm
#includevector
using namespace std;
const int N1e510;
struct node{int l,r;
};
struct nstr{vectornode r;int id;
}sr[N];
int n,m,q,nxt[10],p[10],pos[N];
int x[N],y[N],c[N],sa[N],rk[N];
int lg[N],f[N][20],h[N],s[N];
char rs[N];
void Qsort(){for(int i1;im;i)c[i]0;for(int i1;in;i)c[x[i]];for(int i1;im;i)c[i]c[i-1];for(int in;i1;i--)sa[c[x[y[i]]]--]y[i],y[i]0;return;
}
void Get_SA(){for(int i1;in;i)x[i]s[i]1,mmax(m,s[i]1),y[i]i;Qsort();for(int w1;wn;w1){int p0;for(int in-w1;in;i)y[p]i;for(int i1;in;i)if(sa[i]w)y[p]sa[i]-w;Qsort();swap(x,y);x[sa[1]]p1;for(int i2;in;i)x[sa[i]](y[sa[i]]y[sa[i-1]]y[sa[i]w]y[sa[i-1]w])?p:(p);if(pn)break;mp;}return;
}
void Get_Height(){int k0;for(int i1;in;i)rk[sa[i]]i;for(int i1;in;i){if(rk[i]1)continue;if(k)k--;int jsa[rk[i]-1];while(iknjkns[jk]s[ik])k;h[rk[i]]f[rk[i]][0]k;}return;
}
void Get_RMQ(){for(int i2;in;i)lg[i]lg[i1]1;for(int j1;(1j)n;j)for(int i1;i(1j)-1n;i)f[i][j]min(f[i][j-1],f[i(1j-1)][j-1]);return;
}
int RMQ(int l,int r){if(!l||!r)return 0;if(lr)return n-l1;lrk[l];rrk[r];if(lr)swap(l,r);l;int zlg[r-l1];return min(f[l][z],f[r-(1z)1][z]);
}
int RMQs(int l,int r){l;int zlg[r-l1];return min(f[l][z],f[r-(1z)1][z]);
}
void SA(){Get_SA();Get_Height();Get_RMQ();return;
}
int cp(node x,node y){//xyif(!x.l!y.l)return 2;if(!x.l)return 1;if(!y.l)return 0;int lenRMQ(x.l,y.l);if(lenx.r-x.l||leny.r-y.l){if(x.r-x.ly.r-y.l)return 2;return (x.r-x.l)(y.r-y.l);}return s[x.llen]s[y.llen];
}
bool cmp(nstr x,nstr y){int i0;while(1){if(ix.r.size())return 0;if(iy.r.size())return 1;int opcp(x.r[i],y.r[i]);if(op2)i;else return op;}return 0;
}
int LCP(nstr x,nstr y){int i0,ans0;while(ix.r.size()iy.r.size()cp(x.r[i],y.r[i])2)ansx.r[i].r-x.r[i].l1,i;if(ix.r.size()iy.r.size())ansmin(RMQ(x.r[i].l,y.r[i].l),min(x.r[i].r-x.r[i].l,y.r[i].r-y.r[i].l)1);return ans;
}
int main()
{
// freopen(similar.in,r,stdin);
// freopen(similar.out,w,stdout); scanf(%d%d,n,q);scanf(%s,rs1);for(int i1;in;i){if(!nxt[rs[i]-0])s[i]0;else s[i]i-nxt[rs[i]-0];nxt[rs[i]-0]i;}SA();memset(nxt,0,sizeof(nxt));for(int in;i1;i--){nxt[rs[i]-0]i;for(int j0;j9;j)p[j]nxt[j];sort(p,p10);int nowi;for(int j0;j9;j){if(!p[j])continue;if(p[j]now)sr[i].r.push_back((node){now,p[j]-1});sr[i].r.push_back((node){0,0});nowp[j]1;}if(nown)sr[i].r.push_back((node){now,n});sr[i].idi;}sort(sr1,sr1n,cmp);for(int i1;in;i)pos[sr[i].id]i;for(int i2;in;i)h[i]LCP(sr[i-1],sr[i]);for(int i2;in;i)f[i][0]h[i];for(int j1;(1j)n;j)for(int i1;i(1j)-1n;i)f[i][j]min(f[i][j-1],f[i(1j-1)][j-1]);int las0;while(q--){int l,r;scanf(%d%d,l,r);l^las;r^las;if(ln||rn||l1||r1)continue;int xpos[l],lenr-l1;int Lx1,Rn,ans1;while(LR){int mid(LR)1;if(RMQs(x,mid)len)Lmid1;else Rmid-1;}ansR-x;L1;Rx-1;while(LR){int mid(LR)1;if(RMQs(mid,x)len)Rmid-1;else Lmid1;}ansx-L;printf(%d\n,lasans);}return 0;
}
