一树上差分：

对于数组来说如果我们要在区间[L,R]上增加k，那么可以在L位置上增加K，R+1位置上减小K。

那么对于一颗数来说，如果我们要记录（x，y）之间的信息，那么可以在x和y位置+k，lca(x,y)位置减去2*k，访问的时候从叶子节点回溯到跟即是所求的值。题目：https://www.acwing.com/problem/content/description/354/

二 tarjan算法求割边

割边判定法则：无向变（ x，y）是桥，当且仅当搜索树上存在x的一个子节点y，满足：

dfn[x]<low[y]

#include<bits/stdc++.h>
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std;

const int N = 1000*100+10;
int n,m,cnt,num;
int head[N],ne[N*2],to[N*2];
int dfn[N],low[N];
bool bridge[N*2];

void add(int u,int v){
    to[cnt]=v,ne[cnt]=head[u],head[u]=cnt++;
    to[cnt]=u,ne[cnt]=head[v],head[v]=cnt++;
}


int main(){

    scanf("%d %d",&n,&m);
    cnt=2;
    for(int i=1;i<=n;i++)head[i]=-1;

    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }

    for(int i=1;i<=n;i++)dfn[i]=low[i]=0;
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan_edge(i,0);
    }

    for(int i=2;i<cnt;i+=2)
        if(bridge[i])
            printf("%d %d\n",to[i],to[i^1]);
}

三 tarjan求割点

判定法则：若x不是搜索树的根节点，则x是割点当且仅当搜索树上存在x的一个子节点y，满足：

dfn[x]<=low[y]

特别地，若x是搜索树的根节点，则x是割点当且仅当搜索树上至少存在两个子节点y1，y2，满足上述条件。

#include<bits/stdc++.h>
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std;

const int N = 1000*100+10;
int n,m,cnt,num,root;
int head[N],ne[N*2],to[N*2];
int dfn[N],low[N];
bool cut[N];

void add(int u,int v){
    to[cnt]=v,ne[cnt]=head[u],head[u]=cnt++;
    to[cnt]=u,ne[cnt]=head[v],head[v]=cnt++;
}

void tarjan_point(int x){
    dfn[x]=low[x]=++num;
    int flag=0;
    for(int i=head[x];i!=-1;i=ne[i]){
        int y=to[i];
        if(!dfn[y]){
            tarjan_point(y);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                flag++;
                if(x!=root||flag>1)cut[x]=true;
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}

int main(){

    scanf("%d %d",&n,&m);
    cnt=2;
    for(int i=1;i<=n;i++)head[i]=-1;

    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        if(u==v)continue;
        add(u,v);
    }

    for(int i=1;i<=n;i++)dfn[i]=low[i]=0,cut[i]=false;

    for(int i=1;i<=n;i++){
        if(!dfn[i])root=i,tarjan_point(i);
    }

    cout<<"This is all:"<<endl;
    for(int i=1;i<=n;i++)
        if(cut[i])
            printf("%d\n",i);

}

四康托展开

把一个全排列从小到大排序，对于给定的任意一个排列我们可以求出他属于第几个排列，即是求出有多少个排列比他小。

有关至少参看：康托展开

以下给出用树状数组优化后的算法：

#include<bits/stdc++.h>
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std;
const int mod=1e9 + 7;
const int MAXN=1e7;
int n,m,cnt;
int f[20],dat[20],vis[20];

struct {
    int s[20];
    void init(){
        for(int i=1;i<=n;i++)s[i]=0;
    }

    int lowerbit(int x){return x&-x;}
    void add(int x,int k){while(x<=n)s[x]+=k,x+=lowerbit(x);}
    int query(int x){int ans=0;while(x)ans+=s[x],x-=lowerbit(x);return ans;}
}bit;

void init(){
    f[0]=1;
    for(int i=1;i<=n;i++)f[i]=f[i-1]*i;
    while(m){
        dat[++cnt]=m%10;
        m/=10;
    }
}

int kangtuo(){
    int ans=0;
    for(int i=cnt;i;i--){
        ans+=bit.query(dat[i]-1)*f[i-1];
        bit.add(dat[i],-1);
    }
    return ans;
}

int main(){

    scanf("%d%d",&n,&m);
    bit.init();
    for(int i=1;i<=n;i++)bit.add(i,1);
    init();

    int n=kangtuo();
    printf("%d\n",n+1);

    return 0;
}

康托展开的逆运算：

就是求解第n个排列具体是什么

#include<bits/stdc++.h>
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 0x3f3f3f3f
using namespace std;
const int mod=1e9 + 7;
const int MAXN=1e7;
int n,m,cnt;
int f[20],dat[20],vis[20];

void init(){
    f[0]=1;
    for(int i=1;i<=n;i++)f[i]=f[i-1]*i;
}

int kangtuo_inver(int x){
    int num;
    int a[20];
    for(int i=1;i<=n;i++)a[i]=i;
    for(int i=1;i<=n;i++){
        num=x/f[n-i];
        x=x%f[n-i];
        int cnt=0;
        for(int j=1;j<=n;j++){
            if(cnt==num&&a[j]<n+1){
                dat[i]=a[j];
                a[j]=n+1;
                break;
            }
            if(a[j]<n+1)cnt++;
        }
    }
}

int main(){

    scanf("%d%d",&n,&m);

    init();

    kangtuo_inver(m);
    for(int i=1;i<=n;i++)printf("%d",dat[i]);

    return 0;
}

五后缀数组模板：

#include<bits/stdc++.h>
using namespace std;

const int N =1e6 + 10;
int M;
char s[N];
int n,m;
int rak[N],h[N],tax[N],tp[N],sa[N];

void qsort(){
    for(int i=0;i<M;i++)tax[i]=0;
    for(int i=1;i<=n;i++)tax[rak[i]]++;
    for(int i=1;i<=M;i++)tax[i]+=tax[i-1];
    for(int i=N;i>=1;i--)sa[tax[rak[tp[i]]]--]=tp[i];
}

void get_sa(){
    M=130;
    for(int i=1;i<=n;i++)rak[i]=s[i]-'0'+1,tp[i]=i;
    qsort();
    for(int w=1,p=0;p<=n;w<<=1,M=p){
        p=0;
        for(int i=1;i<=w;i++)tp[++p]=n-w+i;
        for(int i=1;i<=n;i++)if(sa[i]>w)tp[++p]=sa[i]-w;
        qsort();
        
        swap(tp,rak);
        rak[sa[1]]=p=1;
        for(int i=2;i<=n;i++){
            rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
        }
        
        if(p>=n)break;
    }
}


void get_h(){
    int j,k=0;
    for(int i=1;i<=n;i++){
        if(k)k--;
        int j=sa[rak[i]-1];
        while(s[i+k]==s[j+k])k++;
        h[rak[i]]=k;
    }
}


int main(){
    scanf("%s",s+1);    
    n=strlen(s+1);
    get_sa();
    get_h();
    
    for(int i=1;i<=n;i++)cout<<sa[i]<<" ";
    cout<<endl;
    
    return 0;
}

六后缀自动机模板：

const int N = 1000*100+10;
int sz,last;
struct state{
    int len,link;
    map<char,int>next;
}st[N*2];

void init(){
    st[0].len=0;
    st[0].link=-1;
    sz++;
    last=0;
}

void sa_extend(char c){
    int cur=sz++;
    st[cur].len=st[last].len+1;
    int p=last;
    while(p!=-1&&!st[p].next.count(c)){
        st[p].next[c]=cur;
        p=st[p].link;
    }
    if(p==-1)st[cur].link=0;
    else{
        int q=st[p].next[c];
        if(st[p].len+1==st[q].len)st[cur].link=q;
        else{
            int clone=sz++;
            st[clone].len=st[p].len+1;
            st[clone].next=st[q].next;
            st[clone].link=st[q].link;
            while(p!=-1&&st[p].next[c]==q){
                st[p].next[c]=clone;
                p=st[p].link;
            }
            st[q].link=st[cur].link=clone;
        }
    }
    last=cur;
}

日常笔记

一 树上差分：

二 tarjan算法求割边

三 tarjan求割点

四 康托展开

五 后缀数组模板：

六 后缀自动机模板：

一树上差分：

四康托展开

五后缀数组模板：

六后缀自动机模板：