首页 > 其他分享 >可持久化线段树

可持久化线段树

时间:2022-11-06 21:55:18浏览次数:44  
标签:ch 持久 lc int 线段 long maxn rc

数组一般开maxn<<5,但有的时候也会不够,不知道怎么判断得到的建议是“贴着内存开”。
最套路的应用就是各种形式的区间k小:

K小数

保存一下模板

code


#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e5 + 3;

int n, m, a[maxn], b[maxn], rt[maxn], cnt, ans;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct seg 
{
    struct node 
    {
        int sum;
    }t[maxn<<5];
    int lc[maxn<<5], rc[maxn<<5], tot;
    void build(int &x, int l, int r)
    {
        x = ++tot;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(lc[x], l, mid);
        build(rc[x], mid+1, r);
    }
    void update(int &x, int pre, int l, int r, int pos)
    {
        x = ++tot; lc[x] = lc[pre]; rc[x] = rc[pre];
        t[x].sum = t[pre].sum + 1;
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(pos <= mid) update(lc[x], lc[x], l, mid, pos);
        else update(rc[x], rc[x], mid+1, r, pos);
    }
    int query(int pre, int x, int l, int r, int k)
    {
        if(l == r) return l;
        int mid = (l + r) >> 1;
        int res = t[lc[x]].sum - t[lc[pre]].sum;
        if(res >= k) return query(lc[pre], lc[x], l, mid, k);
        else return query(rc[pre], rc[x], mid+1, r, k-res);
    }
}t;

int main()
{
    n = read(); m = read();
    for(int i=1; i<=n; i++)
    {
        a[i] = read(); b[i] = a[i];
    }
    sort(b+1, b+1+n);
    cnt = unique(b+1, b+1+n)-b-1;
    t.build(rt[0], 1, cnt);
    for(int i=1; i<=n; i++)
    {
        int x = lower_bound(b+1, b+1+cnt, a[i])-b;
        t.update(rt[i], rt[i-1], 1, cnt, x);
    }
    while(m--)
    {
        int l = read(), r = read(), k = read();
        ans = t.query(rt[l-1], rt[r], 1, cnt, k);
        printf("%d\n", b[ans]);
    }
    

    return 0;
}

花神的嘲讽计划

可以预处理特定长度的hash然后对存在性进行查找,直接定点前缀和相减、

code
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 3;

int n, m, k, cnt, rt[maxn];
ull p[maxn], h[maxn], a[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct seg 
{
    struct node 
    {
        int sum;
    }t[maxn<<5];
    int lc[maxn<<5], rc[maxn<<5], tot;
    void build(int &x, int l, int r)
    {
        x = ++tot;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(lc[x], l, mid);
        build(rc[x], mid+1, r);
    }
    void update(int &x, int pre, int l, int r, int pos)
    {
        x = ++tot; lc[x] = lc[pre], rc[x] = rc[pre];
        t[x].sum = t[pre].sum + 1;
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(pos <= mid) update(lc[x], lc[x], l, mid, pos);
        else update(rc[x], rc[x], mid+1, r, pos);
    }
    int query(int x, int pre, int l, int r, int pos)
    {
        if(l == r)
        {
            if(t[x].sum - t[pre].sum) return 1;
            else return 0;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) return query(lc[x], lc[pre], l, mid, pos);
        else return query(rc[x], rc[pre], mid+1, r, pos);
    }
}t;

int main()
{
    n = read(); m = read(); k = read();
    p[0] = 1; 
    for(int i=1; i<=k; i++) p[i] = p[i-1] * 131;
    for(int i=1; i<=n; i++)
    {
        a[i] = read();
        h[i] = h[i-1] * 131 + a[i];
        if(i >= k) a[i] = h[i] - h[i-k] * p[k];
        else a[i] = h[i];
    }
    for(int i=1; i<=n; i++) h[i] = a[i];
    sort(h+1, h+1+n);
    cnt = unique(h+1, h+1+n)-h-1;
    t.build(rt[0], 1, cnt);
    for(int i=1; i<=n; i++)
    {
        int x = lower_bound(h+1, h+1+cnt, a[i])-h;
        t.update(rt[i], rt[i-1], 1, cnt, x);
    }
    while(m--)
    {
        int l = read(), r = read();
        ull tmp = 0;
        for(int i=1; i<=k; i++)
        {
            int x = read();
            tmp = tmp * 131 + x;
        }
        int x = lower_bound(h+1, h+1+cnt, tmp)-h;
        if(h[x] == tmp && t.query(rt[l+k-2], rt[r], 1, cnt, x)) printf("No\n");
        else printf("Yes\n");
    }

    return 0;
}

森林

跟线段树分治和LCT什么的没有关系,那些动态图数据结构最主要的应用是删边。
如果把它放到了树上,发现它在数组上的时候前缀和相减是答案,在树上就可以使用树上差分的套路继续减法,可持久化树的每一个状态(时间)都是一些权值的累计,减掉需要减的东西就好,减谁都行。
路径不路径的,对建权值树没有影响,其它的,减法照常做就完了……
因为树链剖分涉及大小不方便修改,所以倍增求LCA,发现倍增LCA支持加边!!

code
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 8e4 + 1;

int dep[maxn], f[maxn][17], fa[maxn], son[maxn], cnt, root[maxn];
int T, n, m, q, a[maxn], ans, b[maxn];
bool vis[maxn];
char op[3];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct edge 
{
    int next, to;
}e[maxn<<2];
int head[maxn], len;

void add(int x, int y)
{
    e[++len].to = y; e[len].next = head[x];
    head[x] = len;
}

struct seg 
{
    struct node 
    {
        int sum;
    }t[maxn*600];
    int lc[maxn*600], rc[maxn*600], tot;
    void build(int &x, int l, int r)
    {
        x = ++tot;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(lc[x], l, mid);
        build(rc[x], mid+1, r);
    }
    void update(int &x, int pre, int l, int r, int pos)
    {
        x = ++tot; lc[x] = lc[pre]; rc[x] = rc[pre];
        t[x].sum = t[pre].sum + 1;
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(pos <= mid) update(lc[x], lc[x], l, mid, pos);
        else update(rc[x], rc[x], mid+1, r, pos);
    }
    //我又一次在query的时候忘了传入k-lsize,而是传了个k
    int query(int x, int y, int pre1, int pre2, int l, int r, int k)
    {
        if(l == r) return b[l];
        int lsize = t[lc[x]].sum + t[lc[y]].sum - t[lc[pre1]].sum - t[lc[pre2]].sum;
        int mid = (l + r) >> 1;
        if(lsize >= k) return query(lc[x], lc[y], lc[pre1], lc[pre2], l, mid, k);
        else return query(rc[x], rc[y], rc[pre1], rc[pre2], mid+1, r, k-lsize);
    }
}t;

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

void dfs(int x, int fat, int rt)
{
    f[x][0] = fat;
    for(int i=1; i<=16; i++)
    {
        f[x][i] = f[f[x][i-1]][i-1];
    }
    son[rt]++;
    dep[x] = dep[fat] + 1;
    fa[x] = fat;
    vis[x] = 1;
    int k = lower_bound(b+1, b+1+cnt, a[x])-b;
    t.update(root[x], root[fat], 1, cnt, k);
    for(int i=head[x]; i; i=e[i].next)
    {
        int u = e[i].to;
        if(u == fat) continue;
        dfs(u, x, rt);
    }
}

int LCA(int x, int y)
{
    if(x == y) return x;
    if(dep[x] > dep[y]) swap(x, y);
    for(int i=16; i>=0; i--)
    {
        if(dep[f[y][i]] >= dep[x])
        {
            y = f[y][i];
        }
    }
    if(x == y) return x;
    for(int i=16; i>=0; i--)
    {
        if(f[x][i] != f[y][i])
        {
            x = f[x][i]; y = f[y][i];
        }
    }
    return f[x][0];
}

int main()
{   
    read();
    n = read(); m = read(); q = read();
    for(int i=1; i<=n; i++)
    {
        a[i] = read(); b[i] = a[i]; fa[i] = i;
        //这里的并查集为什么不直接染成rt?
    }
    sort(b+1, b+1+n);
    cnt = unique(b+1, b+1+n)-b-1;
    for(int i=1; i<=m; i++)
    {
        int x = read(), y = read();
        add(x, y); add(y, x);
    }
    t.build(root[0], 1, cnt);
    for(int i=1; i<=n; i++)
    {
        if(!vis[i])
        {
            dfs(i, 0, i); fa[i] = i;
        }
    }
    while(q--)
    {
        scanf("%s", op);
        int x = read()^ans, y = read()^ans;
        if(op[0] == 'Q')
        {
            int k = read()^ans;
            int lca = LCA(x, y);
            ans = t.query(root[x], root[y], root[lca], root[f[lca][0]], 1, cnt, k);
            printf("%d\n", ans);
        }
        else 
        {
            add(x, y); add(y, x);
            int u = find(x), v = find(y);
            if(son[u] < son[v])
            {
                swap(u, v); swap(x, y);
            }
            dfs(y, x, u);
        }
    }

    return 0;
}

P2633 Count on a tree

是上一题没有加边操作的简化版。

code
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e5 + 3;

int n, m, a[maxn], b[maxn], ans, cnt, f[maxn][18], root[maxn], dep[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct edge 
{
    int next, to;
}e[maxn<<1];
int head[maxn], len;

void add(int x, int y)
{
    e[++len].to = y; e[len].next = head[x];
    head[x] = len;
}

struct seg 
{
    struct node 
    {
        int sum;
    }t[maxn<<8];
    int lc[maxn<<8], rc[maxn<<8], tot;
    void build(int &x, int l, int r)
    {
        x = ++tot;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(lc[x], l, mid);
        build(rc[x], mid+1, r);
    }
    void update(int &x, int pre, int l, int r, int pos)
    {
        x = ++tot; lc[x] = lc[pre]; rc[x] = rc[pre];
        t[x].sum = t[pre].sum + 1;
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(pos <= mid) update(lc[x], lc[x], l, mid, pos);
        else update(rc[x], rc[x], mid+1, r, pos);
    }
    int query(int x, int y, int pre1, int pre2, int l, int r, int k)
    {
        if(l == r) return b[l];
        int mid = (l + r) >> 1;
        int lsize = t[lc[x]].sum + t[lc[y]].sum - t[lc[pre1]].sum - t[lc[pre2]].sum;
        if(lsize >= k) return query(lc[x], lc[y], lc[pre1], lc[pre2], l, mid, k);
        else return query(rc[x], rc[y], rc[pre1], rc[pre2], mid+1, r, k-lsize);
    }
}t;

void dfs(int x, int fa)
{
    f[x][0] = fa;
    for(int i=1; i<=17; i++)
    {
        f[x][i] = f[f[x][i-1]][i-1];
    }
    dep[x] = dep[fa] + 1;
    int k = lower_bound(b+1, b+1+cnt, a[x])-b;
    t.update(root[x], root[fa], 1, cnt, k);
    for(int i=head[x]; i; i=e[i].next)
    {
        int u = e[i].to;
        if(u == fa) continue;
        dfs(u, x);
    }
}

int LCA(int x, int y)
{
    if(x == y) return x;
    if(dep[x] > dep[y]) swap(x, y);
    for(int i=17; i>=0; i--)
    {
        if(dep[f[y][i]] >= dep[x])//>=居然被我写成了<=
        {
            y = f[y][i];
        }
    }
    if(x == y) return x;
    for(int i=17; i>=0; i--)
    {
        if(f[x][i] != f[y][i])
        {
            x = f[x][i]; y = f[y][i];
        }
    }
    return f[x][0];
}

int main()
{
    n = read(); m = read();
    for(int i=1; i<=n; i++) 
    {
        a[i] = read(); b[i] = a[i];
    }
    sort(b+1, b+1+n);
    cnt = unique(b+1, b+1+n)-b-1;
    t.build(root[0], 1, cnt);
    for(int i=1; i<n; i++)
    {
        int x = read(), y = read();
        add(x, y); add(y, x);
    }
    dfs(1, 0);
    while(m--)
    {
        int u = read()^ans, v = read(), k = read();
        int lca = LCA(u, v);
        //经典树上差分
        ans = t.query(root[u], root[v], root[lca], root[f[lca][0]], 1, cnt, k);
        printf("%d\n", ans);
    }

    return 0;
}

疯狂的颜色序列

这种数颜色的好像也是常见的套路了,然而我老是忘……
记录每个位置的nxt,表示这个位置上的颜色下一次出现的位置,区间内出现的颜色种类就是nxt在右端点右边的颜色个数,这得到的是前缀和,还是以前缀和相减的形式。

code
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int maxn = 5e5 + 3;

int n, m, a[maxn], pos[maxn], nxt[maxn], ans, rt[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct seg 
{
    struct node 
    {
        int sum;
    }t[maxn<<5];
    int lc[maxn<<5], rc[maxn<<5], tot;
    void update(int &x, int pre, int l, int r, int pos)
    {
        x = ++tot; lc[x] = lc[pre], rc[x] = rc[pre];
        t[x].sum = t[pre].sum + 1;
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(pos <= mid) update(lc[x], lc[x], l, mid, pos);
        else update(rc[x], rc[x], mid+1, r, pos);
    }
    //查询的不是单点,而是以这个点为左端点的后缀和!
    int query(int pre, int x, int l, int r, int pos)
    {
        if(l == r)
        {
            return t[x].sum - t[pre].sum;
        }
        int mid = (l + r) >> 1;
        if(pos <= mid) return query(lc[pre], lc[x], l, mid, pos)+t[rc[x]].sum-t[rc[pre]].sum;
        else return query(rc[pre], rc[x], mid+1, r, pos);
    }
}t;

int main()
{
    n = read(); m = read();
    for(int i=1; i<=n; i++)
    {
        a[i] = read();
    }
    for(int i=1; i<=n; i++) pos[a[i]] = n + 1;
    for(int i=n; i>=1; i--)
    {
        nxt[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    for(int i=1; i<=n; i++) 
    {
        t.update(rt[i], rt[i-1], 1, n+1, nxt[i]);
    }
    while(m--)
    {
        int l = read(), r = read();
        l = (l + ans) % n + 1; r = (r + ans) % n + 1;
        if(l > r) swap(l, r);
        ans = t.query(rt[l-1], rt[r], 1, n+1, r+1);
        printf("%d\n", ans);
    }

    return 0;
}

影魔

转化成平面点对,感觉这个是主席树的另一个应用类型了,就是有两个限制条件都是区间的形式,想到了二维前缀和,主席树的优点应该是省空间?

code
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 2e5 + 7;

int n, st[maxn], top, p1, p2, a[maxn], L[maxn], R[maxn], m, root[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

struct node 
{
    int l, r, w;
};

struct edge 
{
    int next; node to;
}e[maxn<<2];
int head[maxn], len;

void add(int x, node y)
{
    e[++len].to = y; e[len].next = head[x];
    head[x] = len;
}

struct seg 
{
    struct tree 
    {
        ll sum, tag;
    }t[maxn<<5];
    int lc[maxn<<5], rc[maxn<<5], tot;
    void update(int &x, int l, int r, int L, int R, int w)
    {
        if(!x) x = ++tot;
        t[x].sum += 1ll * (min(R,r)-max(L,l)+1) * w;
        if(L <= l && r <= R)
        {
            t[x].tag += 1ll * w; return;
        }
        int mid = (l + r) >> 1;
        if(L <= mid) update(lc[x], l, mid, L, R, w);
        if(R > mid) update(rc[x], mid+1, r, L, R, w);
    }
    int merge(int x, int y)
    {
        if(!x || !y) return x+y;
        t[x].sum += t[y].sum; t[x].tag += t[y].tag;
        lc[x] = merge(lc[x], lc[y]);
        rc[x] = merge(rc[x], rc[y]);
        return x;
    }
    ll query(int x, int l, int r, int L, int R)
    {
        if(!x) return 0;
        if(L <= l && r <= R) return t[x].sum;
        int mid = (l + r) >> 1; ll res = 0;
        if(L <= mid) res += query(lc[x], l, mid, L, R);
        if(R > mid) res += query(rc[x], mid+1, r, L, R);
        return res + 1ll * (min(R,r)-max(L,l)+1) * t[x].tag;
    }
}t;

int main()
{
    n = read(); m = read(); p1 = read(); p2 = read();
    for(int i=1; i<=n; i++)
    {
        a[i] = read();
        while(top && a[st[top]] < a[i]) R[st[top--]] = i;
        L[i] = st[top];
        st[++top] = i;
    }
    while(top) R[st[top--]] = n + 1;
    for(int i=1; i<=n; i++)
    {
        if(i != n) add(i, (node){i+1, i+1, p1});
        if(L[i] && R[i] <= n) add(L[i], (node){R[i], R[i], p1});
        if(L[i] && i+1<=R[i]-1) add(L[i], (node){i+1, R[i]-1, p2});
        if(R[i]<=n && L[i]+1<=i-1) add(R[i], (node){L[i]+1, i-1, p2}); 
    }
    for(int i=1; i<=n; i++)
    {
        for(int j=head[i]; j; j=e[j].next)
        {
            node v = e[j].to;
            int l = v.l, r = v.r, w = v.w;
            t.update(root[i], 1, n, l, r, w);
        }
        root[i] = t.merge(root[i], root[i-1]);
    }
    for(int i=1; i<=m; i++)
    {
        int l = read(), r = read();
        printf("%lld\n", t.query(root[r], 1, n, l, r)-t.query(root[l-1], 1, n, l, r));
    }

    return 0;
}

标签:ch,持久,lc,int,线段,long,maxn,rc
From: https://www.cnblogs.com/Catherine2006/p/16864260.html

相关文章