BZOJ 3439: Kpm的MC密码【论splay的正确姿势】

这题本身很简单
就是把串反过来做trie+区间k大即可
但是这题主席树做空间不够(应该是不够吧0.0)
于是就按拓扑序做启发式合并平衡树
刚好早上被黄神神d模板过长 于是orz了贵校的模板 学习了下
这是spaly的一些函数的科学写法

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
void rot(int now, int p)
{
    int fa = t[now].fa, q = t[t[fa].fa].c[1] == fa;
    t[now].fa = t[fa].fa;
    if (t[fa].fa) t[t[fa].fa].c[q] = now;
    t[fa].c[p] = t[now].c[!p];
    t[t[now].c[!p]].fa = fa;
    t[now].c[!p] = fa, t[fa].fa = now;
    up(fa), up(now);
}

int splay(int now)
{
    for (int fa, p, q; fa = t[now].fa;)
    {
        p = t[fa].c[1] == now, q = t[t[fa].fa].c[1] == fa;
        if (!t[fa].fa) rot(now, p);
        else rot(p == q ? fa : now, p), rot(now, q);
    }
    return now;
}

int ins(int now, int v)
{
    t[v].c[0] = t[v].c[1] = t[v].fa = 0, t[v].sum = 1;
    if (!now) return v;
    int fa, p;
    for (; now; fa = now, now = t[now].c[p = v > now])
        ++t[now].sum;
    t[v].fa = fa;
    t[fa].c[p] = v;
    return splay(v);
}

int query(int now, int k)
{
    for (int lsum; (lsum = t[t[now].c[0]].sum) != k - 1; )
        if (lsum >= k) now = t[now].c[0];
        else now = t[now].c[1], k -= lsum + 1;
    return splay(now);
}

然后这题的全题代码0 0
我只能说要是用我原来的模板得多100行=-=

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 1000005;

struct node
{
    int ch[26], sum, fa;
    vector<int> to;
}tr[maxn];

struct nodes
{
    int c[2], fa, sum;
}t[maxn];

int n, d[maxn], totr, root[maxn], ans[maxn], k[maxn];
string s;
queue<int> q;

void inss(int no)
{
    for (int i = s.length() - 1, now = 1; i >= 0; --i)
    {
        int to = tr[now].ch[s[i] - 'a'];
        ++tr[now].sum;
        if (!to)
        {
            to = tr[now].ch[s[i] - 'a'] = ++totr;
            tr[to].fa = now;
            ++d[now];
        }
        if (!i) tr[to].to.push_back(no), ++tr[to].sum;
        now = to;
    }
}

void up(int now)
{
    t[now].sum = t[t[now].c[0]].sum + t[t[now].c[1]].sum + 1;
}

void rot(int now, int p)
{
    int fa = t[now].fa, q = t[t[fa].fa].c[1] == fa;
    t[now].fa = t[fa].fa;
    if (t[fa].fa) t[t[fa].fa].c[q] = now;
    t[fa].c[p] = t[now].c[!p];
    t[t[now].c[!p]].fa = fa;
    t[now].c[!p] = fa, t[fa].fa = now;
    up(fa), up(now);
}

int splay(int now)
{
    for (int fa, p, q; fa = t[now].fa;)
    {
        p = t[fa].c[1] == now, q = t[t[fa].fa].c[1] == fa;
        if (!t[fa].fa) rot(now, p);
        else rot(p == q ? fa : now, p), rot(now, q);
    }
    return now;
}

int ins(int now, int v)
{
    t[v].c[0] = t[v].c[1] = t[v].fa = 0, t[v].sum = 1;
    if (!now) return v;
    int fa, p;
    for (; now; fa = now, now = t[now].c[p = v > now])
        ++t[now].sum;
    t[v].fa = fa;
    t[fa].c[p] = v;
    return splay(v);
}

int query(int now, int k)
{
    for (int lsum; (lsum = t[t[now].c[0]].sum) != k - 1; )
        if (lsum >= k) now = t[now].c[0];
        else now = t[now].c[1], k -= lsum + 1;
    return splay(now);
}

int dfs(int now, int root)
{
    if (!now) return root;
    root = dfs(t[now].c[0], root);
    root = dfs(t[now].c[1], root);
    root = ins(root, now);
    return root;
}

int merge(int u, int v)
{
    if (!u) return v;
    if (!v) return u;
    if (t[u].sum < t[v].sum) swap(u, v);
    return dfs(v, u);
}

int main()
{
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
    scanf("%d", &n);
    totr = 1;
    for (int i = 1; i <= n; ++i)
    {
        s = "";
        char c = getchar();
        while (!(c >= 'a' && c <= 'z')) c = getchar();
        while (c >= 'a' && c <= 'z')
        {
            s += c;
            c = getchar();
        }
        inss(i);
    }
    for (int i = 1; i <= n; ++i)
        scanf("%d", &k[i]);

    for (int i = 1; i <= totr; ++i)
        if (!d[i])
            q.push(i);
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        for (int i = 0; i < 26; ++i)
        {
            int to = tr[now].ch[i];
            if (!to) continue;
            root[now] = merge(root[now], root[to]);
        }
        for (int i = 0; i < tr[now].to.size(); ++i)
            root[now] = ins(root[now], tr[now].to[i]);
        for (int i = 0; i < tr[now].to.size(); ++i)
        {
            int to = tr[now].to[i];
            if (k[to] > tr[now].sum) ans[to] = -1;
            else root[now] = ans[to] = query(root[now], k[to]);
        }
        if (!--d[tr[now].fa]) q.push(tr[now].fa);
    }
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    fclose(stdin);fclose(stdout);
}

发表评论