主席树学习笔记
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对我主席树学习的帮助。
navigate_before
Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip
快速幂
navigate_next