


## 一些定义

**字符串**

* $|s|$ 为字符串 $s$ 的长度

* $s_{i}$ 为字符串 $s$ 的中第 $i$ 个字符，$1\le i \le |str|$

* $s[l:r]=s_ls_{l+1}...s_{r-1}s_r$，即 $s$ 区间 $[l,r]$ 的子串

**后缀数组**

我们研究字符串 $s$

* 把$suff_i$ 为字符串 $s$ 的第 $i$ 个后缀，即 $s[i:|s|]$

* 把所有的后缀按字典序排序，$rk_i$ 表示 $suff_i$ 的排名，$sa_i$ 就表示排名为 $i$ 的后缀是字符串 $s$ 的第几个后缀
* $sa_{rk_i}=i$，$rk_{sa_i}=i$

例如，对于 $s=vamamadn$：

| $i$  | $suff_i$ |
| ---- | -------- |
| 1    | vamamadn |
| 2    | amamadn  |
| 3    | mamadn   |
| 4    | amadn    |
| 5    | madn     |
| 6    | adn      |
| 7    | dn       |
| 8    | n        |

| 排名 | $sa_i$ | 对应字符串 |
| ---- | ------ | ---------- |
| 1    | 6      | adn        |
| 2    | 4      | amadn      |
| 3    | 2      | amamadn    |
| 4    | 7      | dn         |
| 5    | 5      | madn       |
| 6    | 3      | mamadn     |
| 7    | 8      | n          |
| 8    | 1      | vamamadn   |

## LCP

LCP：我们定义 $LCP(i,j)$ 为，排名为 $i$ 和排名为 $j$ 的字符串的最长公共前缀，即 $suff_{sa_i}$ 和 $suff_{sa_j}$ 的最长公共前缀

**显然的两条性质**

* $LCP(i,j)=LCP(j,i)$
* $LCP(i,i)=|suff_{sa_i}|=|s|-sa_i+1$

**LCP 引理**
$$
LCP(i,j)=min(LCP(i,k),LCP(k,j))\space\space(1\le i \le k \le j \le |s|)
$$
证明：

令 $p=min(LCP(i,k),LCP(k,j))$，则有 $LCP(i,k)\ge p$ 且 $LCP(k,j)\le p$

设 $suff_{sa_i}=I, suff_{sa_j}=J, suff_{sa_K}=K$

那么就说明 $I$ 和 $K$ 前 $p$ 个字符相等，$K$ 和 $J$ 前 $p$ 个字符相等，所以 $I$ 和 $J$ 前 $p$ 个字符相等，即 $LCP(i,j)\ge p$

然后下面用反证法，假设 $LCP(i,j) p$，那么就有 $I_{p+1}=J_{p+1}$

但是，$min(LCP(i,k),LCP(k,j))=p$，那么就意味要么有 $I_{p+1} \neq K_{p+1}$ 要么有 $K_{p+1}\neq J_{p+1}$，所以不可能会有  $I_{p+1}=J_{p+1}$，假设不成立。

因此 $LCP(i,j)=p=min(LCP(i,k),LCP(k,j))$

**LCP定理**
$$
LCP(i,j)=MIN_{k=i+1}^{j}(LCP(k,k-1))
$$
证明：

我们把 $i$ 到 $j$ 拆成 $i$ 到 $i+1$ 到 $i+1$ 到 $j$，应用 LCP引理，则有 $LCP(i,j)=min(LCP(i,i+1),LCP(i+1,j))$

我们把 $i+1$ 到 $j$ 再拆，这么递归拆下去，就证明了上式

**hight引理**

令 $hight_i=LCP(i,i-1)$，$2\le i \le n$。特别地，定义 $hight_1=0$。$hight_i$ 可以看作排名为 $i$ 的后缀与排名为 $i-1$ 的后缀的最长公共前缀长度

令 $h_i=height_{rk_i}$，$h_i$ 可以看作第 $i$ 个后缀与和他排名紧挨着靠前的那个后缀的最长公共前缀长度

然后有
$$
h_i\ge h_{i-1}-1
$$
证明：

如果第 $i-1$ 个后缀与排名为 $rk_{i-1}-1$ 的后缀之间没有公共前缀，那么 $h_{i-1}=0$，而 $h_i$ 必然为非负数，那么上式成立

反之，我们假设排名为 $rk_{i-1}-1$ 的后缀是第 $k$ 个后缀。那么第 $i$ 个后缀是第 $i-1$ 个后缀去掉首字母得到的，第 $k+1$ 个后缀是第 $k$ 个后缀去掉首字母得到的。且由于第 $k$ 个后缀的排名比第 $i-1$ 个后缀的排名靠前，则第 $k+1$ 个后缀的排名也应该比第 $i$ 个后缀的排名靠前，并且两者的最长公共前缀，即 $LCP(rk_i,rk_{k+1})=h_{i-1}-1$

然后我们考虑，两个排名紧挨着的后缀的最长公共前缀应该是最大的。第 $k+1$ 个后缀的排名不一定紧挨着第 $i$ 个后缀的排名，排名可能要更靠前一点。那么此时我们的 $h_i$ 就表示的是和第 $i$ 个后缀和紧挨着第 $i$ 个后缀的后缀的 LCP，必然有 $h_i\ge LCP(rk_i,rk_{k+1})=h_{i-1}-1$，证毕

**求LCP**

由LCP定理可知 $LCP(i,j)=min(height_k)$，$i+1\le k\le j$

而由 $h_i$ 的定义，我们可以得到 $height_i=h_{sa_i}$

然后我们可以借助 $height$ 引理，先求出 $h$ ，来求出 $height$

具体代码见题目部分

## 题目

### P3809 【模板】后缀排序

https://www.luogu.com.cn/problem/P4051

求后缀数组的板子题

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 1000006
char s[_];
int n,cnt[_],m,rk[_  1],sa[_],nd[_],oldrk[_  1];
inline void SA(){
    m=300;//设定字符值域
    for(int i=1;i =n;i++) ++cnt[rk[i]=s[i]]; //先来一波基数排序
    for(int i=1;i =m;i++) cnt[i]+=cnt[i-1];
    for(int i=n;i =1;i--) sa[cnt[rk[i]]--]=i;
    for(int p=0,k=1;k n;k  =1,p=0){
        for(int i=n;i =n-k+1;i--) nd[++p]=i;//后半截空串，第二关键字肯定排名考前
        for(int i=1;i =n;i++) if(sa[i] k) nd[++p]=sa[i]-k;//通过上回的整体排名，推本次的后半截排名
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i =n;i++) ++cnt[rk[nd[i]]];//再根据第一关键字排名，第一关键字就是上次的整体排名
        for(int i=1;i =m;i++) cnt[i]+=cnt[i-1];
        for(int i=n;i =1;i--) sa[cnt[rk[nd[i]]]--]=nd[i];
        swap(rk,oldrk);m=0;//更新排名
        for(int i=1;i =n;i++) rk[sa[i]]=(m+=((oldrk[sa[i]]==oldrk[sa[i-1]]    oldrk[sa[i]+k]==oldrk[sa[i-1]+k])?0:1));
    }
}
inline void subtask(){
    cin  (s+1);n=strlen(s+1);
    SA();
    for(int i=1;i =n;i++) cout  sa[i]  ' ';
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

### P4051 [JSOI2007] 字符加密

https://www.luogu.com.cn/problem/P4051

**题目描述**

JS 同学把需要加密的信息排成一圈，显然，它们有很多种不同的读法。

例如‘JSOI07’，可以读作：  JSOI07 SOI07J OI07JS I07JSO 07JSOI 7JSOI0 把它们按照字符串的大小排序： 07JSOI 7JSOI0 I07JSO JSOI07 OI07JS SOI07J 读出最后一列字符：I0O7SJ，就是加密后的字符串。你能写一个程序完成这个任务吗？

**数据范围**

$1\le n \le 10^5$

**笔记**

断环成链，即把原串复制一遍，然后跑 SA。取 SA 中编号小于等于 $n$ 的后缀。

```cpp
inline void subtask(){
    cin  s+1,n=strlen(s+1);
    for(int i=1;i =n;i++) s[i+n]=s[i];
    n  =1;
    SA();
    for(int i=1;i =n;i++){
        if(sa[i] (n  1)) continue;
        cout  s[sa[i]+(n  1)-1];
    }
}
```

### SUBST1 - New Distinct Substrings

https://www.luogu.com.cn/problem/SP705

**题目数据**

$T$ 组数据，每次给定一个字符串 $s$，求该字符串本质不同的子串数量。

两个子串本质不同，当且仅当两个子串长度不等，或长度相等但有任意一位不同。

**数据范围**

$1\le T \le 20$，$1\le |s|\le 50000$

**笔记**

我们发现如果存在两个本质相同的子串，那么这两个子串一定是某两个后缀的公共前缀，而且这两个后缀的排名接近

于是我们考虑按排名的顺序逐个添加后缀。考虑添加后缀 $sa_i$ 后对本质不同子串数量的影响。增加的子串数量即为后缀 $sa_i$ 的长度，其中有 $LCP(i,i-1)$ 个子串是已经在添加后缀 $sa_{i-1}$ 的时候已经算进去了，需要减掉。

于是答案即为：
$$
\frac{n(n+1)}{2}-\sum_{i=1}^n height_i
$$
求 height 数组的模板

```cpp
void LCP(){
    int k=0;//表示h数组
    for(int i=1;i =n;i++){
        if(rk[i]==1) continue;//hight[1]=0;
        if(k) k--;//h[i] =h[i-1]-1
        int j=sa[rk[i]-1];//排名紧靠前的后缀
        while(i+k =n  j+k =n  s[i+k]==s[j+k]) k++;
        height[rk[i]]=k;//h[i]=height[rk[i]]
    }
}
```

```cpp
inline void subtask(){
    cin  s+1,n=strlen(s+1);
    SA();LCP();
    int sum=0;
    for(int i=1;i =n;i++) sum+=height[i];
    cout  n*(n+1)/2-sum  endl;
}
```

### LCS - Longest Common Substring

https://www.luogu.com.cn/problem/SP1811

**题目描述**

给定两个字符串，求最长公共子串长度，长度不超过 $2.5\times 10^5$

**笔记**

把两个字符串首尾拼接起来，中间加一个分隔符，于是答案即为
$$
\max_{1\le i \le |S_1| j\le |S_1+S_2|} LCP(rk_i,rk_j)
$$
因为我们加了个特殊分割符，所以正确性是能保证的

不过直接暴力枚举 $i$ ，$j$ 的话时间复杂度还是太大了。实际上我们考虑，排名紧挨着的字符串的 LCP 是最大的，所以我们直接找后缀起始点分处于两个字符串的 height 的值的最大值即可

不过可能还有一个问题：有可能排名为 $i$ 和 $i-1$ 的后缀的起始点在同一字符串，而排名 $i$ 和 $i-2$ 的后缀不在同一字符串，且这两个后缀的 LCP 也不小，那么我们不就忽略掉了

我们可以这么考虑，两个字符串的公共部分起始点构成的后缀，排名要么紧挨着，于是上述算法成立。排名也可能不紧挨着，如果不紧挨着的话，排名位于中间的后缀也包含这个公共部分。这些后缀中必然会有起始点来自不同的字符串的，于是这两个后缀的 LCP 应该是另一个 $height$，我们上述做法也没问题

```cpp
inline void subtask(){
    cin  s+1,n=strlen(s+1);s[n+1]='$';
    int n1=n;
    cin  s+n+2,n=strlen(s+1);
    SA();LCP();
    int ans=-inf;
    for(int i=1;i =n;i++){
        if(rk[i]==1) continue;
        int j=sa[rk[i]-1];
        if((i =n1  j =n1+2)||(i =n1+2  j =n1)) ans=max(ans,height[rk[i]]);
    }
    cout  ans;
}
```

### P4248 [AHOI2013] 差异

https://www.luogu.com.cn/problem/P4248

**题目描述**

给定一个长度为 $n$ 的字符串 $S$，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求

$$\displaystyle \sum_{1\leqslant i j\leqslant n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j)$$

其中，$\text{len}(a)$ 表示字符串 $a$ 的长度，$\text{lcp}(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。

**数据范围**

对于 $100\%$ 的数据，保证 $2\le n\le 500000$，且 $S$ 中均为小写字母。

**笔记**

结合公式 $\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{2}$上述式子可以变为
$$
\frac{n(n-1)(n+1)}{2} - 2\sum_{1\le i j\le n} LCP(i,j)
$$
后面那部分我们可以考虑使用线段树来做。具体来说就是维护求和以及取 min 操作

首先一个想法是可以使用吉司机线段树来做。不过我们考虑 $height$ 数组的值域不大，也可以使用权值线段树，对 $x$ 取 min 的时候就是先计算有几个值比 $x$ 大，然后把这些值的数量归到 $x$ 的数量

线段树还是太吃操作了。我们进一步考虑，后面那部分也可以视为 $height$ 数组的所有子区间的最小值加和

这是经典问题，可以使用单调栈来做

```cpp
int sta[_],top,l[_],r[_];
inline void subtask(){
    cin  s+1;n=strlen(s+1);
    SA();
    //for(int i=1;i =n;i++) debug(height[i]);
    sta[top=1]=1;
    for(int i=2;i =n;i++){
        while(top  height[sta[top]] height[i]){
            r[sta[top]]=i;
            top--;
        }
        l[i]=sta[top];
        sta[++top]=i;
    }
    while(top) r[sta[top--]]=n+1;
    //for(int i=1;i =n;i++) debug(l[i]),debug(r[i]);
    int ans=n*(n+1)/2*(n-1);
    for(int i=2;i =n;i++) ans-=2*(i-l[i])*(r[i]-i)*height[i];
    cout  ans;
}
```

### P3181 [HAOI2016] 找相同字符

https://www.luogu.com.cn/problem/P3181

**题目描述**

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。

**数据范围**

$1\le n_1,n_2\le 2\times 10^5$，字符串中只有小写字母。

**笔记**

把两个字符串首尾相接，然后就转为求所有后缀起点位于不同字符串的 LCP 之和

这个和上一题类似，不过这题对后缀有限制要求了

我们可以考虑容斥，先把拼接后的整个的字符串的所有后缀组合 LCP 求出来，然后再减去后缀起点位于同一字符串的所有组合的 $LCP$ ，即得到答案了

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 400005
char s1[_],s2[_],s[_];
int n1,n2,n,m,cnt[_],nd[_],sa[_],rk[_  1],oldrk[_  1],height[_],l[_],r[_],sta[_],top;
int SA(){
    m=300;
    memset(cnt,0,sizeof(cnt));
    for(int i=1;i =n;i++) ++cnt[rk[i]=s[i]];
    for(int i=1;i =m;i++) cnt[i]+=cnt[i-1];
    for(int i=n;i =1;i--) sa[cnt[rk[i]]--]=i;
    for(int p=0,k=1;k n;k  =1,p=0){
        for(int i=n;i =n-k+1;i--) nd[++p]=i;
        for(int i=1;i =n;i++) if(sa[i] k) nd[++p]=sa[i]-k;
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i =n;i++) ++cnt[rk[nd[i]]];
        for(int i=1;i =m;i++) cnt[i]+=cnt[i-1];
        for(int i=n;i =1;i--) sa[cnt[rk[nd[i]]]--]=nd[i];
        swap(rk,oldrk);m=0;
        for(int i=1;i =n;i++) rk[sa[i]]=(m+=((oldrk[sa[i]]==oldrk[sa[i-1]]    oldrk[sa[i]+k]==oldrk[sa[i-1]+k])?0:1));
    }
    int k=0;
    for(int i=1;i =n;i++){
        if(rk[i]==1) continue;
        if(k) k--;
        int j=sa[rk[i]-1];
        while(i+k =n  j+k =n  s[i+k]==s[j+k]) k++;
        height[rk[i]]=k;
    }
    sta[top=1]=1;
    for(int i=2;i =n;i++){
        while(top  height[sta[top]] height[i]) r[sta[top--]]=i;
        l[i]=sta[top];
        sta[++top]=i;
    }
    while(top) r[sta[top--]]=n+1;
    int res=0;
    for(int i=2;i =n;i++) res+=(i-l[i])*(r[i]-i)*height[i];
    return res;
}
inline void subtask(){
    cin  s1+1;n1=strlen(s1+1);
    cin  s2+1;n2=strlen(s2+1);
    int ans=0;
    for(int i=1;i =n1;i++) s[i]=s1[i];
    s[n1+1]='$';
    for(int i=1;i =n2;i++) s[i+n1+1]=s2[i];
    n=n1+n2+1;
    ans+=SA();
    for(int i=1;i =n1;i++) s[i]=s1[i];
    n=n1;
    ans-=SA();
    for(int i=1;i =n2;i++) s[i]=s2[i];
    n=n2;
    ans-=SA();
    cout  ans;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```









## GSS1 - Can you answer these queries I

线段树

https://www.luogu.com.cn/problem/SP1043

**题目描述**

给 $n$ 个数字，$m$ 个询问，每次询问给定区间的最大字段和，$1\le n,m\le 5\times 10^4$

**笔记**

一上来口胡了个分治做法，用主定理分析了一下发现时间复杂度好像是 $O(mn\log n)$ 的（）

实际上维护区间前缀和最大值、后缀和的最大值、区间和、区间内最大字段和就好了

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define nt tree[k]
#define lt tree[ls(k)]
#define rt tree[rs(k)]
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 50004
int in[_],n,m;
struct Node{int lmax,rmax,sum,seg;} tree[_  2];
inline Node merge(Node l,Node r){
    Node res;
    res.sum=l.sum+r.sum;
    res.lmax=max(l.lmax,l.sum+r.lmax);
    res.rmax=max(r.rmax,r.sum+l.rmax);
    res.seg=max(max(l.seg,r.seg),l.rmax+r.lmax);
    return res;
}
void build(int k,int l,int r){
    if(l==r) return nt.lmax=nt.rmax=nt.sum=nt.seg=in[l],void();
    int mid=(l+r)  1;
    build(ls(k),l,mid);
    build(rs(k),mid+1,r);
    nt=merge(lt,rt);
}
Node query(int k,int l,int r,int x,int y){
    if(l =x  r =y) return nt;
    int mid=(l+r)  1,flag=false;
    Node res;
    if(x =mid) res=query(ls(k),l,mid,x,y),flag=true;
    if(y mid){
        Node rson=query(rs(k),mid+1,r,x,y);
        if(!flag) res=rson;
        else res=merge(res,rson);
    }
    return res;
}
inline void subtask(){
    cin  n;for(int i=1;i =n;i++) cin  in[i];cin  m;
    build(1,1,n);
    while(m--){
        int l,r;cin  l  r;
        cout  query(1,1,n,l,r).seg  endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

## D - M =ab

数学、枚举

https://atcoder.jp/contests/abc296/tasks/abc296_d

**题目描述**

找到两个正整数 $a$ 和 $b$ 满足 $a,b\le n$ 且 $a\times b\ge m$

**笔记**

上来先对 $m$ 开根，然后以为 $a$ 和 $b$ 必然全都大于等于 $\sqrt{m}$，wa了两发，发现忘记了可能一个数很小但另一个数很大

然后发现这是经典讨论题，往往需要枚举一个，且枚举花费的时间复杂度是可以接受的。于是这题只需要枚举 $a$，然后求出最小的 $b$，再看看满不满足条件即可

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
inline int exsqrt(int x){
    int r=sqrt(x);
    while((r+1)*(r+1) =x) r++;
    while((r-1)*(r-1) =x) r--;
    return r;
}
inline void subtask(){
    int n,m;cin  n  m;
    if(n =1000000  n*n m) return cout  -1,void();
    int r=exsqrt(m);
    if(r*r==m) return cout  m,void();
    int ans=inf;
    for(int i=1;i =r+1;i++){
        if(m%i==0){
            if(m/i =n) return cout  m,void();
        }else if((m/i+1) =n) ans=min(ans,i*(m/i+1));
    }
    cout  ans;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

## Nearest vectors

https://codeforces.com/problemset/problem/598/C

**题目描述**

给你 $n(1\le n \le 10^5)$ 个点，然后让你求出所有原点到这个点的向量中夹角最小的那个

**笔记**

先进行极角排序，然后逐个求夹角就可以了

但关键是怎么搞出最小夹角出来

朴素使用点乘求夹角，然后再比较，会有精度损失，只能过 32 个点

开 long double，精度好一点，但只能过 103 个点

我们再卡一卡，把所有坐标乘 1000，有效果，但也只能过 104 个点

搜题解，得知了一种无精度损失的比较夹角的方法：

对于一个角，我们将其旋转，使一条边与 X 轴平行。假设角度为 $\theta$，另一条边向量模长为 $v$，则旋转后的点为 $(v\cos \theta, v \sin \theta)$

我们发现，这两个坐标再同时乘上已经与 X 轴平行的边的模长后，横坐标就变成了点乘，纵坐标就变成了叉乘。而同时乘上一个数是不会改变其与 X ，即原来的边的夹角

对于另外一个角也进行上述操作，于是就转变为判断两个向量，哪个向量与 X 轴夹角更小一点，可以使用叉乘判断

```cpp
//判断OA1和OB1之间的夹角是不是比OA2和OB2之间的夹角更小
inline bool angle_less(Point a1,Point b1,Point a2,Point b2){
    Point t1(a1*b1,abs(a1^b1)),t2(a2*b2,abs(a2^b2));
    return (t1^t2) 0;
}
```

## P3349 [ZJOI2016] 小星星

https://www.luogu.com.cn/problem/P3349

**题目描述**

给出一个包含 $n$ 个点的树，以及 $n$ 个点 $m$ 条边的图。现在你需要给这个树每个点分配一个序号，分配的应该为 $n$ 的排列。分配后需要满足如果两个点在树上有连边，那么也应该在图上有连边。求分配方案数

**数据范围**

$1\le m\le 17$

**笔记**

考虑 dp，dp 的时候，为了保证分配序号时不会分配重复，我们就遇到了后效性的问题。解决后效性可以把有后效性的因素放到状态里，于是我们可以设 $dp[x][i][S]$ 表示给 $x$ 点分配序号 $i$ ，其子节点分配序号集合为 $S$ 时的方案数。但这样大力 dp 的时间复杂度太高

考虑放松限制。如果我们不必让分配的序号满足是一个排列，那么 dp 就可以变为 $dp[x][i]$。但这样算出来的方案中，可能存在两点分配的序号是相同的。此时就可以考虑容斥了，我们枚举 $\{1,...,n\}$ 的子集 $S$。令 $dp[x][i]$ 表示配分在集合 $S$ 中的序号时的方案数。我们计算出 $|S|=n$ 时方案数，减去 $|S|=n-1$ 时方案数，加上 $|S|=n-2$ 时方案数，即可得到答案

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
int now,dp[18][18],n,m;
vector int  ve[18],ma[18];
void dfs(int x,int fa){
    for(int i=1;i =n;i++) if((now (1  (i-1)))) dp[x][i]=1;
    for(auto to:ve[x]){
        if(to==fa) continue;
        dfs(to,x);
        for(int i=1;i =n;i++){
            if(!(now (1  (i-1)))) continue;
            int s=0;
            for(auto j:ma[i]){
                if(!(now (1  (j-1)))) continue;
                s+=dp[to][j];
            }
            dp[x][i]*=s;
        }
    }
}
inline int popcnt(int x){
    int res=0;
    while(x){
        if(x 1) res++;
        x  =1;
    }
    return res;
}
inline void subtask(){
    cin  n  m;
    for(int i=1;i =m;i++){
        int u,v;cin  u  v;
        ma[u].push_back(v);
        ma[v].push_back(u);
    }
    for(int i=1;i n;i++){
        int u,v;cin  u  v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    int ans=0;
    for(now=1;now (1  n);now++){
        memset(dp,0,sizeof(dp));
        dfs(1,1);
        int tmp=0;
        for(int i=1;i =n;i++){
            if(!(now (1  (i-1)))) continue;
            tmp+=dp[1][i];
        }
        //debug(now);debug(tmp);
        if((n-popcnt(now))%2) ans-=tmp;
        else ans+=tmp;
    }
    cout  ans;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

## P6628 [省选联考 2020 B 卷] 丁香之路

https://www.luogu.com.cn/problem/P6628

贪心+欧拉路+最小生成树

**题目描述**

求 $s$ 到 $i(1\le i \le n)$  的最短路，要求必须经过指定的 $m$ 条边，至少经过一次。点 $x$ 到点 $y$ 的距离为 $|x-y|$ 

**数据范围**

$1\le n \le 2500$

保证 $1\le s\le n$；保证 $m\le \frac {n(n-1)}2$

**笔记**

如果若有的边都恰好走一次，那么就很像欧拉路问题了。现在所有的边可以不止经过一次，那么我们可以考虑加入一些重复边，转化为欧拉路问题。

我们知道，只要度数均为偶数，那么一定存在欧拉路，于是我们现在只需要想办法加入一些边，让所有的点的度数变成偶数

由于欧拉路还需要两个度数是奇数的点，不太好处理。我们考虑给起点和终点连接一条边权，此时就转为了欧拉回路了

因为题目还要求是最短路，因此我们加入的边权之和应最小

首先考虑将边的度数变成偶数，我们把点的编号从小到大排序，然后直接给相邻的两个度数为奇数的点连边就可以了。仔细思考原图的性质，能够发现度数为奇数的点一定有偶数个，可以两两配对

然后现在我们还面临着连通性的问题。在上面将边的度数变成偶数的连边过程中，对于点 $u$ 和 $v$，$u v$，我们不去直接将他俩连边，而是选择连接 $(u,u+1)$、$(u+1,u+2)$、......、$(v-1,v)$。这样的话，产生的边权还是一样的，中间的点因为多连了两条边，度数的奇偶性没有发生变化，但是我们多把一些点连接了起来，感性上可以发现能够让连通性变得更强一点。

但还是可能有连通块之间没有连通。我们考虑把涉及到的这些点编号从小到大排序，然后两两连边，跑最小生成树，以最小的代价将整个图连通。值得注意的是跑最小生成树时建边时应该建两个重复的边，来保持度数是偶数。

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 2502
inline int dis(int u,int v){return abs(u-v);}
struct UFS{
    int fa[_],n;
    UFS(int n){for(int i=1;i =n;i++) fa[i]=i;this- n=n;}
    UFS(const UFS  old){
        n=old.n;
        for(int i=1;i =old.n;i++) fa[i]=old.fa[i];
    }
    int find(int x){while(x!=fa[x]) x=fa[x]=fa[fa[x]];return x;}
    void merge(int x,int y){fa[find(x)]=find(y);}
};
set int  se;
int de1[_],de2[_],n,m,s;
struct Edge{int u,v,w;} edge[_];
int solve(UFS u2,int x){
    for(int i=1;i =n;i++) de2[i]=de1[i];
    de2[s]++,de2[x]++;
    int res=0,las=0,pre=0,cnt=0;
    for(auto it=se.begin();it!=se.end();it++){
        int now=*it;
        if(it!=se.begin()) edge[++cnt]={las,now,dis(las,now)};
        las=now;
        if(de2[now]%2==0) continue;
        else if(!pre) pre=now;
        else{
            res+=dis(pre,now);
            for(int i=pre+1;i =now;i++) u2.merge(i-1,i);
            pre=0;
        }
    }
    sort(edge+1,edge+cnt+1,[](Edge x,Edge y){return x.w y.w;});
    for(int i=1;i =cnt;i++){
        int u=edge[i].u,v=edge[i].v;
        if(u2.find(u)==u2.find(v)) continue;
        res+=2*edge[i].w;
        u2.merge(u,v);
    }
    return res;
}
inline void subtask(){
    cin  n  m  s;se.insert(s);
    UFS u1(n);
    int base=0;
    for(int i=1;i =m;i++){
        int u,v;cin  u  v;
        se.insert(u),se.insert(v);
        de1[u]++,de1[v]++;
        base+=dis(u,v);
        u1.merge(u,v);
    }
    for(int i=1;i =n;i++){
        se.insert(i);
        cout  base+solve(u1,i)  " ";
        if(!de1[i]  i!=s) se.erase(i);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```











## 语法知识

### 声明与初始化

头文件：` bitset `

声明方法：`std::bitset N  s;`

开在全局时，默认全为 0；**开在局部时无法保证，需要使用 reset 函数清空**。

可以使用字符串来初始化：

```cpp
std::bitset 8  s(std::string("00110101"));
```

注意，字符串最右边的数字是低位，也就是上述赋值后的结果为：

| 下表 | 0    | 1    | 2    | 3    | 4    | 5    | 6    | 7    |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 值   | 1    | 0    | 1    | 0    | 1    | 1    | 0    | 0    |

### 修改与运算

直接下标修改 `s[pos]=x;` ，时间复杂度 $O(1)$

支持左右位移、与、或、异或，返回一个 bitset，如 `std::bitset N  k=s  x;` ，时间复杂度 $O(\frac{N}{w})$，$w$ 为计算机字长，可以视为 $64$。右移是逻辑右移。

### 输入输出

可以与 cin 和 cout 一块使用。还是注意字符串最右边的数字是低位。cout 时会自动补 0

```cpp
cin  s;		// 1101
cout  s;	// 000001101
```

### 成员函数

* `reset()`：全部置为 0
* `to_string() -  string`：转为 string，高位补 0
* `to_ulong() -  unsigned int`：转为 unsigned int ，溢出的话会 re
* `to_ullong() -  unsigned long long`：转为 unsigned long long，溢出的话会 re
* set
  * `set()`：全部置为 1
  * `set(int index,bool value = true)`：将下标为 index 的位置置为 value

* `test(int index) -  bool`：返回 index 位置的值
* `any() -  bool`：如果 bitset 内有 1 ，则返回 true，反之返回 false
* `none() -  bool`：如果 bitset 内有 1，则返回 false，反之返回 true
* `count() -  unsigned int`：返回 bitset 内 1 的个数，注意是无符号
* flip
  * `flip()`：所有位取反
  * `flip(int index)`：指定位置按位取反

以上操作的单点操作都为 $O(1)$，整体操作都为 $O(\frac{N}{w})$

## 题目

### P1537 弹珠

https://www.luogu.com.cn/problem/P1537

**题目描述**

给出六个非负整数 $N_1,\cdots,N_6$，其中 $N_i$ 是价值为 $i$ 的弹珠的个数。最大弹珠总数将达到 $2\times 10^4$。判断能否把这些弹珠分成价值相等的两份。

**笔记**

显然可以直接多重背包做。

现在考虑 01 背包，朴素的 01 背包会超时，但我们可以使用 bitset 优化

转移方程：$f_j = f_j | f_{j-w_i}$，倒序枚举 $w_i$

我们发现这个方程相当于把一个 01 串左移 $w_i$ 位再与原 01 串取或

我们把 $f$ 视为一个 bitset，则转移可以写成 $f|=f  w_i$

时间复杂度 $O(\frac{n}{w}\sum w_i)$

```cpp
#include bits/stdc++.h 
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
#define _ 120004
typedef pair int,int  pii;
int in[7];
signed main(){
    //ios::sync_with_stdio(false);
    int now;
    while(true){
        int sum=0;now++;
        for(int i=1;i =6;i++) scanf("%d", in[i]),sum+=i*in[i];
        if(!sum) break;
        printf("Collection #%d:\n",now);
        if(sum%2){
            printf("Can't be divided.\n\n");
            continue;
        }
        bitset _  s;s.reset();s.set(0);
        for(int i=1;i =6;i++){
            for(int j=1;j =in[i];j++){
                s|=(s  i);
            }
        }
        if(s.test(sum/2)) printf("Can be divided.\n\n");
        else printf("Can't be divided.\n\n");
    }
    return 0;
}
```

### P5020 [NOIP 2018 提高组] 货币系统

https://www.luogu.com.cn/problem/P5020

**题目描述**

在一个完善的货币系统中，每一个非负整数的金额 $x$ 都应该可以被表示出。然而， 货币系统可能是不完善的。例如在货币系统 $n=3$, $a=[2,5,9]$ 中，金额 $1,3$ 就无法被表示出来。 

两个货币系统 $(n,a)$ 和 $(m,b)$ 是等价的，当且仅当对于任意非负整数 $x$，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。 

现在网友们打算简化一下货币系统。他们希望找到一个货币系统 $(m,b)$，满足 $(m,b)$ 与原来的货币系统 $(n,a)$ 等价，且 $m$ 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 $m$。

有多组测试数据。

**数据范围**

 $T ≤ 20, n \le 100, a_i \le 25000$。

**笔记**

先去重，然后从小到大排序。如果这 $n$ 个数中，一个数已经能被前面的数组合出来，那么这个数就可以去掉了。是一个完全背包问题。时间复杂度 $O(n\times max\{a_i\})$

完全背包也可以使用 bitset 优化。

对于一个物品 $a_i$，我们枚举这个物品的个数 $k$，转移方程即为 $f_j |= f_{j-k\times a_i}$ 。将 dp 数组视为一个 bitset，则有 $f|=f  (k\times a_i)$。

然后我们进一步考虑：

$k=1$ 时相当于 $f$ 和 $f    a_i$ 按位或。

$k=2$ 时相当于 $f$ 、$f  a_i$ 、$f  2a_i$、$f  3a_i$ 异或。

发现 $k=3$ 是不需要枚举的，因为 $k=1$ 和 $k=2$ 的结果叠加了。同理 $k=5$ 可以由 $k=1$ 和 $k=4$ 的结果叠加。我们发现只需要枚举 $2$ 的幂次即可。

总的时间复杂度 $O(n\times log(max\{a_i\})\times \frac{max\{a_i\}}{w})$，优化了一点。

```cpp
#include bits/stdc++.h 
#define int long long
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
int in[101];
inline void subtask(){
    int n,mx=-1;cin  n;
    int ans=n;
    for(int i=1;i =n;i++) cin  in[i],mx=max(mx,in[i]);
    sort(in+1,in+n+1);
    bitset 25001  s;s.reset();s.set(0);
    for(int i=1;i =n;i++){
        if(s.test(in[i])){
            ans--;
            continue;
        }
        int x=in[i];
        while(x =mx){
            s|=(s  x);
            x*=2;
        }
    }
    cout  ans  endl;
}
signed main(){
    ios::sync_with_stdio(false);
    int t;cin  t;
    while(t--) subtask();
    return 0;
}
```

### P3674 小清新人渣的本愿

https://www.luogu.com.cn/problem/P3674

**题目描述**

$n$ 个数，$m$ 个操作：

1. 询问区间内是否存在两个数（可为同一个数）相加为 $x$
2. 询问区间内是否存在两个数（可为同一个数）相减为 $x$
3. 询问区间内是否存在两个数（可为同一个数）相乘为 $x$

**数据范围**

$n,m\le 10^5, max(x,a_i)\le 10^5$

**笔记**

没有修改，仅查询，支持离线，考虑莫队。考虑使用 bitset 维护：

* 操作一：

如果询问是否存在 $a$ 和 $b$ 满足 $a-b=x$ ，即判断是否存在 $a=b+x$。我们令 bitset $s1$ 维护某个数是否存在，那么只需要看一下 $s1\ (s1  x)$ 是否存在 1 即可。

* 操作二：

如果沿用上述的方法，需要判断 $a=x-b$ 是否存在，直接用 $s1$ 无法实现，因为 $b$ 前面有一个负号。我们可以考虑维护 $-b$，但是 bitset 只能维护非负数，所以我们改为维护 $N-b$，其中 $N$ 为值域上限，用 bitset $s2$。

于是转化为判断 $a=(N-b)-N+x$ 是否存在，那么只需要看一下 $s1\ (s2  (N-x))$ 是否存在 1 即可。

* 操作三：

可以用 $O(\sqrt{x})$ 的时间暴力枚举 $x$ 的因数 $d$，然后判断 $d$ 和 $\frac{x}{d}$ 是否都存在即可。

```cpp
#include bits/stdc++.h 
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 100005
const int N=100000;
int a[_],blo,bl[_],bu[_];
struct Q{int l,r,id,op,x,ans;} q[_];
bitset _  s1,s2;
inline void add(int x){
    bu[a[x]]++;
    if(bu[a[x]]==1) s1.set(a[x]),s2.set(N-a[x]);
}
inline void del(int x){
    bu[a[x]]--;
    if(bu[a[x]]==0) s1.set(a[x],0),s2.set(N-a[x],0);
}
inline void subtask(){
    int n,m;cin  n  m;
    blo=sqrt(n);
    for(int i=1;i =n;i++) cin  a[i],bl[i]=(i-1)/blo+1;
    for(int i=1;i =m;i++) cin  q[i].op  q[i].l  q[i].r  q[i].x,q[i].id=i;
    sort(q+1,q+m+1,[](Q x,Q y){return bl[x.l]==bl[y.l]?x.r y.r:bl[x.l] bl[y.l];});
    int l=1,r=0;
    for(int i=1;i =m;i++){
        while(l q[i].l) del(l++);
        while(l q[i].l) add(--l);
        while(r q[i].r) add(++r);
        while(r q[i].r) del(r--);
        if(q[i].op==1) q[i].ans=(s1 (s1  q[i].x)).any();
        else if(q[i].op==2) q[i].ans=(s1 (s2  (N-q[i].x))).any();
        else if(q[i].op==3){
            for(int j=1;j*j =q[i].x;j++){
                if(q[i].x%j) continue;
                q[i].ans=s1[j] s1[q[i].x/j];
                if(q[i].ans) break;
            }
        }
    }
    sort(q+1,q+m+1,[](Q x,Q y){return x.id y.id;});
    for(int i=1;i =m;i++) cout  (q[i].ans?"hana":"bi")  endl;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

::: warn 踩坑

add 那里要写成 `if(bu[a[x]]==1) s1.set(a[x]),s2.set(N-a[x]);` 而不是 `if(bu[a[x]]==1) s1.set(a[x]);s2.set(N-a[x]);` 。delete 函数同理。

:::

### F. Substrings in a String

https://codeforces.com/problemset/problem/914/F

**题目描述**

给定字符串 $s$，多次询问某个字符串 $x$ 在 $s[l:r]$ 中出现了多少次，带修。$|s|,\sum|x|\le 10^5$，时限 6s

**笔记**

bitset 还可以用来乱搞字符串匹配

我们把字符串 $s$ 中的每种字符都开一个 bitset，在 bitset 中记录该字符的出现位置，比如对于字符串 `ababababab`

则 bitset $s_a$  为 `0101010101`

bitset $s_b$  为 `1010101010`

（注意字符串最右边的数字是低位）

如果现在有字符串 $y$ `aba` ，我们想知道这个字符串在字符串 $s$ 中出现了多少次，那么我们可以这样：先有一个bitset $ans$ ，初始时该 bitset 中每一位都置为 1。然后我们枚举字符串 $y$ 中的每个字符 $y_i$，再令 $ans\ =(s_{y_i}  i)$：

| bitset           | 位         |
| ---------------- | ---------- |
| $ans$ 初始时     | 1111111111 |
| $s_a  0$         | 0101010101 |
| $s_b  1$         | 0101010101 |
| $s_a  2$         | 0001010101 |
| $ans$ 按位与之后 | 0001010101 |

然后我们发现，最后得到的 $ans$ 中，有 $1$ 的位置就表示这个位置可以作为字符串 $y$ 起始位置。于是我们看一下有多少个 1，就知道了出现了多少次。时间复杂度 $O(\frac{n\sum |s|}{w})$。如果 $n$ 和 $\sum|s|$ 都是 $10^5$ 级别，那么可以通过这个优化给草过去。相当于优化了暴力。

而本题还给定了区间，对于询问区间 $[l,r]$ （下标为 1 开始），我们取 $ans$ 的区间 $[l,r-|x|+1]$ （区间从右往左看）中的 1 的个数。

```cpp
#include bits/stdc++.h 
#define ull unsigned long long
#define ls(k) (k)  1
#define rs(k) (k)  1|1
#define debug(x) cout  #x  "="  x  endl
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
const int mod=0;
typedef pair int,int  pii;
#define _ 100005
bitset _  s[27];//index-1
char str[_];//index-0
inline void subtask(){
    cin  str;
    for(int i=0;i strlen(str);i++) s[str[i]-'a'][i+1]=1;
    int m;cin  m;
    while(m--){
        string ss;
        int op,l,r;cin  op  l;
        if(op==1) cin  ss,s[str[l-1]-'a'][l]=0,str[l-1]=ss[0],s[str[l-1]-'a'][l]=1;
        else{
            cin  r  ss;
            bitset _  ans;ans.set();
            for(int i=0;i ss.size();i++) ans =(s[ss[i]-'a']  i);
            int sum1=(ans  l).count(),sum2=(ans  max(r-(int)ss.size()+2,0)).count();
            cout  max(sum1-sum2,0)  endl;
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```





## hash
这里展示使用自然溢出的hash
```cpp
ull hashs[_],bases[_],base=131311;

bases[0]=1;
for(int i=1;i =n;i++){
	bases[i]=bases[i-1]*base;
	hashs[i]=hashs[i-1]*base+str[i];
}

inline ull range(int l,int r){return hashs[r]-hashs[l-1]*bases[r-l+1];}
```

### 求最小循环节
首先线性筛预处理出素数
我们有下面两个性质

* 若长度为 $n$ 的前缀是 str 的循环节，则 $k*n$ 也是 str 的循环节 （ $n$ 和 $k*n$ 都是字符串长度的因数）

* 若字符串从 1 到 (len-n) 的子字符串与从 (n+1) 到 len 的子字符串是相同的，且 n 为 len 的因数，则长度为 n 的前缀是该字符串的循环节

于是对于求给定区间的最小循环节，我们可以这样处理
```cpp
	while(q--){
		int l,r;cin  l  r;
		int len=r-l+1,cnt=0;
		while(len 1){//这一步是分解质因数
			num[++cnt]=nxt[len];
			len/=nxt[len];
		}
		len=r-l+1;
		for(int i=1;i =cnt;i++){//根据上述第一个性质，我们尝试把一个质因子除掉后还是不是循环节
			int tmp=len/num[i];
			if(range(l,r-tmp)==range(l+tmp,r)) len=tmp;//根据上述第二个性质判断
		}
		cout  len  endl;;
	}
```

### 求最长公共前缀

**【模板】后缀排序**

读入一个长度为 $ n $ 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序（用 ASCII 数值比较）从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 $ 1 $ 到 $ n $。

直接使用sort对每个字符串进行排序的时间复杂度其实是大于 $O(n^2)$ 的，因为两个字符串之间的比较的复杂度是 $O(n)$ 的。为了快速比较两个字符串的字典序，我们考虑求出两个字符串的LCP，然后看LCP下一个字符哪个字符串的大

使用hash+二分来求

```cpp
#include bits/stdc++.h 
#define _ 1000006
#define ull unsigned long long
using namespace std;

ull base=131311,hashs[_],bases[_];
inline ull range(int l,int r){return l =r? hashs[r]-hashs[l-1]*bases[r-l+1]:0;}
char str[_];
int n,a[_];

inline bool cmp(int x,int y){
	int l=0,r=min(n-x+1,n-y+1),ans=0;//r处的意思是取两个字符串之间的长度最小的那个字符串的长度
	while(l =r){
		int mid=(l+r)  1;
		if(range(x,x+mid-1)==range(y,y+mid-1)) ans=mid,l=mid+1;
		else r=mid-1;
	}
	if(ans==min(n-x+1,n-y+1)) return x y;
	else return str[x+ans] str[y+ans];
}

int main(){
	cin  str+1;
	n=strlen(str+1);
	bases[0]=1;
	for(int i=1;i =n;i++){
		bases[i]=bases[i-1]*base;
		hashs[i]=hashs[i-1]*base+str[i];
		a[i]=i;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i =n;i++) cout  a[i]  ' ';
	return 0;
}
```


## KMP  

处理nxt数组

```cpp
int p=0;
nxt[1]=0;
for(int i=1;i m;i++){
	while(p 0  b[i+1]!=b[p+1]) p=nxt[p];
	if(b[i+1]==b[p+1]) p++;
	nxt[i+1]=p;
}
```

$nxt[i]$ 表示一直到位置i（包括i）的前缀字符串的最长公共前后缀长度  
并且，如果 $n \bmod (n-nxt[n])=0$ 则该字符串是由前缀长度 $n-nxt[n]$ 的子串进行若干次拼接得到的  

匹配  

```cpp
p=0;
for(int i=0;i n;i++){
	while(p 0  b[p+1]!=s[i+1]) p=nxt[p];
	if(b[p+1]==s[i+1]) p++;
	if(p==m) ans++;
}
```

## trie树  

### 普通trie树

```cpp
struct Node{int w,son[62];} trie[3000006];
int size;
inline void put(string str){
	int p=0;
	for(int i=0,now;i str.size();i++){
		if(!trie[p].son[now=str[i]-'a']) trie[p].son[now]=++size;
		p=trie[p].son[now];
		trie[p].w++;
	}
}
```

### 01trie作平衡树  

$w[]$ 用来kth，rak操作。$num[]$ 用来存放当前节点表示的数，省去了位运算的过程  

有可能读入负数，需要先加上一个偏移量变成正数  

加入操作

```cpp
const int off=10000000;
int trie[10000007][2],num[10000007],w[10000007],size=1;
inline void add(int x,int c){
	int p=1;
	x+=off;
	for(int i=32,now;i =0;i--){
		if(!trie[p][(now=((x  i) 1))]) trie[p][now]=++size;
		p=trie[p][now];
		w[p]+=c;
	}
	num[p]=x;
}
```

rak操作。这个操作返回的是比给定的数小的个数。求排名还需要加一  

```cpp
inline int rak(int x){
	int p=1,res=0;
	x+=off;
	for(int i=32,now;i =0;i--){
		if(now=((x  i) 1)) res+=w[trie[p][0]];
		p=trie[p][now];
	}
	return res;
}
```

kth操作  

```cpp
inline int kth(int k){
	int p=1;
	for(int i=32,now;i =0;i--){
		if(w[trie[p][0]] k) k-=w[trie[p][0]],p=trie[p][1];
		else p=trie[p][0];
	}
	return num[p]-off;
}
```

**插入** `add(x,1);`  

**删除** `add(x,-1);`  

**求排名** `cout  rak(x)+1  endl;`  

**求第x小** `cout  kth(x)  endl;`  

**求前驱** `cout  kth(rak(x))  endl;`  

**求后继** `cout  kth(rak(x+1)+1)  endl;`  

## Manacher

对字符串处理  

```cpp
	str[0]='~';
	str[1]='|';
	cnt=1;
	char c=getchar();
	while(c 'a'||c 'z') c=getchar();
	while(c ='a'  c ='z') str[++cnt]=c,str[++cnt]='|',c=getchar();
```

求p数组

```cpp
	for(int t=1,r=0,mid=0;t =cnt;t++){
		if(t =r) p[t]=min(p[(mid  1)-t],r-t+1);
		while(str[t-p[t]]==str[t+p[t]]) ++p[t];
		if(p[t]+t r) r=p[t]+t-1,mid=t;
	}
```

$p[t]-1$ 才是回文串长度  
