头像

Aigrl

是一只喜欢魔法少女的初中生 $\color{red}{♡⃝︒ᴴᴬᴾᴾᵞ ᵂᴱᴱᴷᴱᴺᴰ}$〃•ω$‹$〃




离线:22小时前


最近来访(1254)
用户头像
垫底抽風
用户头像
小小_88
用户头像
云衣醉梦
用户头像
kammaron93
用户头像
三三得玖
用户头像
hncsxzx
用户头像
ididiid
用户头像
不拿NOI金牌不改名
用户头像
不高兴的兽奶
用户头像
whale77
用户头像
我不是子龙
用户头像
夜寐
用户头像
牧濑红莉栖
用户头像
Isaac_
用户头像
ACdefly
用户头像
第十三颗光玉
用户头像
Ycary
用户头像
Cofe_Milk
用户头像
Moyou
用户头像
GongYe


Aigrl
1天前

很直观的一种算法。

点分治

找出重心,然后对子树分治统计。

由于每一层的所有递归过程合计对每个点处理一次,所以复杂度为 $O(nlogn)$。

具体过程是 $trick$。

点分树

即动态点分治,用来解决 带点权/边权修改 的树上路径信息统计问题。

在查询和修改的时候,我们在点分树上暴力跳父亲修改。

我们可以用 $LCA$ 统计一个结点到其点分树上的祖先的距离等其他信息。

注意:一个结点到其点分树上的祖先的距离不一定递增,不能累加!

在动态点分治的过程中,一个结点在其点分树上的祖先结点的信息中可能会被重复计算,这是我们需要消去重复部分的影响。一般的方法是对于一个连通块用两种方式记录:一个是其到分治中心的距离信息,另一个是其到点分树上分治中心父亲的距离信息。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 150010, M = N * 2;

int n, m, A;
int h[N], e[M], w[M], ne[M], idx;
int age[N];
bool st[N];
struct Father
{
    int u, num;
    LL dist;
};
vector<Father> f[N];
struct Son
{
    int age;
    LL dist;
    bool operator< (const Son& t) const
    {
        return age < t.age;
    }
};
vector<Son> son[N][3];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int get_size(int u, int fa)
{
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i])
        if (e[i] != fa)
            res += get_size(e[i], u);
    return res;
}

int get_wc(int u, int fa, int tot, int& wc)
{
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        ms = max(ms, t);
        sum += t;
    }
    ms = max(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void get_dist(int u, int fa, LL dist, int wc, int k, vector<Son>& p)
{
    if (st[u]) return;
    f[u].push_back({wc, k, dist});
    p.push_back({age[u], dist});
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        get_dist(j, u, dist + w[i], wc, k, p);
    }
}

void calc(int u)
{
    if (st[u]) return;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;

    for (int i = h[u], k = 0; ~i; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;
        auto& p = son[u][k];
        p.push_back({-1, 0}), p.push_back({A + 1, 0});
        get_dist(j, -1, w[i], u, k, p);
        k ++ ;
        sort(p.begin(), p.end());
        for (int i = 1; i < p.size(); i ++ ) p[i].dist += p[i - 1].dist;
    }

    for (int i = h[u]; ~i; i = ne[i]) calc(e[i]);
}

LL query(int u, int l, int r)
{
    LL res = 0;
    for (auto& t: f[u])
    {
        int g = age[t.u];
        if (g >= l && g <= r) res += t.dist;
        for (int i = 0; i < 3; i ++ )
        {
            if (i == t.num) continue;
            auto& p = son[t.u][i];
            if (p.empty()) continue;
            int a = lower_bound(p.begin(), p.end(), Son({l, -1})) - p.begin();
            int b = lower_bound(p.begin(), p.end(), Son({r + 1, -1})) - p.begin();
            res += t.dist * (b - a) + p[b - 1].dist - p[a - 1].dist;
        }
    }

    for (int i = 0; i < 3; i ++ )
    {
        auto& p = son[u][i];
        if (p.empty()) continue;
        int a = lower_bound(p.begin(), p.end(), Son({l, -1})) - p.begin();
        int b = lower_bound(p.begin(), p.end(), Son({r + 1, -1})) - p.begin();
        res += p[b - 1].dist - p[a - 1].dist;
    }

    return res;
}

int main()
{
    scanf("%d%d%d", &n, &m, &A);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &age[i]);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    calc(1);
    LL res = 0;
    while (m -- )
    {
        int u, a, b;
        scanf("%d%d%d", &u, &a, &b);
        int l = (a + res) % A, r = (b + res) % A;
        if (l > r) swap(l, r);
        res = query(u, l, r);
        printf("%lld\n", res);
    }

    return 0;
}


活动打卡代码 AcWing 2226. 开店

Aigrl
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 150010, M = N * 2;

int n, m, A;
int h[N], e[M], w[M], ne[M], idx;
int age[N];
bool st[N];
struct Father
{
    int u, num;
    LL dist;
};
vector<Father> f[N];
struct Son
{
    int age;
    LL dist;
    bool operator< (const Son& t) const
    {
        return age < t.age;
    }
};
vector<Son> son[N][3];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int get_size(int u, int fa)
{
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i])
        if (e[i] != fa)
            res += get_size(e[i], u);
    return res;
}

int get_wc(int u, int fa, int tot, int& wc)
{
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        ms = max(ms, t);
        sum += t;
    }
    ms = max(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void get_dist(int u, int fa, LL dist, int wc, int k, vector<Son>& p)
{
    if (st[u]) return;
    f[u].push_back({wc, k, dist});
    p.push_back({age[u], dist});
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        get_dist(j, u, dist + w[i], wc, k, p);
    }
}

void calc(int u)
{
    if (st[u]) return;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;

    for (int i = h[u], k = 0; ~i; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;
        auto& p = son[u][k];
        p.push_back({-1, 0}), p.push_back({A + 1, 0});
        get_dist(j, -1, w[i], u, k, p);
        k ++ ;
        sort(p.begin(), p.end());
        for (int i = 1; i < p.size(); i ++ ) p[i].dist += p[i - 1].dist;
    }

    for (int i = h[u]; ~i; i = ne[i]) calc(e[i]);
}

LL query(int u, int l, int r)
{
    LL res = 0;
    for (auto& t: f[u])
    {
        int g = age[t.u];
        if (g >= l && g <= r) res += t.dist;
        for (int i = 0; i < 3; i ++ )
        {
            if (i == t.num) continue;
            auto& p = son[t.u][i];
            if (p.empty()) continue;
            int a = lower_bound(p.begin(), p.end(), Son({l, -1})) - p.begin();
            int b = lower_bound(p.begin(), p.end(), Son({r + 1, -1})) - p.begin();
            res += t.dist * (b - a) + p[b - 1].dist - p[a - 1].dist;
        }
    }

    for (int i = 0; i < 3; i ++ )
    {
        auto& p = son[u][i];
        if (p.empty()) continue;
        int a = lower_bound(p.begin(), p.end(), Son({l, -1})) - p.begin();
        int b = lower_bound(p.begin(), p.end(), Son({r + 1, -1})) - p.begin();
        res += p[b - 1].dist - p[a - 1].dist;
    }

    return res;
}

int main()
{
    scanf("%d%d%d", &n, &m, &A);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &age[i]);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    calc(1);
    LL res = 0;
    while (m -- )
    {
        int u, a, b;
        scanf("%d%d%d", &u, &a, &b);
        int l = (a + res) % A, r = (b + res) % A;
        if (l > r) swap(l, r);
        res = query(u, l, r);
        printf("%lld\n", res);
    }

    return 0;
}


活动打卡代码 AcWing 264. 权值

Aigrl
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 200010, M = N * 2, S = 1000010, INF = 0x3f3f3f3f;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int f[S], ans = INF;
PII p[N], q[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int get_size(int u, int fa)
{
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        res += get_size(j, u);
    }
    return res;
}

int get_wc(int u, int fa, int tot, int& wc)
{
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        int t = get_wc(j, u, tot, wc);
        ms = max(ms, t);
        sum += t;
    }
    ms = max(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void get_dist(int u, int fa, int dist, int cnt, int& qt)
{
    if (st[u] || dist > m) return;
    q[qt ++ ] = {dist, cnt};
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        get_dist(j, u, dist + w[i], cnt + 1, qt);
    }
}

void calc(int u)
{
    if (st[u]) return;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;

    int pt = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i], qt = 0;
        get_dist(j, u, w[i], 1, qt);
        for (int k = 0; k < qt; k ++ )
        {
            auto& t = q[k];
            if (t.x == m) ans = min(ans, t.y);
            ans = min(ans, f[m - t.x] + t.y);
            p[pt ++ ] = t;
        }
        for (int k = 0; k < qt; k ++ )
        {
            auto& t = q[k];
            f[t.x] = min(f[t.x], t.y);
        }
    }
    for (int i = 0; i < pt; i ++ )
        f[p[i].x] = INF;

    for (int i = h[u]; ~i; i = ne[i]) calc(e[i]);
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    memset(f, 0x3f, sizeof f);
    calc(0);

    if (ans == INF) ans = -1;
    printf("%d\n", ans);

    return 0;
}


活动打卡代码 AcWing 252. 树

Aigrl
1天前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10, M = 2e4 + 10;

int n, m;
int h[N], e[M], ne[M], w[M], idx;
bool st[N];
int q[N], p[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

int get_size(int u, int father)
{
    if (st[u]) return 0;
    int res = 1;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        res += get_size(j, u);
    }
    return res;
}

int get_wc(int u, int father, int tot, int &wc)
{
    if (st[u]) return 0;
    int sum = 1, ms = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        int t = get_wc(j, u, tot, wc);
        ms = max(ms, t);
        sum += t;
    }
    ms = max(ms, tot - sum);
    if (ms <= tot / 2) wc = u;
    return sum;
}

void get_dist(int u, int father, int dist, int &qt)
{
    if (st[u]) return;
    q[qt ++ ] = dist;
    for (int i = h[u]; i != -1; i = ne[i])
        if (e[i] != father)
        {
            get_dist(e[i], u, dist + w[i], qt);
        }
}

int get(int a[], int k)
{
    sort(a, a + k);
    int res = 0;
    for (int i = k-1, j = -1; i >= 0; i -- )
    {
        while (j + 1 < i && a[j + 1] + a[i] <= m) j ++;
        j = min(j, i-1);
        res += j + 1;
    }
    return res;
}

int calc(int u)
{
    if (st[u]) return 0;
    int res = 0;
    get_wc(u, -1, get_size(u, -1), u);
    st[u] = true;
    int pt = 0;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i], qt = 0;
        get_dist(j, -1, w[i], qt);
        res -= get(q, qt);
        for (int k = 0; k < qt; k ++ )
        {
            if (q[k] <= m) res ++;
            p[pt ++ ] = q[k];
        }
    }
    res += get(p, pt);
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        res += calc(j);
    }
    return res;
}

int main()
{
    while (scanf("%d%d", &n, &m), n || m)
    {
        idx = 0;
        memset(h, -1, sizeof h);
        memset(st, 0, sizeof st);
        for (int i = 1; i < n; i ++ )
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c), add(b, a, c);
        }
        printf("%d\n", calc(0));
    }
    return 0;
}


活动打卡代码 AcWing 1053. 修复DNA

Aigrl
1天前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int tr[N][4], dar[N], idx;
int q[N], ne[N];
char str[N];

int f[N][N];

int get(char c)
{
    if (c == 'A') return 0;
    if (c == 'T') return 1;
    if (c == 'G') return 2;
    return 3;
}

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int t = get(str[i]);
        if (tr[p][t] == 0) tr[p][t] = ++ idx;
        p = tr[p][t];
    }
    dar[p] = 1;
}

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

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 0; i < 4; 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;
                dar[p] |= dar[ne[p]];
            }
        }
    }
}

int main()
{
    int T = 1;
    while (scanf("%d", &n), n)
    {
        memset(tr, 0, sizeof tr);
        memset(dar, 0, sizeof dar);
        memset(ne, 0, sizeof ne);
        idx = 0;

        for (int i = 0; i < n; i ++ )
        {
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str + 1);
        m = strlen(str + 1);

        memset(f, 0x3f, sizeof f);
        f[0][0] = 0;
        for (int i = 0; i < m; i ++ )
            for (int j = 0; j <= idx; j ++ )
                for (int k = 0; k < 4; k ++ )
                {
                    int t = get(str[i + 1]) != k;
                    int p = tr[j][k];
                    if (!dar[p]) f[i + 1][p] = min(f[i + 1][p], f[i][j] + t);
                }

        int res = 0x3f3f3f3f;
        for (int i = 0; i <= idx; i ++ ) res = min(res, f[m][i]);

        if (res == 0x3f3f3f3f) res = -1;
        printf("Case %d: %d\n", T ++, res);
    }

    return 0;
}


新鲜事 原文

Aigrl
1天前
自动机=DP(暴论


活动打卡代码 AcWing 1282. 搜索关键词

Aigrl
1天前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, S = 55, M = 1000010;

int n;
int tr[N * S][26], cnt[N * S], idx;
char str[M];
int q[N * S], ne[N * S];

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int t = str[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];
    }
    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 (hh <= tt)
    {
        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 main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        scanf("%d", &n);
        for (int i = 0; i < n; i ++ )
        {
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str);

        int res = 0;
        for (int i = 0, j = 0; str[i]; i ++ )
        {
            int t = str[i] - 'a';
            j = tr[j][t];

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

        printf("%d\n", res);
    }

    return 0;
}


活动打卡代码 AcWing 1285. 单词

Aigrl
1天前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
int tr[N][26], f[N], idx;
int q[N], ne[N];
char str[N];
int id[210];

void insert(int x)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int t = str[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];
        f[p] ++ ;
    }
    id[x] = 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 (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 0; i < 26; i ++ )
        {
            int &p = tr[t][i];
            if (!p) p = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[ ++ tt] = p;
            }
        }
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ )
    {
        scanf("%s", str);
        insert(i);
    }

    build();

    for (int i = idx - 1; i >= 0; i -- ) f[ne[q[i]]] += f[q[i]];

    for (int i = 0; i < n; i ++ ) printf("%d\n", f[id[i]]);

    return 0;
}


活动打卡代码 AcWing 3188. manacher算法

Aigrl
1天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e7 + 10;

int n;
char a[N], b[N];
int p[N];

void init()
{
    int k = 0;
    b[k ++ ] = '$', b[k ++ ] = '#';
    for (int i = 0; i < n; i ++ ) b[k ++ ] = a[i], b[k ++ ] = '#';
    b[k ++ ] = '^';
    n = k;
}

void manacher()
{
    int mr = 0, mid;
    for (int i = 1; i < n; i ++ )
    {
        if (i < mr) p[i] = min(p[mid * 2 - i], mr - i);
        else p[i] = 1;
        while (b[i - p[i]] == b[i + p[i]]) p[i] ++ ;
        if (i + p[i] > mr)
        {
            mr = i + p[i];
            mid = i;
        }
    }
}

int main()
{
    scanf("%s", a);
    n = strlen(a);

    init();
    manacher();

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, p[i]);
    printf("%d\n", res - 1);

    return 0;
}



Aigrl
1天前

(K)MP

作用:在文本串s中快速查找模式串p的所有位置。

本质:π(i) = s{0…x-1} == s{i-x+1…i} 中最大的x

$pmt[i]:$ 从$p[0]$往后数、同时从$p[i]$往前数相同的位数,在保证前后缀相同的情况下,最多能数多少位。

$next[i]:$ 储存可以匹配上的文本串$s$的位置。

其实并不用掌握真正的KMP就够用了。

板子

KMP自动机

KMP 自动机就是一个不断读入待匹配串,每次匹配时走到接受状态的 DFA。

EXKMP

作用:$O(n)$求出一个字符串的所有后缀与一个字符串的的最长公共前缀的长度。

本质:Z(i) = s{0…x-1} == s{i…i+x-1} 中最大的x

具体讲解

板子

$ext[i]:$ 表示文本串的子串$s[i,x−1]$与$p$的最长公共前缀的长度。

$z[i]:$ 表示模板串的子串$p[i,x−1]$与$p$的最长公共前缀的长度。

Manacher

作用:与回文子串有关

本质:d(i): 以s[i]为中心的奇回文子串的数量。

类似EXKMP。

板子

SA

本质:sa[i]:将所有后缀排序后第 i 小的后缀的编号

rk[i]:表示后缀 i 的排名,是重要的辅助数组,(sa[rk[i]] == rk[sa[i]] == i)

板子

Trie

本质:接受且仅接受指定的字符串集合中的元素。

可持久化(类似主席树)

它是最简单的$DFA$

可持久化板子

AC自动机

本质:接受且仅接受以指定的字符串集合中的某个元素为后缀的字符串,也就是 Trie + KMP。

可持久化

板子

SAM

本质:接受且仅接受指定字符串的后缀。

板子

广义SAM

本质:接受且仅接受指定的字符串集合中的某个元素的后缀,也就是 Trie + SAM。

板子