book
归档: OI 
flag

什么是主席树

主席树:可持久化线段树,特点是每次修改都新建一颗新树,由于单点修改最多影响$\log n$个节点,因此只需要新建一条链,挂在原树上

问题:[COGS 2554][福利]可持久化线段树 RMQ问题的可持久化版本

这是一道板子题,但是此题没有体现主席树的经典应用,代码如下:

#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 10005;
const int INF = 1 << 29;
struct node
{
    node *lc, *rc;
    int maxv;
#define MAXV(x) ((x) ? (x)->maxv : -INF)
    inline void mt()
    {
        if (lc != 0 && rc != 0)
            maxv = max(MAXV(lc), MAXV(rc));
    }
    node()
    {
        maxv = -INF;
        lc = rc = 0;
    }
};
node *modify(node *o, int l, int r, int p, int v)
{
    if (!o)
        return 0;
    node *d = new node();
    *d = *o;
    if (l == r)
        d->maxv = v;
    else
    {
        int m = (l + r) >> 1;
        if (p <= m)
            d->lc = modify(o->lc, l, m, p, v);
        else
            d->rc = modify(o->rc, m + 1, r, p, v);
        d->mt();
    }
    return d;
}
int query(node *o, int l, int r, int ql, int qr)
{
    if (o == 0)
        return -INF;
    if (ql <= l && r <= qr)
        return o->maxv;
    int m = (l + r) >> 1, ans = -INF;
    if (ql <= m)
        ans = max(ans, query(o->lc, l, m, ql, qr));
    if (m < qr)
        ans = max(ans, query(o->rc, m + 1, r, ql, qr));
    return ans;
}
int data[maxn];
node *roots[100001];
node *build(int l, int r)
{
    node *d = new node();
    if (l == r)
        d->maxv = data[l];
    else
    {
        int m = (l + r) >> 1;
        d->lc = build(l, m);
        d->rc = build(m + 1, r);
        d->mt();
    }
    return d;
}
int n, q;
int main()
{
    freopen("longterm_segtree.in", "r", stdin);
    freopen("longterm_segtree.out", "w", stdout);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> data[i];
    roots[1] = build(1, n);
    int cver = 1;
    for (int i = 1; i <= q; ++i)
    {
        int op, k;
        cin >> op >> k;
        if (op & 1)
        { //==1
            int p, v;
            cin >> p >> v;
            roots[++cver] = modify(roots[k], 1, n, p, v);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            cout << query(roots[k], 1, n, l, r) << endl;
        }
    }
    return 0;
}

应用

区间出现次数

问题:[COGS 2569][東方] 博丽灵梦 梦想妙珠 给定一个序列,查询在$[l,r]$区间内,v出现了多少次

解决方案

先考虑一个弱化版的题目:给定一个序列,查询v在整个序列里出现了多少次。

对于这个问题,我们可以将每个数的值作为下标,值为1,插入到一颗线段树里,维护区间和,由于这颗线段树的下标是值,我们称之为权值线段树。如果要查询v在整个序列出现了多少次,我们可以查询位置v所维护的值是多少。

那么原问题呢?

注意到v在区间$[l,r]$内出现的次数$=$v在$[1,r]$内出现次数$-$v在$[1,l-1]$内出现次数,如果我们对于这个序列的每一个前缀都建一颗线段树,就可以把这个问题转化为弱化版的问题了。建树代码如下:

node* insert(node* pre,int l,int r,int p)
{
    node* x=new node();
  	*x = *pre
    int m=(l+r)>>1;
    if(l==r)
    {
        x->sum++;return x;
    }
    else
        if(p<=m)
            x->lc=insert(pre->lc,l,m,p),
        else
            x->rc=insert(pre->rc,m+1,r,p),
    return x;
}
int main()
{
  	for(int i=1;i<=n;++i)
        scanf("%d",&a[i]),maxnum=max(maxnum,a[i]);
    root[0]=build(1,maxnum);
    for(int i=1;i<=n;++i)
        root[i]=insert(root[i-1],1,maxnum,a[i]);
}

如果你非要二分查找水过我也没办法233

区间k小/大

问题:[COGS 1534][NEERC 2004]K小数 给定一个序列,查询区间$[l,r]$内第k小的数是多少

解决方案

思路与上面的类似,先对于每个前缀建树,然后再统计在$[l,r]$内比k小的数有多少,根据情况判断应该向左查还是向右查。

int query(node *l, int ll, int lr, node *r, int k)
{
    int lm = (ll + lr) >> 1;
    int cnt = r->lsum() - l->lsum();
    if (ll == lr)
        return ll;
    return k <= cnt ? query(l->lc, ll, lm, r->lc, k)
                    : query(l->rc, lm + 1, lr, r->rc, k - cnt);
}

调试技巧

输出线段树:

void printsegt(node *root, int k)
{
#define SPACE "        "
    for (int i = 0; i < k; ++i)
        cout << SPACE;
    cout << root << " 's SUM:" << root->sum << endl;
    if (root->lc != 0)
    {
        for (int i = 0; i < k; ++i)
            cout << SPACE;
        cout << root << " 's LC:" << endl,
            printsegt(root->lc, k + 1);
    }
    if (root->rc != 0)
    {
        for (int i = 0; i < k; ++i)
            cout << SPACE;
        cout << root << " 's RC :" << endl,
            printsegt(root->rc, k + 1);
    }
#undef SPACE
}

主席树套DP

问题:[COGS 2692] 天才魔法少女琪露诺爱计数 题意见原题

解决方案

首先搞出来DP方程,令$dp(i)$表示跳到第$i$个高台的方案数,则有
$$
\begin{cases}

dp\left(1\right)=1 \\

dp\left(i\right)=\sum_{j\in\left[max(i-r,1),i-l\right]&h(j)\in\left[h(i)-t,h(i)+t\right]}dp(j)

\end{cases}
$$
我们把高度作为下标,维护方案数的区间和,对高台的所有前缀建线段树,代码如下

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const int maxh = 1e4 + 10;
const long long mod = 998244353;
long long h[maxn], f[maxn];
long long mh;
struct node
{
    node *lc, *rc;
    long long sum;
    node()
    {
        sum = 0;
        lc = rc = 0;
    }
};
int n, l, r, t;
node *root[maxn];
node *build(int l, int r)
{
    int m = (l + r) >> 1;
    node *x = new node();
    if (l == r)
        return x;
    x->lc = build(l, m);
    x->rc = build(m + 1, r);
    return x;
}
node *insert(node *pre, int l, int r, int v)
{
    node *x = new node();
    *x = *pre;
    int m = (l + r) >> 1;
    if (l == r)
    {
        x->sum = ((x->sum + f[v]) % mod + mod) % mod;
        return x;
    }
    if (h[v] <= m)
        x->lc = insert(pre->lc, l, m, v);
    else
        x->rc = insert(pre->rc, m + 1, r, v);
    x->sum = ((x->lc->sum % mod + x->rc->sum % mod) + mod) % mod;
    return x;
}
int query(node *l, node *r, int ll, int rr, int ql, int qr)
{
    if (ql <= ll && rr <= qr)
        return ((r->sum % mod - l->sum % mod) + mod) % mod;
    if (ll == ql && rr == qr)
        return 0;
    int m = (ll + rr) >> 1;
    long long ans = 0;
    if (ql <= m)
        ans = (ans + query(l->lc, r->lc, ll, m, ql, qr)) % mod;
    if (qr > m)
        ans = (ans + query(l->rc, r->rc, m + 1, rr, ql, qr)) % mod;
    return (ans % mod + mod) % mod;
}
void init()
{
    freopen("cirnoisclever.in", "r", stdin);
    freopen("cirnoisclever.out", "w", stdout);
    scanf("%d%d%d%d", &n, &l, &r, &t);
    for (int i = 1; i <= n; ++i)
        cin >> h[i], mh = max(mh, h[i]);
}
int main()
{
    init();
    f[1] = 1;
    root[0] = build(1, mh);
    //root[0] = insert(root[0], 1, mh, 1);
    for (int i = 1; i <= n; ++i)
        root[i] = insert(root[i - 1], 1, mh, i);
    for (long long i = l + 1; i <= n; ++i)
    {
        long long ll = max(i - r, (long long)1),
                  lr = i - l;
        long long hl = max(h[i] - t, (long long)1),
                  hr = min(h[i] + t, mh);
        f[i] = query(root[ll - 1], root[lr], 1, mh, hl, hr);
        root[i] = insert(root[i - 1], 1, mh, i);
    }
    cout << (f[n] % mod + mod) % mod << endl;
}

解决方案2

可以将此题理解为维护一个矩形内的权值和,由于矩形宽度固定,可以用BIT维护,矩形每移动一次,将右端点逐出矩形,将左端点加入矩形,代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const int maxh = 1e4 + 10;
const ll mod = 998244353;
ll n, l, r, t;
ll h[maxn], c[maxn], f[maxn];
ll mx;
ll lowbit(ll x) { return x & -x; }
inline ll mmod(ll x)
{
    while (x < 0)
        x += mod;
    x %= mod;
    return x;
}
void update(ll pos, ll v)
{
    for (ll i = pos; i <= maxn; i += lowbit(i))
        c[i] = mmod(c[i] + v);
}
ll sum(ll e)
{
    ll ans = 0;
    for (int i = e; i > 0; i -= lowbit(i))
        ans = mmod(ans + c[i]);
    return mmod(ans);
}
ll sum(int l, int r) { return mmod(sum(r) - sum(l - 1)); }
void init()
{
    freopen("cirnoisclever.in", "r", stdin);
    freopen("cirnoisclever.out", "w", stdout);
    cin >> n >> l >> r >> t;
    for (int i = 1; i <= n; ++i)
        cin >> h[i], mx = max(h[i], mx);
    f[1] = 1;
    update(h[1], f[1]);
}
int main()
{
    init();
    for (int i = l + 1; i <= n; ++i)
    {
        ll hl = max(1ll, h[i] - t), hr = min(h[i] + t, mx);
        f[i] = sum(hl, hr);
        update(h[i - l + 1], f[i - l + 1]); //加入矩形右端点
        if (i > r)
            update(h[i - r], -f[i - r]); //逐出矩形左端点
    }
    cout << f[n] % mod << endl;
}

总结

主席树的思想是对序列的所有前缀建树,将值插入其中。

最后感谢mk,zf,sxysxy和kZime对我主席树学习的帮助。