数据结构进阶

最近公共祖先(LCA)

1.树上标记法

// LCA最近公共祖先 倍增算法
// accepted
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;
const int SIZE = 50010;
int f[SIZE][20], d[SIZE], dist[SIZE], tot, head[SIZE], t, n, m;
struct Edge
{
    int next;
    int v;
    int w;
};
Edge e[SIZE << 1];
queue<int> q;
void addEdge(int x, int y, int z)
{
    e[++tot].v = y;
    e[tot].w = z;
    e[tot].next = head[x];
    head[x] = tot;
}
// 计算树上节点的深度，用数组d存
void bfs()
{
    q.push(1);
    d[1] = 1;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = e[i].next)
        {
            int y = e[i].v;
            if (d[y])
                continue;
            d[y] = d[x] + 1;
            dist[y] = dist[x] + e[i].w;
            f[y][0] = x;
            for (int j = 1; j <= t; j++)
                f[y][j] = f[f[y][j - 1]][j - 1];
            q.push(y);
        }
    }
}
int lca(int x, int y)
{
    if (d[x] > d[y])
        swap(x, y);
    for (int i = t; i >= 0; i--)
        if (d[f[y][i]] >= d[x])
            y = f[y][i];
    if (x == y)
        return x;
    for (int i = t; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &m);
        t = (int)log(n) / log(2) + 1;
        memset(head, 0, sizeof(int) * (n + 1));
        memset(d, 0, sizeof(int) * (n + 1));
        tot = 0;
        for (int i = 1; i < n; i++)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            addEdge(x, y, z);
            addEdge(y, x, z);
        }
        bfs();
        for (int i = 1; i <= m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", dist[x] + dist[y] - 2 * dist[lca(x, y)]);
        }
    }
    return 0;
}

2.向上标记法

#include <stdio.h>
#include <string.h>
const int MAX = 10005;
int parent[MAX], mark[MAX], n;
int goUp(int u)
{
    int tmp = u;
    while(u)
    {
        if(mark[u]){
            return u;
        }
        mark[u] = 1;
        u = parent[u];
    }
    return 0;
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        memset(parent, 0, sizeof(parent));
        memset(mark, 0, sizeof(mark));
        scanf("%d", &n);
        int a, b;
        for(int i = 1; i < n; i++)
        {
            scanf("%d%d", &a, &b);
            parent[b] = a;
        }
        scanf("%d%d", &a, &b);
        goUp(a);
        printf("%d\n", goUp(b));
    }
    return 0;
}

树状数组

1.单点修改区间询问

// 树状数组 模板
// accepted
#include <stdio.h>
#include <string.h>
const int MAX = 5e4 + 5;
int a[MAX], c[MAX], n;
char str[10];
void add(int x, int y)
{
    for (; x <= n; x += x & -x)
        c[x] += y;
}
int query(int x)
{
    int ans = 0;
    for (; x; x -= x & -x)
        ans += c[x];
    return ans;
}
int main()
{
    int t, cnt = 0;
    scanf("%d", &t);
    while (t--)
    {
        printf("Case %d:\n", ++cnt);
        scanf("%d", &n);
        memset(c, 0, sizeof(int) * (n + 1));
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", a + i);
            add(i, a[i]);
        }
        int a, b;
        while (1)
        {
            scanf("%s", str);
            if (str[0] == 'E')
                break;
            scanf("%d%d", &a, &b);
            switch (str[0])
            {
            case 'A':
                add(a, b);
                break;
            case 'S':
                add(a, -b);
                break;
            case 'Q':
                printf("%d\n", query(b) - query(a - 1));
                break;
            }
        }
    }
    return 0;
}

线段树

1.延迟标记，区间增量，区间求和

// 线段树 区间求和 区间增量 区间询问 延迟标记
// accepted
#include <stdio.h>
#include <algorithm>
using namespace std;
const int MAX = 1e5 + 5;
typedef long long ll;
int n, q;
ll a[MAX];
struct SegmentTree{
    int l;
    int r;
    ll sum;
    ll add;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
}tree[MAX * 4];
void build(int p, int l , int r)
{
    l(p) = l; r(p) = r;
    if(l == r){
        sum(p) = a[l];
        return ;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    sum(p) = sum(p * 2) + sum(p * 2 + 1);
}

void spread(int p)
{
    if(add(p)){
        sum(p * 2) += add(p) * (r(p * 2) - l(p * 2) + 1);
        sum(p * 2 + 1) += add(p) * (r(p * 2 + 1) - l(p * 2 + 1) + 1);
        add(p * 2) += add(p);
        add(p * 2 + 1) += add(p);
        add(p) = 0;
    }
}

void change(int p, int l, int r, int d)
{
    if(l <= l(p) && r >= r(p)){
        sum(p) += (ll)d * (r(p) - l(p) + 1);
        add(p) += d;
        return ;
    }
    spread(p);
    int mid = (l(p) + r(p)) / 2;
    if(l <= mid)    change(p * 2, l, r, d);
    if(r > mid) change(p * 2 + 1, l, r, d);
    sum(p) = sum(p * 2) + sum(p * 2 + 1);
}

ll ask(int p, int l, int r)
{
    if(l <= l(p) && r >= r(p))  return sum(p);
    spread(p);
    int mid = (l(p) + r(p)) / 2;
    ll val = 0;
    if(l <= mid)    val += ask(p * 2, l, r);
    if(r > mid) val += ask(p * 2 + 1, l, r);
    return val;
}

int main()
{
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++)
        scanf("%lld", a + i);
    build(1, 1, n);
    char op[5];
    int x, y, z;
    for(int i = 1; i <= q; i++)
    {
        scanf("%s%d%d", op, &x, &y);
        if(op[0] == 'Q'){
            printf("%lld\n", ask(1, x, y));
        }
        else{
            scanf("%d", &z);
            change(1, x, y, z);
        }
    }
    return 0;
}

2.扫描线

// 扫描线 线段树
// accepted
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAX = 20005;
struct Edge{
    double x;
    double y1;
    double y2;
    int flag;
}e[MAX << 1];
struct SegmentTree{
    int l;
    int r;
    double len;
    int cnt;
}tree[MAX << 2];
double raw[MAX << 1];
int n, e_cnt, r_cnt;
bool cmp(const Edge &a, const Edge &b)
{
    return a.x < b.x;
}
void build(int p, int l, int r)
{
    tree[p].l = l;  tree[p].r = r;
    if(l == r){
        tree[p].len = 0;
        tree[p].cnt = 0;
        return ;
    }

    // 找了一整个上午加小半个晚上
    tree[p].cnt = 0;
    tree[p].len = 0;

    int mid = (l + r) >> 1;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
}
void pushDown(int p)
{
    if(tree[p].cnt >= 2)    tree[p].len = raw[tree[p].r + 1] - raw[tree[p].l];
    else if(tree[p].l == tree[p].r) tree[p].len = 0;
    else    tree[p].len = tree[p * 2].len + tree[p * 2 + 1].len;
}
void change(int p, int l, int r, int flag)
{
    // if(l <= tree[p].l && tree[p].r <= r){
    //     tree[p].cnt += flag;
    //     pushDown(p);
    //     return ;
    // }
    if(tree[p].l == tree[p].r){
        tree[p].cnt += flag;
        pushDown(p);
        return ;
    }
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(l <= mid)    change(p * 2, l, r, flag);
    if(r > mid) change(p * 2 + 1, l, r, flag);
    // tree[p].cnt = tree[p * 2].cnt + tree[p * 2 + 1].cnt;
    pushDown(p);
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        e_cnt = r_cnt = 0;

        double x1, x2, y1, y2;
        for(int i = 1; i <= n; i++)
        {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            e[++e_cnt].x = x1;  e[e_cnt].y1 = y1;   e[e_cnt].y2 = y2;   e[e_cnt].flag = 1;
            e[++e_cnt].x = x2;  e[e_cnt].y1 = y1;   e[e_cnt].y2 = y2;   e[e_cnt].flag = -1;
            raw[++r_cnt] = y1;
            raw[++r_cnt] = y2;
        }

        sort(e + 1, e + e_cnt + 1, cmp);

        sort(raw + 1, raw + r_cnt + 1);
        r_cnt = unique(raw + 1, raw + r_cnt + 1) - raw - 1;
        build(1, 1, r_cnt - 1);
        
        double res = 0;
        for(int i = 1; i < e_cnt; i++)
        {
            int val1 = lower_bound(raw + 1, raw + r_cnt + 1, e[i].y1) - raw;
            int val2 = lower_bound(raw + 1, raw + r_cnt + 1, e[i].y2) - raw; 
            change(1, val1, val2 - 1, e[i].flag);
            res += tree[1].len * (e[i + 1].x - e[i].x);
        }
        printf("%.2lf\n", res);
    }
    return 0;
}

3.区间最大值

// 线段树 区间最大值 模板 B题
// accepted
#include <stdio.h>
#include <algorithm>
using namespace std;
const int MAX = 2e5 + 5;
int a[MAX], n, m;
struct SegmentTree
{
    int l;
    int r;
    int dat;
}t[MAX * 4];

void build(int p, int l, int r)
{
    t[p].l = l; t[p].r = r;
    if(l == r){
        t[p].dat = a[l];
        return ;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    t[p].dat = max(t[p * 2].dat, t[p * 2 + 1].dat);
}

void change(int p, int x, int v)
{
    if(t[p].l == t[p].r){
        t[p].dat = v;
        return ;
    }
    int mid = (t[p].l + t[p].r) / 2;
    if(x <= mid)    change(p * 2, x, v);
    else    change(p * 2 + 1, x, v);
    t[p].dat = max(t[p * 2].dat, t[p * 2 + 1].dat);
}

int ask(int p, int l, int r)
{
    if(l <= t[p].l && r >= t[p].r)
        return t[p].dat;
    int mid = (t[p].l + t[p].r) / 2;
    int val = -(1 << 30);
    if(l <= mid)    val = max(val, ask(p * 2, l, r));
    if(r > mid) val = max(val, ask(p * 2 + 1, l, r));
    return val;
}

int main()
{
    char op[5];
    int x, y;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d", a + i);
        build(1, 1, n);
        for(int i = 1; i <= m; i++)
        {
            scanf("%s%d%d", op, &x, &y);
            if(op[0] == 'Q')
                printf("%d\n", ask(1, x, y));
            else
                change(1, x, y);
        }
    }
    return 0;
}

树上直径

1.两次bfs()

// 水图 两次bfs可以用来求树的直径
// accepted
#include <stdio.h>
#include <queue>
// #include <vector>
#include <string.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 5e4 + 5;
int head[MAXN], E_Cnt = 1, n, x, visited[MAXN];
struct Edge
{
    int v;
    ull w;
    int next;
};
Edge e[MAXN << 1];
void addEdge(int u, int v, ull w)
{
    e[E_Cnt].next = head[u];
    e[E_Cnt].v = v;
    e[E_Cnt].w = w;
    head[u] = E_Cnt++;
}
typedef pair<ull, int> pii;
// priority_queue<pii> pq;
queue<pii> pq;
ull maxlen;
int bfs(int m)
{
    int maxIndex;
    maxlen = 0;
    memset(visited, 0, sizeof(visited));
    pq.push(make_pair(0, m));
    while (!pq.empty())
    {
        ull d = pq.front().first;
        int u = pq.front().second;
        pq.pop();
        if (visited[u])
            continue;
        visited[u] = 1;
        if (maxlen < d)
        {
            maxlen = d;
            maxIndex = u;
        }
        for (int i = head[u]; i; i = e[i].next)
        {
            pq.push(make_pair(e[i].w + d, e[i].v));
        }
    }
    return maxIndex;
}
int main()
{
    // n 为边数 x 为起始点(求树上直径起始点无所谓)
    scanf("%d%d", &n, &x);
    int u, v;
    ull w, sum = 0;
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d%d%llu", &u, &v, &w);
        addEdge(u, v, w);
        addEdge(v, u, w);
        sum += w;
    }
    sum <<= 1;
    bfs(x);
    // 两次bfs  bfs(bfs(x));
    // maxlen即为直径 w 为一条边的长度
    printf("%llu\n", sum - maxlen);
    return 0;
}

单源最短路径

1.Dijkstra关联矩阵

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAX = 1005;
int t, n, Map[MAX][MAX], dist[MAX], visited[MAX];
int FindMinDist()
{
    int minDist = INF + 1, ret = -1;
    for(int i = 1; i <= n; i++)
        if(!visited[i] && dist[i] < minDist){
            minDist = dist[i];
            ret = i;
        }
    return ret;
}
int main()
{
    int a, b, c;
    // t 为边数 n 为点数
    while(scanf("%d%d", &t, &n) != EOF)
    {
        memset(visited, 0, sizeof(visited));
        memset(Map, 0x3f, sizeof(Map));
        for(int i = 0; i < t; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            if(c < Map[a][b])
                Map[a][b] = Map[b][a] = c;
        }
        for(int i = 1; i <= n; i++)
            dist[i] = Map[1][i];
        
        visited[1] = 1;
        while(1)
        {
            int v = FindMinDist();
            if(v == -1) break;
            visited[v] = 1;
            for(int i = 1; i <= n; i++)
                if(!visited[i])
                    dist[i] = min(dist[i], dist[v] + Map[v][i]);
        }
        printf("%d\n", dist[n]);
    }
    return 0;
}

2.Dijkstra前向星

// 标准模板 dijkstra算法 链式前向星存图 最小堆优化
// accepted
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 100005;
typedef pair<int, int> pii;
struct Edge{
    int v;
    int w;
    int next;
};
Edge e[MAX << 1];
int head[MAX], E_Cnt = 1, visited[MAX], n, m, s, dist[MAX];
priority_queue<pii, vector<pii>, greater<pii> > pq;
void add(int u, int v, int w)
{
    e[E_Cnt].next = head[u];
    e[E_Cnt].v = v;
    e[E_Cnt].w = w;
    head[u] = E_Cnt++;
}
int main()
{
    /*n 个点 m 条边 s 点到任一点最短路*/
    scanf("%d%d%d", &n, &m, &s);


    int u, v, w;
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    memset(dist, 0x4f, sizeof(int) * (n + 1));

    
    //dijkstra
    pq.push(make_pair(0, s));
    dist[s] = 0;
    while(!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if(visited[u])  continue;
        visited[u] = 1;
        for(int i = head[u]; i; i = e[i].next)
        {
            if(e[i].w + dist[u] < dist[e[i].v]){
                dist[e[i].v] = e[i].w + dist[u];
                pq.push(make_pair(dist[e[i].v], e[i].v));
            }
        }
    }



    int i;
    for(i = 1; i < n; i++)
        printf("%d ", dist[i]);
    printf("%d\n", dist[i]);
    return 0;
}

最小生成树

Prim关联矩阵

#include <stdio.h>
#include <string.h>
const int MAX = 105, INF = 0x3f3f3f3f;
int matrix[MAX][MAX], dist[MAX], n, m;
int FindMinDist()
{
    int minWeight = INF, ret = -1;
    for(int i = 1; i <= m; i++)
        if(dist[i] && dist[i] < minWeight){
            minWeight = dist[i];
            ret = i;
        }

    return ret;
}
int main()
{
    //  m 是点数，n 是边数
    while(scanf("%d", &n) != EOF && n)
    {
        scanf("%d", &m);

        memset(matrix, 0x3f, sizeof(matrix));
        
        int a, b, c;
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            matrix[a][b] = matrix[b][a] = c;
        }

        for(int i = 1; i <= m; i++)
        {
            dist[i] = matrix[1][i];
        }

        int totalWeight = 0, count = 0;
        dist[1] = 0;
        count++;
        while(1)
        {
            int v = FindMinDist();
            if(v == -1)
                break;
            totalWeight += dist[v];
            dist[v] = 0;
            count++;
            for(int i = 1; i <= m; i++)
            {
                if(dist[i] && matrix[v][i] < dist[i]){
                    dist[i] = matrix[v][i];
                }
            }
        }
        if(count == m)
            printf("%d\n", totalWeight);
        else
            printf("?\n");
    }
    return 0;
}

2.前向星

// 标准模板 prim算法 链式前向星存图 最小堆优化
// accepted
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 305;
const int MAXM = 100005;
int head[MAXN], E_Cnt = 1, dist[MAXN], visited[MAXN], n, m;
struct Edge{
    int v;
    int c;
    int next;
};
Edge e[MAXM];
typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii> > pq;
void addEdge(int u, int v, int c)
{
    e[E_Cnt].next = head[u];
    e[E_Cnt].v = v;
    e[E_Cnt].c = c;
    head[u] = E_Cnt++;
}
int main()
{
    scanf("%d%d", &n, &m);
    int u, v, c;
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d", &u, &v, &c);
        addEdge(u, v, c);
        addEdge(v, u, c);
    }
    memset(dist, 0x4f, sizeof(dist));

    /*******非模板代码部分*****/
    int maxWeight = 0;
    /************************/

    dist[1] = 0;
    pq.push(make_pair(0, 1));
    while(!pq.empty())
    {
        int d = pq.top().first, u = pq.top().second;
        pq.pop();

        /*****visited在这里用******/
        if(visited[u])  continue;
        visited[u] = 1;
        /*************************/
        
        /****非模板代码部分****/
        maxWeight = max(maxWeight, d);
        /*********************/

        for(int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v, w = e[i].c;
            if(w < dist[v]){
                dist[v] = w;
                pq.push(make_pair(w, v));
            }
        }
    }
    printf("%d %d\n", n - 1, maxWeight);
    return 0;
}