可不可以异地建设网站,太原视频剪辑培训机构哪个好,网上商城 网站,做鞋子有什么好网站好题意#xff1a; 给出一个的串 s#xff0c;将 s 所有子串按照字典序排列好相接起来形成一个新串q次询问#xff0c;每一次询问问新串中的第 k 个字符是什么#xff0c;强制在线。 $|s|,q \le 2*10^{5} $ 跟所有子串有关#xff0c;那肯定要么是后缀自动机#xff0c;要么…题意 给出一个的串 s将 s 所有子串按照字典序排列好相接起来形成一个新串q次询问每一次询问问新串中的第 k 个字符是什么强制在线。 $|s|,q \le 2*10^{5} $ 跟所有子串有关那肯定要么是后缀自动机要么是后缀树。 考虑后缀自动机。即使后缀自动机单次询问可以做到线性在这题也无施展之地。鉴于他DAWG的性质没有什么东西可以维护。 然而后缀树就不一样了[TJOI2015] 弦论有一种O(nlogn)的做法可以参考Mangoyang的博客。 实际上考虑 parent 可以进一步优化算法的复杂度考虑原先的 parent 树一个节点代表的多个串都是最长的串的一个后缀是一棵类似于前缀树的结构这样不能适用于一些字典序上优美的性质。不妨将串反序插入到sam 中这样每一个点能代表的多个串都是最长的串的前缀这些串从长到短在字典序上一定是有序的。扩展到整棵树上根据 minlen(u)len(fa(u))1 每个点代表的字符串都比其祖先代表的字符串的字典序大。于是可以计算出每一棵子树代表了多少串在 dfn 序上二分答案即可 类似的也可以计算出后缀树每一颗子树代表的串的总长并且通过构造可以使后缀树上字符串的字典序与 dfn 序同时有序。这样找到了后缀树上的一个节点后考虑一个子串其所代表的串长度在 [len(fa(u))1,len(u)] 上连续在这个节点上继续二分答案就可以找到第k个字符所在的子串及它的长度再计算一下就能知道第k个字符在s中的位置了。时间复杂度O(nqlogn) 1 #includebits/stdc.h2 using namespace std; 3 #define ll long long4 int const N20000010; 5 struct node{6 int len,fa,ch[26]; 7 }a[N1]; 8 int tot,ls,w[N1],num[N],sa[N1],cnt,pos[N1],son[N1][26]; 9 ll sum[N1],l[N1],sz[N1],qs[N1];
10 char s[N];
11 void add(int c,int id){
12 int pls;
13 int nplstot;
14 a[np].lena[p].len1;
15 w[tot]id;
16 sz[tot]1;
17 for(;p!a[p].ch[c];pa[p].fa) a[p].ch[c]np;
18 if(!p) a[np].fa1;
19 else {
20 int qa[p].ch[c];
21 if(a[q].lena[p].len1) a[np].faq;
22 else {
23 int nqtot;
24 a[nq]a[q];
25 a[nq].lena[p].len1;
26 a[q].faa[np].fanq;
27 for(;pa[p].ch[c]q;pa[p].fa)
28 a[p].ch[c]nq;
29 }
30 }
31 }
32 void dfs(int x){
33 if(!x ) return ;
34 pos[cnt]x;
35 for(int i0;i26;i)
36 dfs(son[x][i]);
37 }
38 int main(){
39 scanf(%s,s);
40 int lenstrlen(s);
41 totls1;
42 for(int ilen-1;i0;i--)
43 add(s[i]-a,i1);
44 for(int i2;itot;i)
45 sum[i]1;
46 for(int i1;itot;i) num[a[i].len];
47 for(int i1;ilen;i) num[i]num[i-1];
48 for(int i1;itot;i) sa[num[a[i].len]--]i;
49 for(int itot;i1;i--){
50 int xsa[i];
51 int fa[x].fa;
52 sz[f]sz[x];
53 w[f]w[f ]? w[f]:w[x];
54 }
55 for(int i2;itot;i){
56 int xa[i].fa;
57 int ys[w[i]a[a[i].fa].len-1]-a;
58 son[x][y]i;
59 }
60 dfs(1);
61 for(int i2;itot;i) {
62 int tpos[i];
63 ll xa[a[t].fa].len1;
64 ll ya[t].len;
65 ll tmpsz[t]*(xy)*(y-x1)/2;
66 qs[i]qs[i-1]tmp;
67 }
68
69 int q;
70 scanf(%d,q);
71 ll g0;
72 while (q--){
73 ll p,m;
74 scanf(%lld%lld,p,m);
75 ll kp*g % m 1;
76 int tlower_bound(qs1,qstot1,k)-qs;
77 k-qs[t-1];
78 tpos[t];
79 ll xa[a[t].fa].len1;
80 ll ya[t].len;
81 ll tmpsz[t]*(xy)*(y-x1)/2;
82 ll lx,ry;
83 while (lr){
84 ll mid(lr)/2;
85 tmpsz[t]*(xmid)*(mid-x1)/2;
86 if(tmpk) rmid;
87 else lmid1;
88 }
89 k-sz[t]*(xr-1)*(r-x)/2;
90 k(k-1) % r1;
91 int cw[t]k-2;
92 printf(%c\n,s[c]);
93 gs[c];
94 }
95 return 0;
96 } View Code 转载于:https://www.cnblogs.com/ZJXXCN/p/11054391.html
