算法模板

快排

void quicksort(int l,int r) 
{ 
    if(l>=r) return; 
    swap(a[i],a[l+rand()%(r-l+1)]); 
    int x = a[l]; 
    int i = l,j = r; 
    while (i<j) 
    { 
        while (i<j&&a[j]>x) 
            j--; 
        if(i<j) a[i++] = a[j]; 
        while (i<j&&a[i]<x) 
            i++; 
        if(i<j) a[j--] = a[i];        
    } 
    a[i] = x; 
    quicksort(l,i-1); 
    quicksort(i+1,r); 
} 

归并

void mergesort(int l,int r) 
{ 
    if(l==r) return; 
    int m = (l+r)/2; 
    mergesort(l,m); 
    mergesort(m+1,r); 
    int p1 = l,p2 = m+1,tot = 0; 
    while (p1<=m&&p2<=r) 
        if(a[p1]<=a[p2]) 
            c[++tot] = a[p1++]; 
        else 
            c[++tot] = a[p2++]; 
    while (p1<=m) 
        c[++tot] = a[p1++]; 
    while (p2<=r) 
        c[++tot] = a[p2++];         
    for (int i = 1; i <= tot; i++) 
        a[i+l-1] = c[i];     
}

位运算

一维前缀和

预处理:s[i]=a[i]+a[i-1]

求区间[l,r]:sum=s[r]-s[l-1]

“前缀和数组”和”原数组”可以合二为一

二位前缀和

>计算矩阵的前缀和：s[x][y] = s[x - 1][y] + s[x][y -1] - s[x-1][y-1] + a[x][y] 

>以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：

计算子矩阵的和：s = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 -1]

一维差分

差分是前缀和的逆运算，对于一个数组a，其差分数组b的每一项都是a [ i ]和前一项a [ i − 1 ]的差。

注意：差分数组和原数组必须分开存放！！！！

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：

S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

离散化

离散化的本质是建立了一段数列到自然数之间的映射关系（value -> index)，通过建立新索引，来缩小 目标区间，使得可以进行一系列连续数组可以进行的操作比如二分，前缀和等

离散化首先需要排序去重：

1. 排序：sort(alls.begin(),alls.end())
2. 1. 去重：alls.earse(unique(alls.begin(),alls.end()),alls.end());

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1; // 映射到1, 2, ...n
}

区间合并

// 将所有存在交集的区间合并
void merge(vector<PII> &segs)
{
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
    	else ed = max(ed, seg.second);
}
if (st != -2e9) res.push_back({st, ed});
segs = res;

KMP

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
//求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
 {
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
 }
 // 匹配
for (int i = 1, j = 0; i <= n; i ++ )
 {
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
 }

//判断s中是否包含p，f表示匹配到p的第几位 o(n+m) 
int n,m; 
int nxt[M+1],f[N+1]; 
char s[N+2],p[M+2];//s 主串 p 模式串 

void kmp() 
{ 
    n = strlen(s+1); 
    m = strlen(p+1); 
    int j = 0; 
    nxt[1] = 0; 
    for (int i = 2; i <= m; i++) 
    { 
        while (j>0&&p[j+1]!=p[i]) 
            j = nxt[j]; 
        if(p[j+1]==p[i]) 
            j++; 
        nxt[i] = j; 
    } 
    j = 0; 
    for (int i = 1; i < n; i++) 
    { 
        while ((j==m)||(j>0&&p[j+1]!=s[i])) 
            j = nxt[j]; 
        if(p[j+1]==s[i]) 
            j++; 
        f[i] = j;                 
    } 
} 

EXKMP

//求出s跟它的任意后缀的最长公共前缀的长度 
int n; 
int z[N+1];//z[i]表示s和s[i]-s[n]的最长公共前缀的长度 
char s[N+2]; 
  
void exkmp() 
{ 
    n = strlen(s+1); 
    int l = 1,r = 0; 
    z[1] = 0; 
    for (int i = 2; i <= n; i++) 
    { 
        if(i>r) z[i] = 0; 
        else z[i] = min(z[i-l+1],r-i+1); 
        while (i+z[i]<=n&&s[z[i]+1]==s[i+z[i]]) 
            z[i]++; 
        if(i+z[i]-1>R) 
            l = i,r = i+z[i]-1;         
    } 
} 

最长回文字串

//o(n) 
int n,p[2*N+2]; 
char s[N+2],t[2*N+3]; 

void manacher(){ 
    n = strlen(s+1); 
    int m = 0; 
    t[++m] = '$'; 
    for (int i = 1; i <= n; i++) 
        t[++m] = s[i],t[++m] = '$'; 
    int M = 0,R = 0; 
    for (int i = 1; i <= m; i++) 
    { 
        if(i>R) p[i] = 1; 
        else p[i] = min(p[2*M-i],R-i+1); 
        while (i-p[i]>0&&i+p[i]<=m&&t[i-p[i]]==t[i+p[i]]) 
            ++p[i]; 
        if(i+p[i]-1>R)  
            M = i,R = i+p[i]-1;                 
    } 
    int ans = 0; 
    for (int i = 1; i <= m; i++) 
        ans = max(ans,p[i]); 
    printf("%d\n",ans-1);    
} 

Trie树

Trie 树是一种多叉树的结构，每个节点保存一个字符，一条路径表示一个字符串。

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}
// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

并查集

(1)朴素并查集：
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;
// 合并a和b所在的两个集合：
p[find(a)] = find(b);

(2)维护size的并查集：
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
    p[i] = i;
    size[i] = 1;
}
// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

(3)维护到祖宗节点距离的并查集：
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x)
    {
        int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
    p[i] = i;
    d[i] = 0;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

字符串哈希

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
    小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
    typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

拓扑排序

一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边

一直进行上面出处理，如果所有点都能被删掉，则这个图可以进行拓扑排序

vector<int> edge[N+1]; 
int n,m,q[N+1],d[N+1];//d 记录了每个点一开始的入度 

inline void TopoSort() { 
    int front = 1,rear = 0; 
    for (int i = 1; i <= n; i++)  
        if (!d[i]) q[++rear] = i; 
    while (front <= rear) 
    { 
        int x = q[front]; 
        ++front; 
        for (auto y : edge[x]) 
            if (--d[y] == 0) q[++rear] = y; 
    } 
    if (rear == n) { 
        printf("Yes\n"); 
        //q 中记录啦一个合法的拓扑序列 
    }else { 
        printf("No\n"); 
    } 
} 

Dijkstra算法

朴素版

时间复杂是O(n^2+m)，n表示点数，m表示边数

int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        st[t] = true;
    }
    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

struct Node 
{ 
    int y, v; 
    Node(int _y, int _v) 
    { 
        y = _y; 
        v = _v; 
    } 
}; 

vector<Node> edge[N+1]; 
int n,m,dist[N+1]; 
bool b[N+1]; 

int Dijkstra(int s, int t) 
{ 
    memset(b, false, sizeof(b)); 
    memset(dist, 127, sizeof(dist)); 
    dist[s] = 0; 
    for ( ; ; ) { 
        int x = -1; 
        for (int i = 1; i <= n; i++) 
            if (!b[i]&&dist[i] < 1 << 30)  
                if (x == -1 || dist[i] < dist[x])  
                    x = i; 
        if(x == t || x == -1) break; 
        b[x] = true; 
        for (auto i : edge[x])  
            dist[i.y] = min(dist[i.y], dist[x] + i.v); 
    } 
    return dist[t]; 
} 

堆优化版

时间复杂度O(mlogn)，n表示点数，m表示边数

struct Node 
{ 
    int y, v; 
    Node(int _y, int _v) 
    { 
        y = _y; 
        v = _v; 
    } 
}; 

set<pair<int,int>> q; 
vector<Node> edge[N+1]; 
int n,m,dist[N+1]; 

int Dijkstra(int s, int t) 
{ 
    memset(dist, 127, sizeof(dist)); 
    dist[s] = 0;q.clear(); 
    for (int i = 1; i <= n; i++) 
        q.insert(make_pair(dist[i],i)); 
    for ( ; !q.empty(); ) { 
        int x = q.begin()->second; 
        q.erase(q.begin()); 
        if (x == t || dist[x] > 1<<30) break; 
        for (auto i : edge[x]) { 
            if (dist[x] + i.v < dist[i.y]) { 
                q.erase(make_pair(dist[i.y], i.y)); 
                dist[i.y] = dist[x] + i.v; 
                q.insert(make_pair(dist[i.y], i.y)); 
            } 
        } 
    } 
    return dist[t]; 
}

typedef pair<int, int> PII;
 int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
 int dijkstra(){
    memset(dist,0x3f,sizeof dist);//距离初始化为无穷大
    dist[1]=0;//1->1的节点距离为0
    priority_queue<PII,vector<PII>,greater<PII>> heap;//小根堆
    heap.push({0,1});//插入距离和节点编号
    
    while(heap.size()){
        auto t=heap.top();//取距离源点最近的点
        heap.pop();
        
        int ver=t.second,distance=t.first;//ver：节点编号，distance源点距离ver
        if(st[ver])continue;//如果距离已经确定，则跳过该点
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i])//更新ver所指向的节点距离
        {
            int j=e[i];
            if(dist[j]>dist[ver]+w[i]){
                dist[j]=dist[ver]+w[i];
                heap.push({dist[j],j});//距离变小，则入堆
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    return dist[n];
 }

Bellman-Ford最短路

struct Edge{ 
    int x,y,v; 
}edge[M+1]; 
int n,m,dist[N+1],pre[N+1]; 

int shortestpath(int s,int t) { 
    memset(dist, 127, sizeof(dist)); 
    dist[s] = 0; 
    for( ; ; ) { 
        bool ok = false; 
        for (int i = 1; i <= m; i++){ 
            int x = edge[i].x, y = edge[i].y, v = edge[i].v; 
            if(dist[x] < 1 <<30) { 
                if (dist[x] + v < dist[y]) { 
                    dist[y] = dist[x] + v; 
                    pre[y] = x; 
                    ok = true; 
                } 
            } 
        } 
        if(!ok) break; 
    } 
    return dist[t]; 
} 

Floyd 最短路

初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
			else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

prim算法

时间复杂度是 O(n^2+m)，n表示点数，m表示边数

int n;
// n表示点数
int g[N][N];        
int dist[N];        
bool st[N];     
// 邻接矩阵，存储所有边
// 存储其他点到当前最小生成树的距离
// 存储每个点是否已经在生成树中
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
    }
}
if (i && dist[t] == INF) return INF;
if (i) res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
return res;

//朴素
struct Node 
{ 
    int y, v; 
    Node(int _y, int _v) 
    { 
        y = _y; 
        v = _v; 
    } 
}; 

vector<Node> edge[N+1]; 
int n,m,dist[N+1]; 
bool b[N+1]; 

int Prim() 
{ 
    memset(b, false, sizeof(b)); 
    memset(dist, 127, sizeof(dist)); 
    dist[s] = 0; 
    int ans = 0, tot = 0; 
    for ( ; ; ) { 
        int x = -1; 
        for (int i = 1; i <= n; i++) 
            if (!b[i]&&dist[i] < 1 << 30)  
                if (x == -1 || dist[i] < dist[x])  
                    x = i; 
        if(x == -1) break; 
        ++tot; 
        ans += dist[x]; 
        b[x] = true; 
        for (auto i : edge[x])  
            dist[i.y] = min(dist[i.y], i.v); 
    } 
    if (tot != n) return -1; 
    return ans; 
} 

//堆优化
struct Node 
{ 
    int y, v; 
    Node(int _y, int _v) 
    { 
        y = _y; 
        v = _v; 
    } 
}; 

set<pair<int,int>> q; 
vector<Node> edge[N+1]; 
int n,m,dist[N+1]; 
bool b[N+1]; 

int Prim() 
{ 
    memset(b, false, sizeof(b)); 
    memset(dist, 127, sizeof(dist)); 
    dist[1] = 0;q.clear(); 
    for (int i = 1; i <= n; i++) 
        q.insert(make_pair(dist[i],i)); 
    int ans = 0, tot = 0; 
    for ( ; !q.empty(); ) { 
        int x = q.begin()->second; 
        q.erase(q.begin()); 
        if (dist[x] > 1<<30) break; 
        ++tot; 
        ans += dist[x]; 
        b[x] = true; 
        for (auto i : edge[x]) { 
            if (!b[i.y] && i.v < dist[i.y]) { 
                q.erase(make_pair(dist[i.y], i.y)); 
                dist[i.y] = i.v; 
                q.insert(make_pair(dist[i.y], i.y)); 
            } 
        } 
    } 
    if (tot != n) return -1; 
    return ans; 
} 

Kruskal算法

struct Node 
{ 
    int x, y, v; 
    bool operator < (const Node &A) const { 
        return v < A.v; 
    } 
}a[M+1]; 

int n,m,fa[N+1]; 

int findset(int i) { 
    if (i == fa[i]) return i; 
    return fa[i] == findset(fa[i]); 
} 

int Kruskal() 
{ 
    for (int i = 1; i <= n; i++) 
        fa[i] = i; 
    sort(a+1,a+m+1); 
    int ans = 0, cnt = n; 
    for (int i = 1; i <= m; i++){ 
        int x = findset(a[i].x), y = findset(a[i].y); 
        if (x != y) { 
            fa[x] = y; 
            ans += a[i].v; 
            --cnt; 
        } 
        if (cnt == 1) break; 
    } 
    if (cnt != 1) return -1; 
    return ans; 
}

树状数组

树状数组（O(logn) 单点加 查询前缀和 ）

int a[N]; 
ll c[N]; 

//下标不能为0 要不死循环 
//c[i] = a[i-lowbit(i)+1] ~ a[i] 的和 
//lowbit(i) ==> x&(-x)

ll query(int x){ // 1...x 的和 
    ll s = 0; 
    for (; x; x -= x&(-x)) 
        s+= c[x]; 
    return s;     
} 

void modify(int x,ll s){ // a[x] += s 
    for (; x <= n; x += x&(-x)) 
        c[x] += s; 
} 

线段树

（单点修改 区间查询）

//以查询区间最小值为例 
int a[N]; 
struct Node{ 
    int minv; 
}seg[N*4]; 

void update(int id) { 
    seg[id].minv = min(seg[id*2].minv,seg[id*2+1].minv); 
} 

// [l,r] 
void build(int id,int l,int r) { 
    if(l==r){ 
        seg[id].minv = a[l]; 
    }else { 
        int mid = (l+r)/2; 
        build(id*2,l,mid); 
        build(id*2+1,mid+1,r); 
        update(id); 
    } 
} 

//节点为id,对应的区间为[l,r],修改a[pos] -> val 
void change(int id,int l,int r,int pos,int val) { 
    if(l==r){ 
        seg[id].minv = val; 
    }else { 
        int mid = (l+r)/2; 
        if(pos<=mid) change(id*2,l,mid,pos,val); 
        else change(id*2+1,mid+1,r,pos,val); 
        update(id); 
    } 
} 

//[ql,qr] 表示要查询的区间 
int query(int id,int l, int r,int ql,int qr) { 
    if(l == ql && r == qr) return seg[id].minv; 
    int mid = (l + r)/2; 
    if(qr<=mid) return query(id*2,l,mid,ql,qr); 
    else if (ql>mid) return query(id*2+1,mid+1,r,ql,qr); 
    else { 
        return 
            min(query(id*2,l,mid,ql,mid),query(id*2+1,mid+1,r,mid+1,qr)) 
    } 
}

（区间修改 区间查询） 懒标记

//以 
//1.将某区间每一个数加上k 
//2.求出某区间每一个数的和。 
//为例 
int a[N]; 
struct Node{ 
    ll t,val,sz; 
}seg[N*4]; 
void setting(int id,ll t) { //给节点加标记 
    seg[id].val = seg[id].val + t*seg[id].sz; 
    seg[id].t = seg[id].t + t; 
} 
void pushdown(int id) { // 标记下沉 
    if(seg[id].t != 0) { // 标记非空 
        setting(id *2,seg[id].t); 
        setting(id *2+1,seg[id].t); 
        seg[id].t = 0; 
    } 
} 
void update(int id) { 
    seg[id].sz = seg[id*2].sz+seg[id*2+1].sz; 
    seg[id].val = seg[id*2].val+seg[id*2+1].val; 
} 
// [l,r] 
void build(int id,int l,int r) { 
    if(l==r){ 
        seg[id].val = a[l]; 
        seg[id].sz = 1; 
    }else { 
        int mid = (l+r)/2; 
        build(id*2,l,mid); 
        build(id*2+1,mid+1,r); 
        update(id); 
    } 
} 

//节点为id,对应的区间为[l,r],给区间[ql,qr]加上t 
void modify(int id,int l,int r,int ql,int qr,ll t) { 
    if(l == ql && r == qr) { 
        setting(id,t); 
        return; 
    } 
    int mid = (l + r)/2; 
    pushdown(id); 
    if(qr<=mid) modify(id*2,l,mid,ql,qr,t); 
    else if (ql>mid) modify(id*2+1,mid+1,r,ql,qr,t); 
    else { 
        modify(id*2,l,mid,ql,mid,t); 
        modify(id*2+1,mid+1,r,mid+1,qr,t); 
    } 
    update(id); 
} 

//[ql,qr] 表示要查询的区间 
ll query(int id,int l, int r,int ql,int qr) { 
    if(l == ql && r == qr) return seg[id].val; 
    int mid = (l + r)/2; 
    pushdown(id); 
    if(qr<=mid) return query(id*2,l,mid,ql,qr); 
    else if (ql>mid) return query(id*2+1,mid+1,r,ql,qr); 
    else { 
        return 
            query(id*2,l,mid,ql,mid)+query(id*2+1,mid+1,r,mid+1,qr); 
    } 
} 

ST表

ST表（求 RMQ问题即区间最值 以及区间& | 等重复 运算不会改变值）

// n个数 a1 - an q个询问 每次给出l，r  问al-ar之间的最大值

int n,q,A,B,C; 
int f[N][20],a[N];//f[i][j]：从i开始长度为2的j次的区间最大值 
//让小的维度在第一维可以更快 
int main() 
{ 
    cin>>n>>p>>A>>B>>C; 
    for (int i = 1; i <= n; i++) 
    { 
        cin>>a[i]; 
        f[i][0] = a[i]; 
    } 
    for (int j = 1; j <= 20; j++) 
        for (int i = 1; i+(1<<j) <= n; i++) 
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]); 
    for (int i = 1; i <= q; i++) 
    { 
        int l,r; 
        cin>>l>>r; 
        if(l>r) swap(l,r); 
        int len = __lg(r-l+1); 
        ans ^= max(f[l][len],f[r-(1<<len)+1][len]); 
    } 
    cout<<ans; 
    return 0; 
}

LCA（最近公共祖先）

倍增o((n+m)logn)

const int N = 5e5+10; 
int n,m,s,a,b; 
vector<int> e[N]; 
int dep[N],fa[N][20]; 

void dfs(int u,int father) 
{ 
    dep[u] = dep[father]+1; 
    //向上跳1,2,4...步的祖先节点 
    fa[u][0] = father; 
    for (int i = 1; i < 20; i++) 
        fa[u][i] = fa[fa[u][i-1]][i-1]; 
    for (int v:e[u]) 
        if(v!=father) dfs(v,u); 
} 

int lca(int u,int v) 
{ 
    if(dep[u]<dep[v]) swap(u,v); 
    //先跳到同一层 
    for (int i = 19; i >= 0; i--) 
        if(dep[fa[u][i]]>=dep[v])  
            u = fa[u][i]; 
    if(u==v) return v; 
    //再跳到lca的下一层 
    for (int i = 19; i >= 0; i--) 
        if(fa[u][i]!=fa[v][i]) 
            u=fa[u][i],v=fa[v][i]; 
    return fa[u][0]; 
} 

Tarjan(离线)o(n+m)

vector<int> e[N]; 
vector<pair<int,int>> query[N]; 
int vis[N],fa[N],ans[M]; 

int find(int u) 
{ 
    if(u==fa[u]) return u; 
    return fa[u] = find(fa[u]); 
} 

void tarjan(int u) 
{ 
    vis[u] = true;//刚到u时 标记u 
    for (auto v:e[u]) 
    { 
        if(!vis[v]){ 
            tarjan(v); 
            fa[v] = u;//回到u时 v指向u 
        } 
    } 
    //离开u时 枚举lca 
    for (auto q:query[u]) 
    { 
        int v = q.first,i = q.second; 
        if(vis[v]) ans[i]=find(v); 
    } 
} 

for (int i = 1; i < n; i++) 
{ 
    cin>>a>>b; 
    e[a].push_back(b); 
    e[b].push_back(a); 
} 
for (int i = 1; i <= m; i++) 
{ 
    cin>>a>>b; 
    query[a].push_back({b,i}); 
    query[b].push_back({a,i}); 
}     
for (int i = 1; i <= N; i++) 
    fa[i]=i; 

树链剖分

int n,m; 
vector<int> e[N]; 
int dep[N],fa[N],son[N],sz[N];//sz[u] 存以u为根的子树的节点数 
int top[N];//存u所在重链的顶点 

void dfs1(int u,int father) 
{ 
    fa[u]=father,dep[u]=dep[father]+1,sz[u]=1; 
    for (int v:e[u]) 
    { 
        if(v==father) continue; 
        dfs1(v,u); 
        sz[u]+=sz[v]; 
        if(sz[son[u]]<sz[v]) son[u]=v; 
    } 
} 

void dfs2(int u,int t) 
{ 
    top[u] = t;//记录链头 
    if(!son[u]) return;//无重儿子返回 
    dfs2(son[u],t);//搜重儿子 
    for (int v:e[u]) 
    { 
        if(v==fa[u]||v==son[u]) continue; 
        dfs2(v,v);//搜轻儿子 
    } 
} 
int lca(int u,int v) 
{ 
    while (top[u]!=top[v]) 
    { 
        if(dep[top[u]]<dep[top[v]]) swap(u,v); 
        u=fa[top[u]]; 
    } 
    return dep[u]<dep[v]?u:v; 
}