文章目錄

• 前言
• 解析

前言

1000A快樂！！！awa
沒有想象中的那么惡心。

解析

先考慮每次都詢問 $[1,n]$ 如何做。
正難則反，用T所有本質不同串數量減去是S串子串又是T的子串的數量
前者很好求，關鍵是后者
首先可以常規操作求出每個T的前綴在S上匹配的最長后綴長度 $w$
考慮對T也建出一個SAM，讓T在自己的SAM上跑
假設跑到第 $i$ 個字符，處于結點 $u$
若 $w_i\le le{n}_{lin{k}_u}$，說明在 $u$ 結點的等價類集合中沒有任何子串是S的子串，那么直接往 $link$ 跳即可，不斷上跳，直到不滿足這個條件
然后，令 $an{s}_u\leftarrow \max (an{s}_u,w_i)$。
最后匹配子串的總和就是 $\sum (an{s}_i?le{n}_{lin{k}_i})$

考慮有區間限制 $[l,r]$
發現其實后面對于T的SAM的操作是不影響的，唯一的不同就是 $w$ 不太好求了
考慮對S的SAM的每個結點建一棵線段樹，存儲 $\mathrm{endpos}$ 集合
dfs 一遍線段樹合并就可以求出來
（注意這里需要保留原有的線段樹，需要可持久化）
然后我們繼續常規操作，在S的串上跑T試圖求出 $w_i$
但是現在的答案還要與 ${\max }_{i\in \mathrm{e}\mathrm{n}\mathrm{d}\mathrm{p}\mathrm{o}{\mathrm{s}}_{\mathrm{u}},i\le r}i?l+1$ 取個 min
（也就是合法右端點左側最大的endpos，可以通過剛才建出的線段樹查詢）

那么我們再匹配之余看看往父親跳是否可以不劣，如果不劣就往上，這樣就可以了

注意跳父親的條件是不劣而不是更優，因為可能需要跳多次 $link$ 才能跳到最優解，在此之前結果不變

#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define debug(...) fprintf(stderr,__VA_ARGS__) const int N=1e6+100; inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }int m;#define mid ((l+r)>>1) struct tree{int ls,rs,mx; }; struct Segment_tree{tree tr[N<<5];int rt[N],tot;inline int copy(int x){tr[++tot]=tr[x];return tot;}inline void pushup(int k){tr[k].mx=max(tr[tr[k].ls].mx,tr[tr[k].rs].mx);return;}void upd(int &k,int l,int r,int p){if(!k) k=copy(0);if(l==r){tr[k].mx=l;return;}if(p<=mid) upd(tr[k].ls,l,mid,p);else upd(tr[k].rs,mid+1,r,p);pushup(k);}int merge(int x,int y,int l,int r){if(!x||!y) return x|y;if(l==r) return x;int now=copy(x);tr[now].ls=merge(tr[now].ls,tr[y].ls,l,mid);tr[now].rs=merge(tr[now].rs,tr[y].rs,mid+1,r);pushup(now);return now;}int ask(int k,int l,int r,int x,int y){if(!k) return 0;if(x<=l&&r<=y) return tr[k].mx;int res(0);if(x<=mid) res=max(res,ask(tr[k].ls,l,mid,x,y));if(y>mid) res=max(res,ask(tr[k].rs,mid+1,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 tot=1,lst=1;inline void clear(){while(tot){st[tot].len=st[tot].fa=0;memset(st[tot].tr,0,sizeof(st[tot].tr));sum[tot]=0;--tot;}tot=lst=1;return;}inline void ins(int c,int o){c-='a';int cur=++tot,p=lst;lst=tot;st[cur].len=st[p].len+1;pl[cur]=o;for(;p&&!st[p].tr[c];p=st[p].fa) st[p].tr[c]=cur;if(!st[p].tr[c]) st[cur].fa=1;else{int q=st[p].tr[c];if(st[q].len==st[p].len+1) st[cur].fa=q;else{int pp=++tot;st[pp]=st[q];st[pp].len=st[p].len+1;st[q].fa=st[cur].fa=pp;for(;p&&st[p].tr[c]==q;p=st[p].fa) st[p].tr[c]=pp;}}}void calc(){fill(cnt,cnt+1+n,0);for(int i=1;i<=tot;i++) ++cnt[st[i].len];for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];for(int i=tot;i>=1;i--) id[cnt[st[i].len]--]=i;for(int i=tot;i>=1;i--){if(id[i]!=1) sum[id[i]]=1;for(int j=0;j<26;j++) sum[id[i]]+=sum[st[id[i]].tr[j]];}return;}void build(){scanf(" %s",s+1);n=strlen(s+1);for(int i=1;i<=n;i++) ins(s[i],i);return;}void print(){for(int i=1;i<=tot;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;vector<int>v[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)-L+1)); } void work(){s2.build();s2.calc();L=read();R=read();// s2.print();int p1=1,p2=1,now(0);for(int i=1;i<=s2.n;i++){int c=s2.s[i]-'a';while(p1>1&&!s1.st[p1].tr[c]) p1=s1.st[p1].fa,now=s1.st[p1].len;if(s1.st[p1].tr[c]){p1=s1.st[p1].tr[c];++now;}//printf(" p1=%d now=%d\n",p1,now);while(p1>1&&lenth(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);p1=s1.st[p1].fa;}now=lenth(p1,now);p2=s2.st[p2].tr[c];while(p2>1&&s2.st[s2.st[p2].fa].len>=now) p2=s2.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 i=s2.tot;i>=1;i--){int f=s2.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 res=s2.sum[1];//printf("tot=%lld\n",res);for(int i=2;i<=s2.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 i=1;i<=s1.tot;i++) v[s1.st[i].fa].push_back(i);dfs(1);m=read();while(m--) work();return 0; } /* */

總結

以上是生活随笔為你收集整理的P4770：你的名字（SAM、线段树合并）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。