




## 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;
}
```











## 整体二分

整体二分的基本思想是，二分出一个 $mid$，然后遍历所有的询问，每个询问都 check 一下 mid 是偏大了还是偏小了。把偏大的询问分成一组，偏小的询问分成另一组。然后这两组询问再分别二分

### P3332 [ZJOI2013] K大数查询

https://www.luogu.com.cn/problem/P3332

**题目描述**

你需要维护 $n$ 个可重整数集，集合的编号从 $1$ 到 $n$。  

这些集合初始都是空集，有 $m$ 个操作：  

- `1 l r c`：表示将 $c$ 加入到编号在 $[l,r]$ 内的集合中  
- `2 l r c`：表示查询编号在 $[l,r]$ 内的集合的并集中，第 $c$ 大的数是多少。  

注意可重集的并是不去除重复元素的，如 $\{1,1,4\}\cup\{5,1,4\}=\{1,1,4,5,1,4\}$。

**数据范围**

$1 \le n,m \le 5\times 10^4$ 

$1\le l,r \le n$ 

$1$ 操作中 $|c|\le n$ 

$2$ 操作中 $1\le c   2^{63}$，第 $c$ 大的数存在

**笔记**

```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 _ 50004
int n,arr[_],m,sum[_  2],tag[_  2];
inline void pushup(int k){sum[k]=sum[ls(k)]+sum[rs(k)];}
inline void pushadd(int k,int l,int r,int v){sum[k]+=v*(r-l+1),tag[k]+=v;}
inline void pushdown(int k,int l,int r,int mid){if(tag[k])pushadd(ls(k),l,mid,tag[k]),pushadd(rs(k),mid+1,r,tag[k]),tag[k]=0;}
void modify(int k,int l,int r,int x,int y,int v){
    if(l =x  r =y) return pushadd(k,l,r,v),void();
    int mid=(l+r)  1;
    pushdown(k,l,r,mid);
    if(x =mid) modify(ls(k),l,mid,x,y,v);
    if(y mid) modify(rs(k),mid+1,r,x,y,v);
    pushup(k);
}
int query(int k,int l,int r,int x,int y){
    if(l =x  r =y) return sum[k];
    int mid=(l+r)  1,res=0;
    pushdown(k,l,r,mid);
    if(x =mid) res+=query(ls(k),l,mid,x,y);
    if(y mid) res+=query(rs(k),mid+1,r,x,y);
    return res;
}
struct Q{int l,r,x,id,ans,op;} L[_],R[_],q[_];
void solve(int l,int r,int ql,int qr){
    if(ql qr) return;
    if(l==r){
        for(int i=ql;i =qr;i++) if(q[i].op==2) q[i].ans=l;
        return;
    }
    int mid=(l+r)  1;
    int cntl=0,cntr=0;
    for(int i=ql;i =qr;i++){
        if(q[i].op==1){
            if(q[i].x mid) modify(1,1,n,q[i].l,q[i].r,1),R[++cntr]=q[i];
            else L[++cntl]=q[i];
        }else{
            int cnt=query(1,1,n,q[i].l,q[i].r);
            if(q[i].x =cnt) R[++cntr]=q[i];
            else q[i].x-=cnt,L[++cntl]=q[i];
        }
    }
    for(int i=ql;i =qr;i++) if(q[i].op==1  q[i].x mid) modify(1,1,n,q[i].l,q[i].r,-1);
    for(int i=1;i =cntl;i++) q[ql-1+i]=L[i];
    for(int i=1;i =cntr;i++) q[ql+cntl-1+i]=R[i];
    solve(l,mid,ql,ql+cntl-1);
    solve(mid+1,r,ql+cntl,qr);
}
inline void subtask(){
    cin  n  m;
    for(int i=1;i =m;i++) cin  q[i].op  q[i].l  q[i].r  q[i].x,q[i].id=i;
    solve(-n,n,1,m);
    sort(q+1,q+m+1,[](Q x,Q y){return x.id y.id;});
    for(int i=1;i =m;i++) if(q[i].op==2) cout  q[i].ans  endl;
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```

因为我们判断 mid 是偏大了还是偏小了，需要知道比 mid 大的数有多少，因此我们把大于 $mid$ 的 $x$ 值加入线段树。并且，如果询问需要归到 $R$ 中，那么也只有 $x$ 值大于 $mid$ 的操作一会影响到这些询问，因此 $x$ 值大于 $mid$ 的操作也归到 $R$ 中

### P3527 [POI 2011] MET-Meteors

https://www.luogu.com.cn/problem/P3527

**题目描述**

有 $n$ 个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为 $m$ 份（第 $m$ 份和第 $1$ 份相邻），第 $i$ 份上有第 $a_i$ 个国家的太空站。

这个星球经常会下陨石雨。BIU 已经预测了接下来 $k$ 场陨石雨的情况。

BIU 的第 $i$ 个成员国希望能够收集 $p_i$ 单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。

**输入格式**

第一行是两个数 $n,m$。

第二行有 $m$ 个数，第 $i$ 个数 $o_i$ 表示第 $i$ 段轨道上有第 $o_i$ 个国家的太空站。

第三行有 $n$ 个数，第 $i$ 个数 $p_i$ 表示第 $i$ 个国家希望收集的陨石数量。

第四行有一个数 $k$，表示 BIU 预测了接下来的 $k$ 场陨石雨。 接下来 $k$ 行，每行有三个数 $l_i,r_i,a_i$ ，表示第 $k$ 场陨石雨的发生地点在从 $l_i$ 顺时针到 $r_i$ 的区间中（如果 $l_i \leq r_i$，则是 $l_i, l_i + 1 
\cdots, r_i$，否则就是 $l_i, l_i + 1, 
\cdots m - 1, m, 1, 2, \cdots r_i$），向区间中的每个太空站提供 $a_i$ 单位的陨石样本。

**数据范围**

$1\le n,m,k\le 3\cdot10^5$；

$1\le p_i,a_i\le 10^9$；

**笔记**

把环形的区间加拆成两个操作，然后整体二分即可。整体二分时直接暴力计算每个询问是否满足要求貌似是可以的

```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 _ 900005
int arr[_],n,m;
inline int lowbit(int x){return x -x;}
inline void modify(int x,int v){while(x =m) arr[x]+=v,x+=lowbit(x);}
inline int query(int x,int res=0){while(x) res+=arr[x],x-=lowbit(x);return res;}
struct Q{int l,r,id,ans,op,x,need;} q[_],L[_],R[_];
vector int  g[_];
void solve(int l,int r,int ql,int qr){
    if(ql qr) return;
    if(l==r){
        for(int i=ql;i =qr;i++) if(q[i].op==0) q[i].ans=l;
        return;
    }
    int mid=(l+r)  1,cntl=0,cntr=0;
    for(int i=ql;i =qr;i++){
        if(q[i].op==1){
            if(q[i].id =mid) modify(q[i].l,q[i].x),modify(q[i].r+1,-q[i].x),L[++cntl]=q[i];
            else R[++cntr]=q[i];
        }else{
            int s=0;
            for(auto to:g[q[i].x]){
                s+=query(to);
                if(s =q[i].need) break;
            }
            if(s =q[i].need) L[++cntl]=q[i];
            else q[i].need-=s,R[++cntr]=q[i];
        }
    }
    for(int i=ql;i =qr;i++) if(q[i].op==1  q[i].id =mid) modify(q[i].l,-q[i].x),modify(q[i].r+1,q[i].x);
    for(int i=1;i =cntl;i++) q[ql+i-1]=L[i];
    for(int i=1;i =cntr;i++) q[ql+cntl+i-1]=R[i];
    solve(l,mid,ql,ql+cntl-1);
    solve(mid+1,r,ql+cntl,qr);
}
int need[_];
inline void subtask(){
    cin  n  m;
    for(int i=1,x;i =m;i++) cin  x,g[x].push_back(i);
    for(int i=1;i =n;i++) cin  need[i];
    int totq,cntq=0;cin  totq;
    for(int i=1;i =totq;i++){
        int l,r,x;cin  l  r  x;
        if(l =r) q[++cntq].l=l,q[cntq].r=r,q[cntq].op=1,q[cntq].id=i,q[cntq].x=x;
        else q[++cntq].l=1,q[cntq].r=r,q[cntq].op=1,q[cntq].id=i,q[cntq].x=x,q[++cntq].l=l,q[cntq].r=m,q[cntq].op=1,q[cntq].id=i,q[cntq].x=x;
    }
    for(int i=1;i =n;i++) q[++cntq].id=i,q[cntq].x=i,q[cntq].need=need[i];
    //for(int i=1;i =cntq;i++) debug(q[i].op),debug(q[i].l),debug(q[i].r);
    solve(1,totq+1,1,cntq);
    sort(q+1,q+cntq+1,[](Q x,Q y){return x.id y.id;});
    for(int i=1;i =cntq;i++){
        if(q[i].op) continue;
        if(q[i].ans==totq+1) cout  "NIE"  endl;
        else cout  q[i].ans  endl;
    }
}
signed main(){
    ios::sync_with_stdio(false);
    int t=1;//cin  t;
    while(t--) subtask();
    return 0;
}
```







## 一些定义

**字符串**

* $|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;
}
```


