COGS 930 [河南省队2012] 找第k小的数

简单题面#

求区间第k小

COGS 1534 == 930 找第k小的数本来是主席树或树套树的题然而可持久化Trie树可以过

查了查好像用可持久化Trie做区间k小的人很少啊（我好像是没有查到）事实上可持久化Trie树比较好打，代码很短。本来想用可持久化Treap 做区间k小的结果和 zzh 又调又改弄了一个晚上结果发现是真的不能做啊，Treap 区间不可减他会变化然后想到了可持久化Trie 发现好像可行啊，然后就出来了。跑的好像也很快比树套树和不离散的主席树快。

1
#include <cstdio>
2
#include <cstring>
3
using namespace std;
4
const int full = 21, fix = 1000001;
5
struct Trie
6
{
7
    struct Trie_Node
8
    {
9
        Trie_Node *ch[2];
10
        int s;
11
        Trie_Node()
12
        {
13
            ch[0] = ch[1] = NULL;
14
            s = 0;
15
        }
16
    } * root[100005],*null;
17
    Trie()
18
    {
19
        null = new Trie_Node();
20
        null->ch[0] = null->ch[1] = null;
21
        root[0] = new Trie_Node();
22
        root[0]->ch[1] = root[0]->ch[0] = null;
23
    }
24
    Trie_Node *NewNode()
25
    {
26
        Trie_Node *rt = new Trie_Node();
27
        rt->ch[0] = rt->ch[1] = null;
28
        return rt;
29
    }
30
    void copy(Trie_Node *&a, Trie_Node *b)
31
    {
32
        if (b == null)
33
            a = null;
34
        else
35
            a = NewNode(), *a = *b;
36
    }
37
    void Insert(int x, int cnt)
38
    {
39
        x += fix;
40
        copy(root[cnt], root[cnt - 1]);
41
        Trie_Node *rt1 = root[cnt], *rt2 = root[cnt - 1];
42
        for (int i = full; i >= 0; i--)
43
        {
44
            int k = (x >> i) & 1;
45
            copy(rt1->ch[k], rt2->ch[k]);
46
            if (rt1->ch[k] == null)
47
                rt1->ch[k] = NewNode();
48
            rt1 = rt1->ch[k], rt2 = rt2->ch[k];
49
            rt1->s++;
50
        }
51
    }
52
    int kth(int k, int l, int r)
53
    {
54
        int res = 0;
55
        Trie_Node *rt1 = root[r], *rt2 = root[l - 1];
56
        for (int i = full; i >= 0; i--)
57
        {
58
            if (k > rt1->ch[0]->s - rt2->ch[0]->s)
59
            {
60
                k -= (rt1->ch[0]->s - rt2->ch[0]->s);
61
                res |= (1 << i);
62
                rt1 = rt1->ch[1], rt2 = rt2->ch[1];
63
            }
64
            else
65
            {
66
                rt1 = rt1->ch[0], rt2 = rt2->ch[0];
67
            }
68
        }
69
        return res - fix;
70
    }
71
} root;
72
int main()
73
{
74
    freopen("kth.in","r",stdin);
75
    freopen("kth.out","w",stdout);
76
    int n, m, a;
77
    scanf("%d%d", &n, &m);
78
    for (int i = 1; i <= n; i++)
79
    {
80
        scanf("%d", &a);
81
        root.Insert(a, i);
82
    }
83
    int b, k;
84
    while (m--)
85
    {
86
        scanf("%d%d%d", &a, &b, &k);
87
        printf("%d\n", root.kth(k, a, b));
88
    }
89
}