主席树&莫队

数据结构与算法
字数统计: 1.4k字   |   阅读时长≈ 7分钟

主席树&莫队的总结

题目传送门：SPOJ-DQUERY D-query（主席树 | 莫队 && 区间内不同数个数）

题目大意：

求区间内不同数的个数。

解题思路：

主席树做法：

倒序（从右向左）建立主席树，如果一个值还没出现过，则直接插入，否则删除后再重新插入（相当于保留这个数最左出现的位置）。之后要查询 [l, r] 时，选用 l 位置的主席树，这时树中的数据是 [l, n] 范围内的，因此查询时需要传入 r 作为挡板，仅统计小于等于 r 的个数，这样就可以实现 [l, r] 区间不同数的查询。

莫队做法：

莫队模板题

AC代码：

主席树：

1
#include <cstring>
2
#include <cstdio>
3
#include <algorithm>
4
using namespace std;
5
const int MAXN = 100001;
6
struct node
7
{
8
    int sum, l, r;
9
} hjt[MAXN * 40];
10
int a[MAXN], sorted[MAXN], num;
11
int root[MAXN], cnt;
12
int GetIdx(int v)
13
{
14
    return lower_bound(sorted + 1, sorted + 1 + num, v) - sorted;
15
}
16
void init()
17
{
18
    cnt = 0;
19
}
20
int CreateNode(int sum, int l, int r)
21
{
22
    int idx = ++cnt;
23
    hjt[idx].sum = sum;
24
    hjt[idx].l = l;
25
    hjt[idx].r = r;
26
    return idx;
27
}
28
void Insert(int &root, int pre_rt, int pos, int l, int r)
29
{
30
    root = CreateNode(hjt[pre_rt].sum + 1, hjt[pre_rt].l, hjt[pre_rt].r);
31
    if(l == r)return ;
32
    int m = (l + r) >> 1;
33
    if(pos <= m)Insert(hjt[root].l, hjt[pre_rt].l, pos, l, m);
34
    else Insert(hjt[root].r, hjt[pre_rt].r, pos, m + 1, r);
35
}
36
int Query(int s, int e, int k, int l, int r)
37
{
38
    if(l == r)return l;
39
    int m = (l + r) >> 1;
40
    int sum = hjt[hjt[e].l].sum - hjt[hjt[s].l].sum;
41
    if(k <= sum)return Query(hjt[s].l, hjt[e].l, k, l, m);
42
    else Query(hjt[s].r, hjt[e].r, k - sum, m + 1, r);
43
}
44
int main()
45
{
46
    int n, m, i, j, k, l, r;
47
    while(scanf("%d %d", &n, &m) != EOF){
48
        init();
49
        for(i = 1; i <= n; i++)
50
        {
51
            scanf("%d", &a[i]);
52
            sorted[i] = a[i];
53
        }
54
        sort(sorted + 1, sorted + 1 + n);
55
        num = unique(sorted + 1, sorted + 1 + n) - (sorted + 1);
56
        for(int i = 1; i <= n; i++)
57
        {
58
            Insert(root[i], root[i - 1], GetIdx(a[i]), 1, num);
59
        }
60
        while(m--)
61
        {
62
            scanf("%d %d %d", &l, &r, &k);
63
            printf("%d\n", sorted[Query(root[l - 1], root[r], k, 1, num)]);
64
        }
65
    }
66
    return 0;
67
}

莫队：

1
#include <iostream>
2
#include <bits/stdc++.h>
3
using namespace std;
4
int num[1000010],vis[1000010],s[1000010];
5
int m,block,ans;
6
struct node
7
{
8
    int l,r,id;
9
    bool operator < (const node &c)const{
10
        if(l/block==c.l/block)
11
            return r<c.r;
12
        return l/block < c.l/block;
13
    }
14
}q[1000010];
15
16
17
18
void add(int x)
19
{
20
    vis[s[x]]++;
21
    if(vis[s[x]]==1)ans++;
22
}
23
24
void del(int x)
25
{
26
    vis[s[x]]--;
27
    if(vis[s[x]]==0)ans--;
28
}
29
30
int main()
31
{
32
    int n;
33
    scanf("%d",&n);
34
    block=sqrt(n);
35
    for(int i=1;i<=n;i++)
36
    {
37
        scanf("%d",&s[i]);
38
    }
39
    scanf("%d",&m);
40
    for(int i=1;i<=m;i++)
41
    {
42
        scanf("%d%d",&q[i].l,&q[i].r);
43
        q[i].id=i;
44
    }
45
    sort(q+1,q+1+m);
46
    int l=1,r=0;
47
    for(int i=1;i<=m;i++)
48
    {
49
        while(l<q[i].l)del(l),l++;
50
        while(l>q[i].l)l--,add(l);
51
        while(r<q[i].r)r++,add(r);
52
        while(r>q[i].r)del(r),r--;
53
        num[q[i].id]=ans;
54
    }
55
    for(int i=1;i<=m;i++)
56
    {
57
        printf("%d\n",num[i]);
58
    }
59
    return 0;
60
}

题目传送门：POJ-2104 K-th Number（主席树 && 区间第 k 大）

题目大意：

求区间第 k 小的数。

解题思路：

主席树模板题

AC代码：

1
#include <cstring>
2
#include <cstdio>
3
#include <algorithm>
4
using namespace std;
5
const int MAXN = 100001;
6
struct node
7
{
8
    int sum, l, r;
9
} hjt[MAXN * 40];
10
int a[MAXN], sorted[MAXN], num;
11
int root[MAXN], cnt;
12
int GetIdx(int v)
13
{
14
    return lower_bound(sorted + 1, sorted + 1 + num, v) - sorted;
15
}
16
void init()
17
{
18
    cnt = 0;
19
}
20
int CreateNode(int sum, int l, int r)
21
{
22
    int idx = ++cnt;
23
    hjt[idx].sum = sum;
24
    hjt[idx].l = l;
25
    hjt[idx].r = r;
26
    return idx;
27
}
28
void Insert(int &root, int pre_rt, int pos, int l, int r)
29
{
30
    root = CreateNode(hjt[pre_rt].sum + 1, hjt[pre_rt].l, hjt[pre_rt].r);
31
    if(l == r)return ;
32
    int m = (l + r) >> 1;
33
    if(pos <= m)Insert(hjt[root].l, hjt[pre_rt].l, pos, l, m);
34
    else Insert(hjt[root].r, hjt[pre_rt].r, pos, m + 1, r);
35
}
36
int Query(int s, int e, int k, int l, int r)
37
{
38
    if(l == r)return l;
39
    int m = (l + r) >> 1;
40
    int sum = hjt[hjt[e].l].sum - hjt[hjt[s].l].sum;
41
    if(k <= sum)return Query(hjt[s].l, hjt[e].l, k, l, m);
42
    else Query(hjt[s].r, hjt[e].r, k - sum, m + 1, r);
43
}
44
int main()
45
{
46
    int n, m, i, j, k, l, r;
47
    while(scanf("%d %d", &n, &m) != EOF){
48
        init();
49
        for(i = 1; i <= n; i++)
50
        {
51
            scanf("%d", &a[i]);
52
            sorted[i] = a[i];
53
        }
54
        sort(sorted + 1, sorted + 1 + n);
55
        num = unique(sorted + 1, sorted + 1 + n) - (sorted + 1);
56
        for(int i = 1; i <= n; i++)
57
        {
58
            Insert(root[i], root[i - 1], GetIdx(a[i]), 1, num);
59
        }
60
        while(m--)
61
        {
62
            scanf("%d %d %d", &l, &r, &k);
63
            printf("%d\n", sorted[Query(root[l - 1], root[r], k, 1, num)]);
64
        }
65
    }
66
    return 0;
67
}
  • © 2020 QSH
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信