知识点总结

这个专题好像没什么新算法，标题里的重量平衡树、仙人掌、划分树好像都没用到。。。 都是一些可持久化数据结构和Splay的题目 最多多了一个支配树，在专门那篇Blog里也有学习资料

Problems

Hdu2475 Box(Splay)

Hdu2475 Box(Splay)

Hdu5923 Prediction(并查集)

Hdu5923 Prediction(并查集)

Hdu2665 Kth number（主席树）

主席树模板，只是想吐槽一下题目里说好的求第k大，结果写成第k小才A 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 100000 + 100;

struct node
{
    int id, val;
}A[Maxn];

inline int cmp (node a, node b)
{
    return a.val < b.val;
}

int N, M;
int Cnt;

struct Tree
{
    int lson, rson, val;
}Tree[Maxn * 20];

int Root[Maxn], Rank[Maxn];

inline void build (int &root, int l, int r)
{
    root = ++ Cnt;
    Tree[root].val = 0;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    build(Tree[root].lson, l, mid);
    build(Tree[root].rson, mid + 1, r);
}

inline void Insert (int pre, int &now, int l, int r, int x)
{
    now = ++ Cnt;
    Tree[now].lson = Tree[pre].lson;
    Tree[now].rson = Tree[pre].rson;
    Tree[now].val = Tree[pre].val + 1;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (x <= mid) Insert(Tree[pre].lson, Tree[now].lson, l, mid, x);
    else Insert(Tree[pre].rson, Tree[now].rson, mid + 1, r, x);
}

inline int Query (int pre, int now, int l, int r, int x)
{
    if (l == r)
        return l;
    int mid = (l + r) >> 1;
    int left = Tree[Tree[now].lson].val - Tree[Tree[pre].lson].val;
    if (left >= x)
        return Query(Tree[pre].lson, Tree[now].lson, l, mid, x);
    else return Query(Tree[pre].rson, Tree[now].rson, mid + 1, r, x - left);
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    int t;
    scanf("%d", &t);
    while (t--)
    {
        Cnt = 0;
        memset(A, 0, sizeof A);
        memset(Root, 0, sizeof Root);
        memset(Tree, 0, sizeof Tree);
        memset(Rank, 0, sizeof Rank);
        scanf("%d%d", &N, &M);
        for (int i = 1; i <= N; ++i)
            scanf("%d", &A[i].val), A[i].id = i;
        sort(A + 1, A + N + 1, cmp);
        for (int i = 1; i <= N; ++i) Rank[A[i].id] = i;
        build(Root[0], 1, N);
        for (int i = 1; i <= N; ++i)
            Insert(Root[i - 1], Root[i], 1, N, Rank[i]);
        for (int i = 1; i <= M; ++i)
        {
            int x, y, k;
            scanf("%d%d%d", &x, &y, &k);
            printf("%d\n", A[Query(Root[x - 1], Root[y], 1, N, k)].val);
        }
    }
    return 0;
}

Hdu4757 Tree(可持久化01Trie)

Hdu4757 Tree(可持久化01Trie)

Hdu5324 Boring Class(树套树)

Hdu5324 Boring Class(树套树)

POJ3580 SuperMemo(Splay)

POJ3580 SuperMemo(Splay)

Hdu6041 I Curse Myself(tarjan)

Hdu6041 I Curse Myself(tarjan)

Hdu4694 Important Sisters(支配树)

Hdu4694 Important Sisters(支配树)

Hdu4417 Super Mario(主席树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#define lowbit(x) x & (-x)

using namespace std;

const int Maxn = 1e5 + 10;

int N, M;
int A[Maxn], B[Maxn];
int Root[Maxn];

struct tree
{
    int lson, rson, val;
};

namespace DS
{
    tree Tree[Maxn * 20];
    int cnt = 0;

    inline void insert (int &now, int pre, int l, int r, int z)
    {
        now = ++cnt;
        Tree[now].lson = Tree[pre].lson;
        Tree[now].rson = Tree[pre].rson;
        Tree[now].val = Tree[pre].val + 1;
        if (l == r)
            return ;
        int mid = (l + r) >> 1;
        if (z <= mid)
            insert (Tree[now].lson, Tree[pre].lson, l, mid, z);
        else insert (Tree[now].rson, Tree[pre].rson, mid + 1, r, z);
    }

    inline int query (int now, int pre, int l, int r, int x, int y)
    {
        if (x > r || y < l) return 0;
        if (x <= l && r <= y) return Tree[now].val - Tree[pre].val;
        int mid = (l + r) >> 1;
        int ans = 0;
        if (x <= mid) ans += query (Tree[now].lson, Tree[pre].lson, l, mid, x, y);
        if (y > mid) ans += query (Tree[now].rson, Tree[pre].rson, mid + 1, r, x, y);
        return ans;
    }
}

inline void Init()
{
    DS :: cnt = 0;
}

inline void Solve()
{
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i) scanf("%d", &B[i]), A[i] = B[i];
    sort(B + 1, B + N + 1);
    int len = unique(B + 1, B + N + 1) - B - 1;
    for (int i = 1; i <= N; ++i)
        A[i] = lower_bound(B + 1, B + len + 1, A[i]) - B;
    for (int i = 1; i <= N; ++i)
        DS :: insert(Root[i], Root[i - 1], 1, N, A[i]);

    while (M--)
    {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        x++, y++;
        z = upper_bound(B + 1, B + len + 1, z) - B - 1;
        printf("%d\n", DS :: query (Root[y], Root[x - 1], 1, N, 1, z));
    }
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    int T;
    scanf("%d", &T);
    for (int xz = 1; xz <= T; ++xz)
    {
        printf("Case %d:\n", xz);
        Init();
        Solve();
    }
    return 0;
}