秦皇岛网站制作哪家好,怎样做美瞳网站,如何运营一个行业网站,长宁区网站建设公司文章目录前言解析前言
1000A快乐#xff01;#xff01;#xff01;awa 没有想象中的那么恶心。
解析
先考虑每次都询问 [1,n][1,n][1,n] 如何做。 正难则反#xff0c;用T所有本质不同串数量减去是S串子串又是T的子串的数量 前者很好求#xff0c;关键是后者 首先可以…
文章目录前言解析前言
1000A快乐awa 没有想象中的那么恶心。
解析
先考虑每次都询问 [1,n][1,n][1,n] 如何做。 正难则反用T所有本质不同串数量减去是S串子串又是T的子串的数量 前者很好求关键是后者 首先可以常规操作求出每个T的前缀在S上匹配的最长后缀长度 www 考虑对T也建出一个SAM让T在自己的SAM上跑 假设跑到第 iii 个字符处于结点 uuu 若 wi≤lenlinkuw_i\le len_{link_u}wi≤lenlinku说明在 uuu 结点的等价类集合中没有任何子串是S的子串那么直接往 linklinklink 跳即可不断上跳直到不满足这个条件 然后令 ansu←max(ansu,wi)ans_u\gets \max(ans_u,w_i)ansu←max(ansu,wi)。 最后匹配子串的总和就是 ∑(ansi−lenlinki)\sum (ans_i-len_{link_i})∑(ansi−lenlinki)
考虑有区间限制 [l,r][l,r][l,r] 发现其实后面对于T的SAM的操作是不影响的唯一的不同就是 www 不太好求了 考虑对S的SAM的每个结点建一棵线段树存储 endpos\operatorname{endpos}endpos 集合 dfs 一遍线段树合并就可以求出来 注意这里需要保留原有的线段树需要可持久化 然后我们继续常规操作在S的串上跑T试图求出 wiw_iwi 但是现在的答案还要与 maxi∈endposu,i≤ri−l1\max_{i\in \operatorname{endpos_u},i\le r}i-l1maxi∈endposu,i≤ri−l1 取个 min 也就是合法右端点左侧最大的endpos可以通过刚才建出的线段树查询
那么我们再匹配之余看看往父亲跳是否可以不劣如果不劣就往上这样就可以了
注意跳父亲的条件是不劣而不是更优因为可能需要跳多次 linklinklink 才能跳到最优解在此之前结果不变
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N1e6100;
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 m;#define mid ((lr)1)
struct tree{int ls,rs,mx;
};
struct Segment_tree{tree tr[N5];int rt[N],tot;inline int copy(int x){tr[tot]tr[x];return tot;}inline void pushup(int k){tr[k].mxmax(tr[tr[k].ls].mx,tr[tr[k].rs].mx);return;}void upd(int k,int l,int r,int p){if(!k) kcopy(0);if(lr){tr[k].mxl;return;}if(pmid) upd(tr[k].ls,l,mid,p);else upd(tr[k].rs,mid1,r,p);pushup(k);}int merge(int x,int y,int l,int r){if(!x||!y) return x|y;if(lr) return x;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);return now;}int ask(int k,int l,int r,int x,int y){if(!k) return 0;if(xlry) return tr[k].mx;int res(0);if(xmid) resmax(res,ask(tr[k].ls,l,mid,x,y));if(ymid) resmax(res,ask(tr[k].rs,mid1,r,x,y));return res;}
}t;struct node{int len,fa;int tr[26];
};
struct SAM{char s[N];int n;node st[N];int cnt[N],id[N],pl[N];ll sum[N];int tot1,lst1;inline void clear(){while(tot){st[tot].lenst[tot].fa0;memset(st[tot].tr,0,sizeof(st[tot].tr));sum[tot]0;--tot;}totlst1;return;}inline void ins(int c,int o){c-a;int curtot,plst;lsttot;st[cur].lenst[p].len1;pl[cur]o;for(;p!st[p].tr[c];pst[p].fa) st[p].tr[c]cur;if(!st[p].tr[c]) st[cur].fa1;else{int qst[p].tr[c];if(st[q].lenst[p].len1) st[cur].faq;else{int pptot;st[pp]st[q];st[pp].lenst[p].len1;st[q].fast[cur].fapp;for(;pst[p].tr[c]q;pst[p].fa) st[p].tr[c]pp;}}}void calc(){fill(cnt,cnt1n,0);for(int i1;itot;i) cnt[st[i].len];for(int i1;in;i) cnt[i]cnt[i-1];for(int itot;i1;i--) id[cnt[st[i].len]--]i;for(int itot;i1;i--){if(id[i]!1) sum[id[i]]1;for(int j0;j26;j) sum[id[i]]sum[st[id[i]].tr[j]];}return;}void build(){scanf( %s,s1);nstrlen(s1);for(int i1;in;i) ins(s[i],i);return;}void print(){for(int i1;itot;i)printf(i%d fa%d len%d sum%lld pl%d\n,i,st[i].fa,st[i].len,sum[i],pl[i]);}
}s1,s2;vectorintv[N];
int ans[N];
void dfs(int x){if(s1.pl[x]){t.upd(t.rt[x],1,s1.n,s1.pl[x]);}for(int to:v[x]){dfs(to);t.rt[x]t.merge(t.rt[x],t.rt[to],1,s1.n);}// printf(x%d mx%d\n,x,t.tr[t.rt[x]].mx);return;
}int L,R;
inline int lenth(int x,int val){return max(0,min(min(val,s1.st[x].len),t.ask(t.rt[x],1,s1.n,1,R)-L1));
}
void work(){s2.build();s2.calc();Lread();Rread();// s2.print();int p11,p21,now(0);for(int i1;is2.n;i){int cs2.s[i]-a;while(p11!s1.st[p1].tr[c]) p1s1.st[p1].fa,nows1.st[p1].len;if(s1.st[p1].tr[c]){p1s1.st[p1].tr[c];now;}//printf( p1%d now%d\n,p1,now);while(p11lenth(s1.st[p1].fa,now)lenth(p1,now)){//printf( jump: ask%d mx%d rt%d (%d %d) (%d %d)\n,// t.ask(t.rt[p1],1,s1.n,1,R),t.tr[t.rt[p1]].mx,t.rt[p1],1,s1.n,1,R);p1s1.st[p1].fa;}nowlenth(p1,now);p2s2.st[p2].tr[c];while(p21s2.st[s2.st[p2].fa].lennow) p2s2.st[p2].fa;ans[p2]max(ans[p2],now);//printf(i%d p1%d p2%d now%d\n,i,p1,p2,now);}for(int is2.tot;i1;i--){int fs2.st[s2.id[i]].fa;ans[s2.st[s2.id[i]].fa]max(ans[f],min(s2.st[f].len,ans[s2.id[i]]));}ll ress2.sum[1];//printf(tot%lld\n,res);for(int i2;is2.tot;i){//printf(i%d ans%d\n,i,ans[i]);res-max(0,ans[i]-s2.st[s2.st[i].fa].len);ans[i]0;}printf(%lld\n,res);s2.clear();
}signed main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifs1.build();//s1.print();for(int i1;is1.tot;i) v[s1.st[i].fa].push_back(i);dfs(1);mread();while(m--) work();return 0;
}
/*
*/
