更好的观看体验

目录

• 并查集
• 树状数组
• 线段树
• 平衡树
• 可持久化数据结构
• AC自动机

并查集

模板： 836. 合并集合

//init() : O(n)
//find() : O(log(n)) 或 O(小常数)
//merge() : O(log(n)) 或 O(小常数)

void init()
{
    for(int i=1;i<=n;i++)
        fa[i] = i;
}

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

void merge(int a,int b)
{
    a = find(a);
    b = find(b);

    if(a == b) return;
    fa[a] = b;
}

模型一 : 检查是否存在环 1250. 格子游戏

通过不断连边归并集合，如果一个集合里得两点再次连边则存在环

/*
struct Edge{
    int a,b; // 代表a - b 存在一条无向边
}edge;
*/

for(auto e : edge)
{
    int a = find(e.a);
    int b = find(e.b);

    if(a == b) // 存在环
    {
        break; 
    }
    merge(a,b);
}

模型二 : 捆绑购买问题 1252. 搭配购买

将捆绑购买的物品看作一个物品

void merge(int a,int b)
{
    a = find(a);
    b = find(b);
    if(a==b) return;
    fa[a] = b;
    c[b] += c[a]; // 体积
    w[b] += w[a]; // 价值
}

模型三 ： 离线处理 237. 程序自动分析

先合并相同集合的，再检测集合是否存在冲突。

//get是离散化

// 合并集合
for(int i=0;i<n;i++)
    if(query[i].ans == 1)
        merge(get(query[i].a),get(query[i].b));


bool flag = true;

// 检查合法性
for(int i=0;i<n;i++)
    if(query[i].ans == 0)
    {
        int a = get(query[i].a);
        int b = get(query[i].b);
        if(find(a) == find(b))
        {    
            flag = false;
            break;
        }
    }

模型四 ： 带边权 与 扩展域 AcWing 239. 奇偶游戏 240. 食物链

带边权：本蒟蒻暂时不会QWQ，基本都用扩展域解决了。以后补上~

扩展域 : 以奇偶游戏为例，A集合 与 B 集合 奇偶性不同，那么与A集合奇偶性不同的集合与B奇偶性相同，与B集合奇偶性不同得集合与A集合奇偶性相同，所以我们同时维护与集合奇偶性相同的集合以及与集合奇偶性不同的集合，才能维护所有集合

// a 维护与集合a相同得集合  a + cnt 维护与集合a不同的集合
for (int i = 1; i <= m; i++)
{
    int a = get(query[i].a - 1);
    int b = get(query[i].b);

    if (query[i].ans == 0)
    {
        if (find(a) == find(b + cnt))
        {
            printf("%d\n", i - 1);
            return 0;
        }
        merge(a, b);
        merge(a + cnt, b + cnt);
    }
    else
    {
        if (find(a) == find(b))
        {
            printf("%d\n", i - 1);
            return 0;
        }
        merge(a + cnt, b);
        merge(a, b + cnt);
    }
}

模型五 ： 维护其他属性 AcWing 238. 银河英雄传说

维护集合的同时维护到根的距离，以及集合大小

int fa[N],Size[N],s[N]; // 集合，集合大小，点到根的距离

int find(int x)
{
    if(x!=fa[x])
    {
        int root = find(fa[x]);
        s[x] += s[fa[x]];
        fa[x] = root;
    }
    return fa[x];
}

void merge(int a,int b)
{
    a = find(a) , b = find(b);

    if(a==b) return ;

    s[a] = Size[b];
    Size[b] += Size[a];
    fa[a] = b;

}

int query(int a,int b)
{
    int pa = find(a) , pb = find(b);

    if(pa != pb) return -1;

    return max(0,abs(s[a] - s[b]) - 1);
}

树状数组

模板： AcWing 242. 一个简单的整数问题

ll d[N];

inline int lowbit(int x)
{
    return x & - x;
}

void add(int a,int b) // 在a位置 + b O(log(n))
{
    for(int i=a;i<=n;i+=lowbit(i)) d[i] += b;
}

ll sum(int x)       // 查询 1 ~ x 的前缀和 O(log(n))
{
    ll res = 0;

    for(int i=x;i;i-=lowbit(i)) res += d[i];

    return res;
}

模型一 : 查询值域分布 AcWing 241. 楼兰图腾 788. 逆序对的数量

由于树状数组的高效add，我们可以维护值域分布，数值在[l,r]的数有多少个

for (int i = 1; i <= n; i++)
{
    int x = a[i];

    left_g[i] = ask(n) - ask(x); // 查询 数值在[x + 1,n]有多少个数
    left_s[i] = ask(x - 1); // 查询 数值在[1,x - 1] 有多少个数

    add(x, 1);
}

模型二 : 二分 + 树状数组 AcWing 244. 谜一样的牛 106. 动态中位数

int get(int x)
{
    int l = 1 , r = n;

    while(l<r)
    {
        int mid = l + r >> 1;
        if(sum(mid) >= x) r = mid;
        else l = mid + 1;
    }

    return r;
}

线段树

模板： AcWing 1275. 最大数 AcWing 243. 一个简单的整数问题2

ps : 前一题只有单点修改，后一题基本覆盖了线段树的所有方法

struct Seg{
    int l,r,add; // 左右区间，懒标记
    ll sum; // 区间和
};

Seg seg[N << 2];

void push_up(int u) //自下而上维护上面的节点
{
    seg[u].sum = seg[u << 1].sum + seg[u << 1 | 1].sum;
}

void push_down(int u) // 自上而下维护下面的节点
{
    Seg &root = seg[u] , &left = seg[u << 1] , &right = seg[u << 1 | 1];

    if(root.add)
    {
        left.add += root.add , left.sum += 1ll * (left.r - left.l + 1) * root.add;
        right.add += root.add , right.sum += 1ll * (right.r - right.l + 1) * root.add; 
        root.add = 0;
    }
}

void build(int u,int l,int r) //  O(n * log(n))  建树
{
    if(l == r)
    {
        seg[u].l = l;
        seg[u].r = r;
        seg[u].sum = w[r];
        seg[u].add = 0;
        return;
    }

    seg[u].l = l;
    seg[u].r = r;

    int mid = l + r >> 1;

    build(u << 1,l,mid);
    build(u << 1 | 1,mid + 1,r);

    push_up(u);
}

void modify(int u,int l,int r,int d) // O(log(n)) 区间修改
{
    if(l <= seg[u].l && r >= seg[u].r)
    {
        seg[u].sum += 1ll * (seg[u].r - seg[u].l + 1) * d;
        seg[u].add += d;
        return ;
    }

    push_down(u);

    int mid = seg[u].l + seg[u].r >> 1;

    if(l <= mid) modify(u << 1,l,r,d);
    if(r > mid) modify(u << 1 | 1,l,r,d);

    push_up(u);
}

ll query(int u , int l , int r)  // 区间查询 O(log(n)) 
{
    if(l <= seg[u].l && r >= seg[u].r)
        return seg[u].sum;

    push_down(u);

    int mid = seg[u].l + seg[u].r >> 1;
    ll sum = 0;
    if(l <= mid) sum = query(u << 1 , l , r);
    if(r > mid) sum += query(u << 1 | 1, l ,r);

    return sum;
}

模型一 ：维护差分 AcWing 246. 区间最大公约数

void modify(int u,int p,ll x) // 单点修改
{
    if(seg[u].l == p && seg[u].r == p)
    {
        ll value = x + seg[u].sum;
        seg[u].sum = seg[u].d = value;
        return;
    }

    int mid = seg[u].l + seg[u].r >> 1;

    if(p <= mid) modify(u << 1,p,x);
    else modify(u << 1 | 1,p,x);

    push_up(u);
}

// 维护差分
modify(1,l,x);
if(r  + 1 <= n) modify(1,r + 1, -x);

模型二 ：维护乘法和加法 AcWing 1277. 维护序列

struct Tree{
    int l,r;
    ll sum,mul,add;
};

void pushup(int u)
{
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % mod;
}

void eval(Tree &a,int mul,int add)
{
    a.sum = ((ll)a.sum * mul % mod + (ll)(a.r - a.l + 1) * add % mod) % mod;
    a.mul = ((ll)a.mul * mul) % mod;
    a.add = (a.add * mul % mod + add) % mod;
}

void pushdown(int u)
{
    eval(tr[u << 1],tr[u].mul,tr[u].add);
    eval(tr[u << 1 | 1],tr[u].mul,tr[u].add);
    tr[u].mul = 1;
    tr[u].add = 0;
}

模型三 ：扫描线 AcWing 247. 亚特兰蒂斯

struct Segment
{
    double x, y1, y2;
    int k;
    bool operator< (const Segment &t)const
    {
        return x < t.x;
    }
}seg[N * 2];

struct Node
{
    int l, r;
    int cnt;
    double len;
}tr[N * 8];

void push_up(int u)
{
    if (tr[u].cnt) tr[u].len = v[tr[u].r + 1] - v[tr[u].l];
    else if (tr[u].l != tr[u].r)
    {
        tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
    }
    else tr[u].len = 0;
}

void modify(int u,int l,int r,int k)
{

    if (tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].cnt += k;
        push_up(u);
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, k);
        if (r > mid) modify(u << 1 | 1, l, r, k);
        push_up(u);
    }

}

for(int i=0;i<2*n;i++)
{
    if(i) res += tr[1].len * (seg[i].x - seg[i - 1].x); 
    modify(1, get(seg[i].y1), get(seg[i].y2) - 1, seg[i].k);
}

模型四 ：优化DP AcWing 296. 清理班次2

//无线段树版本
for(int i=1;i<=n;i++)
{
    int a = cow[i].l;
    int b = cow[i].r;
    int c = cow[i].c;
    for(int i=a-1;i<=b;i++)
        f[b] = min(f[b],f[i] + c),
}

// 用线段树来优化DP查找最小值的过程
for(int i=1;i<=n;i++)
{
    int a = cow[i].l;
    int b = cow[i].r;
    int c = cow[i].c;
    f[b] = min(f[b],query(1,a - 1, b) + c);
    modify(1,b,f[b]);
}

平衡树 （treap)

模板 : AcWing 253. 普通平衡树

const int N = 1e5 + 10,INF = 1e8;

struct Node{
    int l,r;
    int key,val;
    int cnt,size;
};

Node tr[N];

int idx,root;

void pushup(int u)
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

void zig(int &p) // 右旋
{
    int q = tr[p].l;
    tr[p].l = tr[q].r,tr[q].r = p,p = q;

    pushup(tr[p].r);
    pushup(p);
}

void zag(int &p) // 左旋
{
    int q = tr[p].r;
    tr[p].r = tr[q].l,tr[q].l = p, p = q;

    pushup(tr[p].l);
    pushup(p);
}

int get_node(int key)
{
    tr[++idx].key = key;
    tr[idx].cnt = tr[idx].size = 1;
    tr[idx].val = rand();

    return idx;
}

void build() // 建树 O(1)
{
    root = 1;

    get_node(-INF);
    get_node(INF);

    tr[1].r = 2;

    pushup(root);

    if(tr[1].val < tr[2].val) zag(root);
}

void insert(int &p,int key) // 插入 O(log(n))
{
    if(!p) p = get_node(key);
    else if(tr[p].key == key) tr[p].cnt ++ ;
    else if(key < tr[p].key)
    {
        insert(tr[p].l,key);
        if(tr[tr[p].l].val > tr[p].val) zig(p);
    }
    else
    {
        insert(tr[p].r,key);
        if(tr[tr[p].r].val > tr[p].val) zag(p);
    }
    pushup(p);
}

void remove(int &p,int key) // 删除 O(log(n))
{
    if(!p) return;

    if(tr[p].key == key)
    {
        if(tr[p].cnt > 1) tr[p].cnt -- ;
        else if(tr[p].l || tr[p].r)
        {
            if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
            {
                zig(p);
                remove(tr[p].r,key);
            }
            else
            {
                zag(p);
                remove(tr[p].l,key);
            }
        }
        else p = 0;

    }
    else if(key > tr[p].key) remove(tr[p].r,key);
    else remove(tr[p].l,key);

    pushup(p);
}

int get_rank_by_key(int p,int key) // 查询某一值的排名 O(log(n))
{
    if(!p) return INF;
    if(tr[p].key == key) return tr[tr[p].l].size + 1;
    if(tr[p].key > key) return get_rank_by_key(tr[p].l,key);

    return get_rank_by_key(tr[p].r,key) + tr[tr[p].l].size + tr[p].cnt;
}

int get_key_by_rank(int p,int rank) // 查询K大值 O(log(n))
{
    if(!p) return INF;

    if (tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
    if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;

    return get_key_by_rank(tr[p].r,rank - tr[p].cnt - tr[tr[p].l].size);
}

int get_prev(int p,int key) // 小于key最大
{
    if(!p) return -INF;
    else if(tr[p].key >= key) return get_prev(tr[p].l,key);
    else return max(tr[p].key,get_prev(tr[p].r,key));
}

int get_nexv(int p,int key) // 大于key最小
{
    if(!p) return INF;
    else if(tr[p].key <= key) return get_nexv(tr[p].r,key);
    else return min(tr[p].key,get_nexv(tr[p].l,key));
}

可持久化数据结构

模板一 : 可持久化trie AcWing 256. 最大异或和

const int N = 6e5 + 10,M = 25 * N;

int s[N];
int son[M][2],maxid[M],root[N],idx;
int n,m;

void insert(int i,int k,int p,int q)
{
    if(k < 0)
    {
        maxid[q] = i;
        return ;
    }

    int v = s[i] >> k & 1;

    if(p) son[q][v ^ 1] = son[p][v ^ 1];

    son[q][v] = ++ idx;
    insert(i,k - 1,son[p][v],son[q][v]);
    maxid[q] = max(maxid[son[q][0]],maxid[son[q][1]]);
}

int query(int root,int x,int l)
{
    int p = root;
    for(int i=23;i>=0;i--)
    {
        int v = x >> i & 1;
        if(maxid[son[p][!v]] >= l) p = son[p][!v];
        else p = son[p][v];
    }

    return x ^ s[maxid[p]];
}

模板二 : 可持久化线段树（主席树） AcWing 255. 第K小数

struct Node{
    int l,r;
    int cnt;
};

Node tr[N * (4 + 17)];
int n,m,a[N];
int root[N],idx;
vector<int> v;


int build(int l,int r)
{
   int p = ++ idx;

   if(l == r)
   {
       tr[p].l = l;
       tr[p].r = r;
       tr[p].cnt = 0;
       return p;
   }

   int mid = l + r >> 1;

   tr[p].l = build(l,mid);
   tr[p].r = build(mid + 1,r);
   tr[p].cnt = 0;

   return p;
}

int insert(int p,int l,int r,int x)
{
    int q = ++ idx;
    tr[q] = tr[p];
    if(l == r)
    {
        tr[q].cnt ++;
        return q;
    }

    int mid = l + r >> 1;
    if(x <= mid) tr[q].l = insert(tr[p].l,l,mid,x);
    else tr[q].r = insert(tr[q].r,mid + 1,r,x);

    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;

    return q;
}

int query(int q,int p,int l,int r,int k)
{
    if(l == r) return r;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1;
    if(k <= cnt) return query(tr[q].l,tr[p].l,l,mid,k);
    else return query(tr[q].r,tr[p].r,mid + 1,r,k - cnt);
}

AC自动机

模板 : AcWing 1282. 搜索关键词

//时间复杂度 O(n * m)

int tr[N * S][26],cnt[N * S],ne[N * S],q[N * S],idx;

string str;

void insert()
{
    int p = 0;

    for(int i=0;i<str.size();i++)
    {
        int c = str[i] - 'a';
        if(!tr[p][c]) tr[p][c] = ++ idx;
        p = tr[p][c];
    }

    cnt[p] ++ ;
}

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];


    while(tt >= hh)
    {
        int t = q[hh ++ ];
        for(int i=0;i<26;i++)
        {
            int p = tr[t][i];
            if(!p) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[++tt] = p;
            }
        }
    }

}

int res = 0;

for (int i = 0, j = 0; i < str.size(); i++)
{
    int c = str[i] - 'a';
    j = tr[j][c];

    int p = j;
    while (p)
    {
        res += cnt[p];
        cnt[p] = 0;
        p = ne[p];
    }
}

cout << res << endl;

最长上升子序列(三)

题目链接

const int N = 100010;
class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */

    int g[N], a[N], last[N];
    vector<int> LIS(vector<int>& arr) {
        memset(g, 0, sizeof g);
        int n = arr.size(), len = 0;

        a[0] = -1;
        for(int i = 1; i <= n; i ++)
        {
            a[i] = arr[i - 1];

            int l = 0, r = len;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(a[i] > a[g[mid]])  l = mid;
                else  r = mid - 1;
            }
            last[i] = g[l];
            g[l + 1] = i;
            if(l + 1 > len)  len ++;

            //for(int i = 1; i <= len; i ++)  printf("%d ", a[g[i]]);  puts("");
        }
        vector<int> res;
        for(int i = g[len]; i; i = last[i])  res.push_back(a[i]);
        reverse(res.begin(), res.end());
        return res;
    }
};

三元环计数

O(m$\sqrt{m}$)

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 3010;

struct Edge
{
    int u, v;
} e[N * N];

char s[N][N];
int deg[N], vis[N];
vector<int> g[N];
int n, m;

int main()
{

    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);

    memset(vis, -1, sizeof vis);

    scanf("%d", &n);

    ll ans = 0;

    for (int i = 0; i < n; i++)
    {
        scanf("%s", &s[i]);
        for (int j = i + 1; j < n; j++)
            if (s[i][j] == '1')
            {
                deg[i]++;
                deg[j]++;
                e[++m] = {i, j};
            }
    }

    for (int i = 1; i <= m; i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        if (deg[u] < deg[v] || (deg[u] == deg[v] && u > v))
            swap(u, v);
        g[u].push_back(v);
    }

    for (int x = 0; x < n; x++)
    {
        for (auto y : g[x])
            vis[y] = x;
        for (auto y : g[x])
            for (auto z : g[y])
                if (vis[z] == x)
                {
                    ++ans;
                }
    }

    printf("%lld\n", ans);

    return 0;
}

最小环

• 做法1 枚举每条边，把正在枚举的边删掉，求Dijkstra,求得每个环的大小 O(m * (n + m) * logn)
• 做法2 Floyd O(n^3)

(a + b) = (a ^ b) + 2 * (a & b)

三分

ll bin3(int l,int r)
{
    if(l>r) return -INF;
    ll res=max(f(l),f(r));
    while(l<=r){
        int m=(l+r)>>1,mm=(m+r)>>1;
        ll fm=f(m),fmm=f(mm);
        if(fm<=fmm) l=m+1;
        else r=mm-1;
        res=max(res,max(fm,fmm));
    }
    return res;
}

用栈维护[l,r]的最大合法解（避免逆操作）

    for(int l=0,tt=0,r=1;r<=n;r++ ) {
        cur = cur * w[r];

        while((VS * stk[l] * cur)[m - 1] > k) {
            l ++ ;
            if(l > tt) {
                stk[r] = w[r];
                for(int i=r-1;i>tt;i--){
                    stk[i] = w[i]*stk[i+1];
                }
                tt = r;
                cur = MS;
            }
        }
        res = max(res,r - l + 1);
    }