$ CSP.S $ 集訓刷題記錄：
$ By~wcwcwch $
一、字元串專題：
1. 【模闆】$ manacher $ 算法
模型：
求出字元串 $ S $ 中所有回文串的位置及長度。
$ solution $ ：
個人了解：解決這類問題，回文串的對稱性質最重要。
于複雜度最關鍵的一句話： $ f[i]=min~(~r-i~,~f[~mid\times2-i~]~)~ $ （實作不同，邊界可能不一樣）
這個 $ min $ 函數左邊 $ r-i $ 是目前位置到它所屬于的回文串邊界的距離，右邊 $ mid\times 2 -1 $ 是它在所屬于的回文串的另一邊的對應位置。如果取左邊，那麼我用目前位置擴充（會超出目前回文串邊界）于是必然能夠使 $ r $ 向右擴充；如果取右邊，我們發現由于回文串的對稱性，這個位置必然不能繼續向外擴充，因為他最開始向外擴充必然還是在目前回文串邊界内（否則 $ min $ 函數肯定取的左邊），而如果它能在目前回文串内擴充，它的對稱位置 $ mid\times 2 -1 $ 也能，而 $ f[~mid\times2-i~] $ 已是擴充最大值，與之沖突。
總結一下，如果 $ min $ 函數取左邊，那麼 $ r $ 一定能向右擴充；如果取右邊，那麼複雜度為 $ 1 $ （常數）。于是複雜度為 $ r $ 的值域和 $ 1 $ 的次數，兩者都不超過 $ n $ ，于是複雜度為 $ O(2\times n) $ ，就算再加上與處理時加“#”号，也是常數而已。
2. 【模闆】擴充 $ KMP $
模型：
有一個字元串 $ a $ ，要求輸出【 $ a $ 本身】和【 $ a $ 的每一個字尾】的最長公共字首 。
$ solution $ ：
$ KMP $ 和 $ Manacher $ 思想的結合産物。不過個人更傾向于 $ Manacher $ 。因為他的計算方法和 $ Manacher $ 神似，都是在某一個位置先根據之前的結果得到一個初始的公共字首長度，就是“回文串”變成了最長公共字首，回文串的中心 $ mid $ 變成了最長公共字首的左端點 $ l $ ，最後 $ min $ 函數長的不一樣了。
我們對于 $ a $ 處理出它【每一位開始的字尾】和【 $ a $ 本身】的最長公共字首 $ f[i] $ 。注意我們要從第二位開始 ，因為 $ f[1]=|a| $ 很特殊。我們用 $ l $ 記錄已經周遊過的 $ i $ 中 $ i+f[i] $ 最大的 $ i $ ，同時用 $ r $ 記錄 $ i+f[i] $ ，這兩者初始均為 $ 0 $ 。然後： $ f[i]=min(~r-i~,~f[i-l+1]~) $ ，這個計算初始值的式子和 $ Manacher $ 很像， $ i $ 處于一個公共字首裡，那麼 $ i $ 後面的字母一定和 $ f[i-l+1] $ 後面的字母在 $ r-i $ 範圍内保持一緻，于是直接拿來作為初始值即可。複雜度證明和上面 $ Manacher $ 一樣！
$ code $ ：
int n,m;
int f[2000005];
string s,a;
int main(){
cin>>a; n=a.size();
cin>>s; m=s.size();
s=' '+s+'#'+a; n+=m+2; //加到一起
rg l=0,r=0; f[1]=m; //第一個不管
for(rg i=2;i<=n;++i){
if(i<=r) f[i]=min(r-i,f[i-l+1]); //确定初始值
while(s[f[i]+1]==s[i+f[i]]) ++f[i]; //向後擴充
if(i+f[i]-1>r) l=i,r=i+f[i]-1; //更新l和r的值
}
for(rg i=1;i<=m;++i) printf("%d%c",f[i],i==m?'\n':' ');
for(rg i=m+2;i<n;++i) printf("%d%c",f[i],i==n-1?'\n':' ');
return 0;
} 3. $ LOJ~3095 $ ： $ Snoi~2019 $ 字元串
題意概括：
給一個長度為 $ n $ 的字元串 $ S $ ，記 $ S′_i $ 表示 $ S $ 删去第 $ i $ 個字元後得到的字元串，輸出：\(( S′_1 , 1)...(S′_n , n)\) 的字典序排序結果。 $ n\leq 10^6 $
$ solution $ ：
我們仔細觀察題目，手算分析樣例，可以發現一個性質：
- 設從 $ i $ 号位置開始，往後第一個與 $ i $ 号位不同的位置為 $ j $ ，則 $ [i,j-1] $ 的字元串相等。
- 若 $ a[i]<a[j] $ ，則可以發現後面的字元串因為多包含一個 $ a[i] $ 而小于 $ [i,j-1] $ 。
- 若 $ a[i]>a[j] $ ，則可以發現後面的字元串因為多包含一個 $ a[i] $ 而大于 $ [i,j-1] $ 。
于是我們開一個雙端加入的數組，記錄最後的答案。期望複雜度： $ O(n) $
$ code $ ：
n=qr(); cin>>a; a=' '+a; a[n+1]=')'; //防出界
rg l=0,r=n+1; //記錄雙端指針
for(rg i=1;i<=n;++i){ rg j=i;
while(a[i]==a[i+1])++i; //找到連續相同串的右端點
if(a[i+1]<a[i]) for(rg k=j;k<=i;++k) s[++l]=k; //這一段都必然比後面的串小
else for(rg k=i;k>=j;--k) s[--r]=k; //這一段都必然比後面的串大
}
for(rg i=1;i<=n;++i) printf("%d ",s[i]); 4. 洛谷 $ P5446 $ ： $ THUPC~2018 $ 綠綠和串串
題意概括：
對于字元串 $ S $ ，定義運算 $ f(S) $ 為将 $ S $ 的前 $ |S|-1 $ 個字元倒序接在 $ S $ 後面形成的長為 $ 2|S|-1 $ 的新字元串。現給出字元串 $ T $ ，詢問有哪些串長度不超過 $ |T| $ 的串 $ S $ 經過若幹次 $ f $ 運算後得到的串包含 $ T $ 作為字首。$ 1 \le |T| \le 5 \times 10^6. $
$ solution $ ：
很糾結的一道題，調了好一會才發現思維不夠嚴謹，判斷出錯了。
首先我們不難發現這是一道與回文串有關的題目，我們可以發現如果 $ S $ 串中存在一個位置 $ i $ 使得它的最長回文串能到達 $ S $ 串的末尾，那麼對 $ [1,i] $ 這一段字元進行 $ f(1,i) $ 的操作一定可以得到一個合法新字元串使 $ S $ 為其字首。然後我們還可以發現如果将這些位置标記，如果 $ S $ 串中還有一些位置 $ i $ 使得從 $ i $ 擴充的回文串可以到達 $ S $ 串的第一個字元且這個回文串的末尾字元是被标記了的，那麼這個位置也是合法的！因為隻要進行多次 $ f $ 操作即可。
$ code $ ：
t=qr();
while(t--){
cin>>s; n=s.size(); s=' '+s; //讀入
rg mid=0,r=0; s[0]='('; s[n+1]=')'; //設邊界
for(rg i=1;i<=n;++i){ f[i]=0;
if(i<r) f[i]=min(r-i,f[(mid<<1)-i]); //manacher尋找初值
while(s[i-f[i]-1]==s[i+f[i]+1]) ++f[i]; //擴充
if(i+f[i]>r) mid=i,r=i+f[i]; //更新
} k[n]=1;
for(rg i=n;i>=1;--i) //如果轉一次就合法，或者能夠連轉多次
if(i+f[i]==n||(i-f[i]==1&&k[i+f[i]])) k[i]=1;
for(rg i=1;i<=n;++i)
if(k[i])printf("%d ",i),k[i]=0; //輸出+清零
puts("");
} 5. 洛谷 $ P4503 $ ：$ CTSC~2014~$ 企鵝 $~QQ $
題意概括：
給出一個帶通配符的字元串 $ S $ ，通配符分兩種，一種可以比對恰好一個字元，另一種可以比對任意個（包括 $ 0 $ 個）字元。再給出 $ n $ 個串 $ T_i $ ，詢問 $ T_i $ 能否與 $ S $ 比對。 $ 1 \le n \le 100, 1 \le |S|,|T_i| \le 10^5, 0 \le $ 通配符個數 $ \le 10. $
$ solution $ ：
總算搞了一道 $ Hash $ 題了，應該算是第一道仔細調了細節的代碼。對于 $ Hash $ 我們有單哈希和多哈希，根據元素資訊的維數來看。但是個人還是喜歡單哈希裡的 $ long~long $ ，效果和雙 $ int $ 哈希差不多。 $ long~long $ 好寫，跑的飛快，但是模數太大容易溢出；雙 $ int $ 哈希（一般用 $ STL:pair $ ），跑的不快，但是正确性高很多。
這道題我們可以采取暴力措施，因為隻有一位可以不同，是以我們幹脆枚舉這一位是哪一位，然後将每個字元串除開這一位的字首和字尾互相比較，如果相同那麼就是合法的一對。字首和字尾的比較可以預處理 $ Hash $ 得到。
期望複雜度： $ O(m\times n\times logn) $
$ code $ ：
const ll mod=20190816170251; //紀念CCF關門的日子是個質數
//小常識：1e18+3和1e18+9都是質數很好記，998244353和998244853和993244853也是。
ll ans;
int n,m,k;
ll q[30005];
ll f[30003][202]; //字首hash
ll s[30003][202]; //字尾hash
char a[30005];
int main(){
n=qr(); m=qr(); k=qr();
for(rg i=1;i<=n;++i){
scanf("%s",a+1); //scanf讀入快一點 //107這個數不要太大，防溢出
for(rg j=1;j<=m;++j) f[i][j]=(f[i][j-1]*107+a[j])%mod; //字首hash
for(rg j=m;j>=1;--j) s[i][j]=(s[i][j+1]*107+a[j])%mod; //字尾hash
} ll x=1; //模數不能太大，否則這裡會炸掉
for(rg i=1;i<=m;++i){ //每個位置分開做會快些，正确性也高一些
for(rg j=1;j<=n;++j)
q[j]=f[j][i-1]*x+s[j][i+1]; //前後合并
sort(q+1,q+n+1);
for(rg j=1,o=1;j<=n;j=++o){
while(q[j]==q[o+1]) ++o; //找到連續一段相同的
ans+=((ll)(o-j+1)*(o-j))>>1; //注意答案貢獻為C[x][2]，從一段中取一對
} x=x*107%mod;
}
printf("%lld\n",ans);
return 0;
} 6. 洛谷 $ P3167 $ ： $ CQOI~2014 $ 通配符比對
題意概括：
給出一個帶通配符的字元串 $ S $ ，通配符分兩種，一種可以比對恰好一個字元，另一種可以比對任意個（包括 $ 0 $ 個）字元。再給出 $ n $ 個串 $ T_i $ ，詢問 $ T_i $ 能否與 $ S $ 比對。 $ 1 \le n \le 100, 1 \le |S|,|T_i| \le 10^5, 0 \le $ 通配符個數 $ \le 10. $
$ solution $ ：
想法頗多，但實作艱巨的一道題，寫了一晚上加一上午。
講課時和 $ Itst $ 讨論覺得是 $ AC $ 自動機，結果大鴿鴿一講是 $ Hash $ ，題解第一篇居然也是 $ Hash $ ？！但是 $ AC $ 自動機本就和 $ Hash $ 完成的東西一樣，都要求兩段子串是否相等， $ AC $ 自動機預處理， $ Hash $ 線上 $ O(1) $ 求，是以同出一源。
首先這道題的突破口是通配符無疑！因為數量太少，我們可以根據通配符劃分模式串，得到不多于 $ 10 $ 個模式串。然後我們可以考慮在給的 $ n $ 個串中找到這些模式串的位置，然後想辦法合并這些位置以判斷是否合法。想法是好的，實作起來卻十分殘酷，首先 $ AC $ 自動機找串複雜度 $ |S|^2 $ ，直接撲街；但是我們很快發現模式串不多，而且隻需要知道其是否在某個位置出現，我們考慮狀壓，每次不暴力通路，直接位運算（期望複雜度 $ O(|S|) $ ）。
然後我們發現實作這個比對是非常難的。但是我們也可以發現比對是線性的按順序的比對，和動态規劃很像，于是我們考慮動态規劃，對每一個位置記錄他可以比對完哪一個的模式串。然後我們對于每一個狀态（某一個位置是某一個模式串的末尾）可以根據這個模式串之前是哪一個通配符來轉移，如果是 $ ? $ 那麼直接找到模式串開頭前一個位置，看它是否比對了上一個模式串；如果是 $ * $ 就找之前所有狀态，是否有比對了上一個模式串的位置（用字首或（位運算）和）。利用狀壓我們可以直接位運算解決所有轉移。
$ code $ ：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int n,m,t;
int s[10005];
int b[10005];
int mx[100005];
int f[100005];
int k[100005];
char a[100005];
struct AC{
int tt;
int end[100005];
int fail[100005];
int son[100005][26];
inline void add(int l,int r,int v){
rg now=0,*to;
for(rg i=l;i<=r;++i){
to=&son[now][a[i]-'a'];
if(*to)now=*to;
else now=*to=++tt;
}end[now]|=(1<<v); //将這個模式串編号狀壓到自動機裡面
}
inline void failed(){
queue<int> q;
for(rg i=0;i<26;++i)
if(son[0][i]){
end[son[0][i]]|=end[0]; //fail樹的應用，這個位置的字元串包含哪些模式串
q.push(son[0][i]);
}
rg *to,next;
while(!q.empty()){
rg i=q.front(); q.pop(); next=fail[i];
for(rg j=0;j<26;++j){
to=&son[i][j];
if(*to){ q.push(*to);
fail[*to]=son[next][j];
end[*to]|=end[son[next][j]]; //fail樹的應用，這個位置的字元串包含哪些模式串
}else *to=son[next][j];
}
}
}
inline void find(int l){ //找到文本串裡每個位置對應哪些模式串末尾
rg now=0; f[0]=end[now];
for(rg i=1;i<=l;++i){
now=son[now][a[i]-'a'];
f[i]=end[now]; //這個位置是那些模式串的末尾
}
}
}T;
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
int main(){
scanf("%s",a+1); m=strlen(a+1); a[++m]='s'; //最後加個字元是為了防通配符在末尾
for(rg i=1,j=1,x=0;i<=m;i=++j){
while(j<=m&&a[j]>='a'&&a[j]<='z')++j; //以通配符為界，劃分為若幹模式串
T.add(i,j-1,++t); s[(1<<t)]=x; b[(1<<t)]=j-i; //記錄上一個通配符是哪一種，以及串長
if(j<=m&&a[j]=='?') x=1; else x=2; //辨識這個通配符是哪一種
}
T.failed(); rg n=qr();
for(rg i=1;i<=n;++i){ //每個待比對串都視為文本串，跑AC自動機
scanf("%s",a+1); m=strlen(a+1);
a[++m]='s'; T.find(m); k[0]=mx[0]=1; //預處理+初始化
for(rg j=1;j<=m;++j) k[j]=mx[j]=0; //初始化
for(rg j=0;j<=m;++j){
for(rg x=f[j];x;x-=x&-x){ //這層循環的複雜度為通配符個數
rg y=x&-x;
if(s[y]==0) k[j]|=y&(k[j-b[y]]<<1); //如果之前沒有通配符
if(s[y]==1) k[j]|=y&(k[j-b[y]-1]<<1); //上一個通配符是?就直接看前面對應位置是否可以比對
if(s[y]==2) k[j]|=y&(mx[j-b[y]]<<1); //上一個通配符是*就直接看全局，因為中間字元可消
mx[j]|=k[j]; //這個對于*操作很重要，記錄這個位置之前的最高比對度
} mx[j+1]=mx[j]; //這個對于*操作很重要，記錄這個位置之前的最高比對度
}
if(k[m]&(1<<t))puts("YES"); //看最後一位的比對度是否達到最高
else puts("NO");
}
return 0;
}
7. 洛谷 $ P3193 $ ： $ HNOI~2008~GT $ 考試
題意概括：
給一個數字串 $ S $ ，求有多少長度為 $ n $ 的數字串 $ T $ 不包含 $ S $ 作為子串。 $ 1 \le |S| \le 100, 1 \le n \le 10^9. $
$ solution $ ：
并沒有想象中（上一道題）的這麼難，唯獨就是要寫嚴格 $ O(1) $ 的 $ kmp $ 算法。感覺比普通的還好寫一點。
首先我們求的串中必須不包含 $ S $ ，這個我們其實不難想到動态規劃。設 $ F[i][j] $ 表示已經構造到第 $ i $ 個位置，在末尾最多有 $ j $ 個位置和 $ S $ 的前 $ j $ 個位置一緻。之是以這樣設狀态是因為我們構造合法串時隻需要知道串後面的字元和 $ S $ 的比對程度，這樣可以知道我們放下一個字元會不會使得一段字尾變為 $ S $ （任何一個子串都可以表示為一個字首的字尾）。然後我們就需要轉移方程，這個其實就是一個 $ kmp $ 的過程。但是為了快速轉移我們需要知道在目前串後面加入某個字元會使比對轉移到哪一個位置！這個需要用嚴格 $ O(1) $ 的 $ kmp $ 算法。再然後我們就可以将這個轉移過程用矩陣來完成，通過改變矩陣系數使得一次轉移等同一次乘法。然後快速幂。
$ code $ ：
int n,m,k;
int nx[105];
int f[105][10];
char a[105];
struct su{ //矩陣
int s[101][101];
inline void operator *=(const su &x){ //矩陣乘法
su res;
for(rg i=0;i<m;++i){
for(rg j=0;j<m;++j){
rg y=0;
for(rg k=0;k<m;++k)
y+=s[i][k]*x.s[k][j];
res.s[i][j]=y%k; //有時候将取模放外面會快些
}
} *this=res;
}
inline su operator ^(int y){ //矩陣快速幂
su res,x=*this;
for(rg i=0;i<m;++i) res.s[i][i]=1;
while(y){
if(y&1)res*=x;
x*=x; y>>=1;
}return res;
}
}ans,xx;
int main(){
n=qr(); m=qr(); k=qr();
scanf("%s",a+1);
ans.s[0][0]=1;
for(rg i=1;i<=m;++i){
nx[i]=f[i-1][a[i]-'0']; //似乎比不嚴格的好寫？
f[i-1][a[i]-'0']=i; //f[i][j]表示從這一位在後面加字元j會比對到哪個位置
for(rg j=0;j<=9;++j) //複雜度比一般kmp高一點
f[i][j]=f[nx[i]][j]; //就是嚴格O(1)的kmp
}
for(rg i=0;i<m;++i)
for(rg j=0;j<=9;++j)
++xx.s[i][f[i][j]]; //加入矩陣系數
ans*=xx^n; int tot=0; //矩陣快速幂
for(rg i=0;i<m;++i)
tot+=ans.s[0][i]; //統計所有不含所給串的串的個數
printf("%d\n",tot%k);
return 0;
}
8. 洛谷 $ P2414 $ $ NOI~2011 $ 阿狸的打字機
題意概括：
給你一棵 $ n $ 個節點的 $ Trie $ 樹， $ q $ 次詢問 $ Trie $ 樹上 $ x $ 節點代表的字元串在 $ y $ 節點代表的字元串中出現了多少次。
$ 1 \le n, q \le 10^6. $
$ solution $ ：
很難的一道題，可以說是很多算法的結合： $ AC $ 自動機， $ fail $ 樹， $ dfs $ 序，樹狀數組
首先是讀入，一般讀入肯定逾時，因為放進 $ AC $ 自動機的字元串很多很長，但是他們很多字首相同。于是根據題意模拟，我們在 $ trie $ 數上跑操作序列，隻要記錄每一個節點的父親，就可以支援加入字元後的撤銷操作，然後列印操作直接在目前 $ trie $ 的節點處打标機即可（詳細見代碼）
然後是關于 $ fail $ 樹，我們對于每一個 $ fail $ 指針件一條反向邊，因為一個節點隻有一個 $ fail $ 指針，得到的圖一定是棵有根樹。然後我們思考這棵樹的意義：（假設每個節點對應一個從根到這個節點的字元串）我們在普通情況下從某個節點（對應字元串 $ S $ ）沿 $ fail $ 指針跑，周遊的字元串都是 $ S $ 的子串且是字尾！于是反過來，我們在 $ fail $ 樹上從某個節點（對應 $ S $ ）周遊其子樹，周遊到的字元串都一定包含 $ S $ 作為子串，且 $ S $ 是它們字尾！
然後我們還知道，一個子串一定可以表示成母串的字首的字尾。于是如果我們要在 $ trie $ 上找 $ x $ 節點代表的字元串在 $ y $ 節點代表的字元串中出現了多少次，我們隻需要将 $ y $ 字元串的每一個字首對應節點（在 $ trie $ 上為到根鍊）都标記，然後在 $ fail $ 樹上的 $ x $ 好節點開始周遊子樹，有多少節點被标記那麼 $ x $ 節點代表的字元串在 $ y $ 節點代表的字元串中出現了多少次。
但是我們發現詢問很多，字元串長度很大。但是我們可以離線：因為字元串的所有字首對應節點在 $ trie $ 上為一條到根的鍊，我們馬上回憶到一種題型（在 $ dfs $ 一棵樹時維護節點到根路徑的資訊：在周遊到某一節點時加入節點貢獻，在離開節點時删掉節點貢獻）。再聯想一下我們需要知道 $ fail $ 的子樹資訊和，我們就可以想到先找到樹的 $ dfs $ 序，用樹狀數組維護以 $ dfs $ 序為對應位置的數組，然後周遊整棵 $ trie $ 樹，在周遊到某一節點時給樹狀數組對應位置加一，在離開節點時減一。然後如果周遊 $ trie $ 樹時，目前節點為詢問中的 $ y $ 字元串（所有字首都以标記），就到樹狀數組裡找到對應詢問 $ x $ 字元串對應位置的子樹和。
$ code $ ：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define rg register int
using namespace std;
int tim;
int n,m,tot;
int a[100005];
int tr[100005];
int dfn[100005];
int low[100005];
int ans[100005];
struct bian{
int to,next;
}b[1000005];
int tou[100005],top;
struct lian{
int to,res,id,next;
}q[100005];
int hd[100005],len;
struct AC{
int tt;
int fa[100005];
int end[100005];
int fail[100005];
int son[100005][26];
bool vis[100005][26];
inline void add(const string &ch){
rg now=0,*to,l=ch.size();
for(rg i=0;i<l;++i){
if(ch[i]>='a'&&ch[i]<='z'){
to=&son[now][ch[i]-'a'];
if(*to) now=*to;
else *to=++tt,fa[*to]=now,now=*to;
}
if(ch[i]=='B') now=fa[now]; //額外計一個父親用來撤銷
if(ch[i]=='P') a[++n]=now;
}
}
inline void failed(){
queue<int> q;
for(rg i=0;i<26;++i){
if(son[0][i]){
fail[son[0][i]]=0;
q.push(son[0][i]);
}
}
rg *to,next;
while(!q.empty()){
rg i=q.front(); q.pop(); next=fail[i];
for(rg j=0;j<26;++j){
to=&son[i][j];
if(*to){ q.push(*to);
fail[*to]=son[next][j];
}else vis[i][j]=1,*to=son[next][j];
} //因為之後需要周遊原始字典樹，是以需要一個vis數組記錄更改
}
}
inline void get_eg(){
for(rg i=1;i<=tt;++i){ rg x=fail[i],y=i;
b[++top]=bian{y,tou[x]}; tou[x]=top;
} //根據fail指針建fail樹的邊（反邊）
}
}ac;
inline int qr(){
register char ch; register bool sign=0; rg res=0;
while(!isdigit(ch=getchar()))if(ch=='-')sign=1;
while(isdigit(ch))res=res*10+(ch^48),ch=getchar();
if(sign)return -res; else return res;
}
inline void add(int x,int v){
for(;x<=tim;x+=x&-x) tr[x]+=v;
} //需要注意樹狀數組的範圍
inline int ask(int x){ rg res=0;
for(;x;x-=x&-x) res+=tr[x];
return res;
}
inline void yu(int i){
dfn[i]=++tim;
for(rg j=tou[i];j;j=b[j].next) yu(b[j].to);
low[i]=tim;
} //有向樹的dfs序，dfn和low記錄子樹區間
inline void dfs(int i){
add(dfn[i],1);
for(rg j=hd[i];j;j=q[j].next){
q[j].res=ask(low[q[j].to])-ask(dfn[q[j].to]-1);
} //用鍊式前向星記錄詢問
for(rg j=0;j<26;++j)
if(ac.son[i][j]&&!ac.vis[i][j])
dfs(ac.son[i][j]);
add(dfn[i],-1);
} //周遊原始字典樹是因為每一個子串都是字首的字尾
//字典樹周遊所有字首，而fail樹的dfs序與字首的字尾有關
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
string ch; getline(cin,ch); ac.add(ch);
ac.failed(); ac.get_eg();
yu(0); m=qr();
for(rg i=1;i<=m;++i){
rg x=a[qr()],y=a[qr()]; //将詢問具體到哪個字元串
q[i]=lian{x,0,i,hd[y]}; hd[y]=i;
} dfs(0);
for(rg i=1;i<=m;++i) ans[q[i].id]=q[i].res;
for(rg i=1;i<=m;++i) printf("%d\n",ans[i]);
return 0;
} 9. 拯救紫萱學姐（試題）
題意概括：
定義對于兩個字元串 $ a $ 和 $ b $ ，如果 $ a $ 既是 $ b $ 的字首也是 $ b $ 的字尾，那麼稱 $ a $ 和 $ b $ 相似（空字元串和任何字元串相似）。一個字元串可以通過編輯變換成一個比它短而且與它相似的字元串，付出的代價為這兩個字元串的長度之差的平方。兩個字元串通過編輯而變為同一個字元串所花費的最小代價被稱為最短編輯距離。現給定一個字元串，你需要知道這個字元串的每一對字首的最短編輯距離中的最大值是多少。
$ 1 \le |S| \le 10^6 $
$ solution $ ：
其實看到 $ a $ 既是 $ b $ 的字首也是 $ b $ 的字尾時，就可以想到 $ kmp $ 思想。然後我們就會發現每一次編輯變換，就是沿着 $ kmp $ 的 $ next $ 數組往前跳。然後為了代價最小，我們肯定每次隻跳一步。于是可以得到一個結論，對于兩個字首他們沿 $ next $ 數組向前跳，第一個相同的位置所對應的字首就是最終狀态（類似于将 $ next $ 數組反向連邊，在樹上跑 $ LCA $ ）。于是我們根據 $ next $ 數組從後往前周遊，每次用目前位置跟新它 $ next[] $ 對應位置的最大代價，同時記錄答案。
$ code $ ：
ll ans;
int n;
int f[2000005];
ll s[2000005];
char a[2000005];
int main(){
scanf("%s",a+1); n=strlen(a+1); f[1]=0;
for(rg i=2,j=0;i<=n;++i){ //kmp
while(j&&a[i]!=a[j+1]) j=f[j];
if(a[i]==a[j+1]) f[i]=++j; //next數組
}
for(rg i=n;i>=1;--i){
ll j=f[i];
ll x=(ll)(i-j)*(i-j); //記錄這一步的代價
ans=max(ans,s[i]+x+s[j]); //更新答案
s[j]=max(s[j],s[i]+x); //更新最大代價
}printf("%lld\n",ans);
return 0;
} 10. 洛谷 $ P3279 $ ： $ SCOI~2013 $ 密碼
題意概括：
給出一個長度為 $ n $ 的數組 $ {p_i} $ 和一個長度為 $ n $ 的數組 $ { q_i } $ ，分别表示以字元串中每個字元以及每兩個相鄰字元的間隙為中心的最長回文串長度。你需要根據給出的 $ { p_i } $ 和 $ {q_i} $ ，構造出一個滿足條件的字元串 $ S $ 。 $ n \le 10^6 $
$ solution $ ：
将 $ manacher $ 倒着做一遍，從前往後構造字元串。
- 因為回文串對稱性質，前面一般直接指派到後面一半。
- 因為回文串對稱性質，我們記錄一個 $ bool $ 數組，回文串的後面第一個字元不能等于回文串前一個字元。
然後貪心放小的字元即可。
$ code $ ：
int n;
int a[1000005];
int b[1000005];
int s[1000005];
bool f[1000005][27];
int main(){
n=qr(); rg r=1; s[0]=26;
for(rg i=1;i<=n;++i)a[i]=qr()>>1; //注意
for(rg i=1;i<n;++i) b[i]=qr()>>1;
for(rg i=1;i<=n;++i){
if(i>=r){ ++r; //貪心放最小的
for(rg j=0;j<26;++j)
if(!f[i][j]){s[i]=j; break;}
} rg x=i-a[i],y=i+a[i]; //記錄邊界
f[y+1][s[x-1]]=1; //後面第一個字元不能等于回文串前一個字元
while(r<=y) s[r]=s[i*2-r],++r;
x=i-b[i]+1,y=i+b[i]; //同上
f[y+1][s[x-1]]=1;
while(r<=y) s[r]=s[i*2-r+1],++r;
}
for(rg i=1;i<=n;++i)
printf("%c",s[i]+'a');
puts("");
return 0;
} 11. \(LOJ~6187~Odd\)
題意概括：
有一個 $ n $ 個數的數組 $ A $ 。求有多少個子區間，滿足每個區間裡出現過的數都隻出現了奇數次。
$ n \leq 2 \times 10^5, a_i \leq 10^6 $
$ solution $ ：
很難調的一道題，細節很多，小技巧也很多。（似乎上一道我這麼認為的題也是分塊？）
我們考慮這道題的“奇偶”二字，說明本題很可能和狀壓、位運算什麼的有關。考場上以為狀壓一下、求個字首異或和、再開個桶就可以解決，奈何資料範圍大、“出現過”三字太毒瘤！但是仔細摸索一番我們不難想到 $ Hash $ 。因為我們要求每個區間，是以很直接的想法就是枚舉一個端點，尋找合法的另一個端點。而要快速知道一個區間内數的奇偶性，我們隻能依靠異或操作，和字尾和（通過異或操作，使得合法區間一定滿足異或和為 $ 0 $ ，這樣根據右端點字尾異或和就能得到左端點字尾異或和，然後查存字尾異或和的桶子就好）
為了能夠友善異或操作，我們給每個值随機一個大數，這樣正确性會很高（總共字尾異或和的數量為 $ n $ 個，值域為 $ 2^{63} $ ，安全）。然後我們枚舉右端點 $ r $ 并實時維護字尾（顯然右端點以右的點的字尾異或和不需要管，因為兩次異或得0）。因為合法區間的異或和為 $ 0 $ 而區間裡的數又是奇數次，是以我們可以忽略每一個數的最後一個。于是當我們右端點向右移時假設下一個數為 $ v_i $ ，那麼對于前面所有字尾，它肯定是裡面等于 $ v $ 的書中最後一個。（假設上一個 $ v $ 出現位置為 $ j $ ）于是從 $ [1,j] $ 的所有字尾均需要異或 $ v $ （ $ [j+1,i] $ 不需要！）。然後因為右端點字尾為 $ 0 $ ，合法區間異或和為零，我們隻需要知道前面有多少位置的字尾異或和為 $ 0 $ 即可！
然後講一下實作，首先我們需要随機 $ rand $ 大數。然後我們需要記錄每一個位置的字尾異或和，并支援區間（某個字首區間）異或修改，以及區間（字首區間）查詢 $ 0 $ 的出現次數！因為值域很大是以我們得考慮 $ Hash $ 表查詢，對于區間修改查詢我們可以線段樹，但是線段樹被卡記憶體了，僅分塊還活着！然後對于區間異或我們可用類似線段樹的 $ lazytag $ 一樣給每個塊打标記！查詢這個塊時有多少0，就是查詢有多少 $ 0~xor~lazytag $ ！（分塊操作有點繞，要仔細分析）
注意 $ Hash $ 表因為分塊的緣故需要支援删除和加入，我們要連結清單删除，回收空間！不能暴力更改，空間會爆！
$ code $ ：
ll ans;
int n,m;
int a[200005];
ll b[1000005]; //随機化權值
ll s[1000005]; //字尾（随着右端點向右移，會變化的字尾）
int t[1000005]; //上一個出現位置
int f[200005]; //分塊
struct Hash{
int tt,top;
ll vv[505]; //數值
int da[505]; //數量
int to[505]; //連結清單指向
int stc[505]; //我删掉的位置（回收棧）
int hd[2005];
inline void add(ll x,int v){
rg y=x%2003; rg i=0; //先Hash一下
for(rg j=hd[y];j;i=j,j=to[j]){ //鍊式前向星存儲
if(vv[j]==x){
da[j]+=v; //更新權值
if(!da[j]){
stc[++top]=j; //計入回收棧
if(!i) hd[y]=to[j]; //連結清單删除
else to[i]=to[j];
} return ;
}
}
i=top?stc[top--]:(++tt); //找到一個沒用的位置
vv[i]=x; da[i]=1; to[i]=hd[y]; hd[y]=i; //存儲
}
inline int ask(ll x){
for(rg j=hd[x%2003];j;j=to[j]) //鍊式前向星通路
if(vv[j]==x) return da[j];
return 0;
}
}ha[505];
ll lz[505];
int main(){
srand(time(NULL)); //随機化
n=qr(); m=sqrt(n-1)+1; //分塊的大小
for(rg i=1;i<=n;++i) f[i]=(i-1)/m+1; //這個下标在哪個塊
for(rg i=1;i<=n;++i) a[i]=qr(),b[a[i]]=rand()+((ll)rand()<<31); //随機權值
for(rg i=1;i<=n;++i){
ha[f[i]].add(0,1); //加入初始值
if(t[a[i]]){ rg x=f[t[a[i]]]; ll v=b[a[i]]; //上一個出現的位置；該位置的随機權值
for(rg j=1;j<x;++j) lz[j]^=v; //塊上打标記
for(rg j=m*(x-1)+1;j<=t[a[i]];++j)
ha[x].add(s[j],-1), s[j]^=v, ha[x].add(s[j],1); //先取出，後修改，再加入
} t[a[i]]=i; //該位置變為最後一個出現位置
for(rg j=1;j<=f[i];++j) ans+=ha[j].ask(lz[j]); //詢問（直接通路大塊就可以了！）
}
printf("%lld\n",ans);
return 0;
} 二、搜尋專題：
$ hncpc~2019E~Numbers $
題意概括：
給一個數字串 $ S $ ，求将其劃分成 $ [0,99] z$ 不含前導零且互不相同的數的方案數。
$ solution $ ：
湖南師範大學的 $ ACM $ 比賽題，沒有 $ source $ 。反正比較簡單，直接口糊。
爆搜，枚舉每個位置是否是小于 $ 10 $ 的位置，其他位置的數就确定了。于是邊搜尋邊 $ check $ 就好了！
題意概括：
$ solution $ ：
$ code $ ：
三、圖論專題：
題意概括：
$ solution $ ：
$ code $ ：
四、資料結構專題：
題意概括：
$ solution $ ：
$ code $ ：
轉載于:https://www.cnblogs.com/812-xiao-wen/p/11600101.html
![goalng nil interface淺析持續學習[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)