模拟赛 - 省选预热二

2015.11.14 13:57 Sat| 7 visits oi_2016| 2016_竞赛日常| Text

数据结构专场。

BZOJ2959 长跑

考场上的确分析出了需要缩边连通分量,然后求路径上的点权和,用动态树维护。然而不幸的是,并不会用并查集缩点(access 的时候 now = (now->fa = tree[find(now->fa->pos)]);)。这大概也是很久以来没有做动态树的奇怪的题所导致的,以后大概会有进步。(知识点欠缺了,以后就会了。做题的思路没问题就好了w)

另外在 BZOJ 上,只有开两个并查集才能过……在清橙上 TLE 了四个点。

  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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include <bits/stdc++.h>
using namespace std;

#define N 150005

int n, m, a[N], fa[N], fa2[N];

int find(int x)
{
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

int find2(int x)
{
    if (x == fa2[x]) return x;
    return fa2[x] = find2(fa2[x]);
}

char getc()
{
    static const int LEN = 1<<15;
    static char buf[LEN],*S=buf,*T=buf;
    if(S == T)
    {
        T = (S=buf)+fread(buf,1,LEN,stdin);
        if(S == T)return EOF;
    }
    return *S++;
}

int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc()));
    for(D=ch-'0'; isdigit(ch=getc());)
        D=(D<<3)+(D<<1)+(ch-'0');
    return D;
}

struct link_cut_tree
{
    struct node
    {
        static node *nil;
        node *fa, *son[2];
        int pos, key, sum, rev;

        node() : pos(0), key(0), sum(0), rev(0) {}
        node(int _pos, int _key)
        : pos(_pos), key(_key), sum(_key), rev(0)
        { fa = son[0] = son[1] = nil; }
        bool root() { return fa->son[0] != this && fa->son[1] != this; }
        int check() { return fa->son[1] == this; }
        void combine(node *x, int d) { son[d] = x, x->fa = this; }
        void pushup() { sum = son[0]->sum + son[1]->sum + key; }
        void pushdown()
        {
            if (!root()) fa->pushdown();
            if (rev) reverse();
        }
        void reverse()
        {
            rev ^= 1;
            swap(son[0], son[1]);
            son[0]->rev ^= 1; son[1]->rev ^= 1;
        }
    };

    node *tree[N];

    link_cut_tree() { tree[0] = node::nil; }

    void rotate(node *x)
    {
        node *k = x->fa;
        int d = !x->check();
        k->combine(x->son[d], d ^ 1);
        if (!k->root())
            k->fa->son[k->check()] = x;
        x->fa = k->fa;
        x->combine(k, d);
        k->pushup(); x->pushup();
    }

    void splay(node *x)
    {
        x->pushdown();
        while (!x->root())
        {
            if (!x->fa->root())
                rotate(x->check() ^ x->fa->check() ? x : x->fa);
            rotate(x);
        }
    }

    void access(node *x)
    {
        node *now = x, *pre = node::nil;
        while (now != node::nil)
            splay(now), now->son[1] = pre, now->pushup(),
            pre = now, now = (now->fa = tree[find(now->fa->pos)]);
        splay(x);
    }

    void setroot(node *x)
    {
        access(x); x->rev ^= 1;
    }

    int getroot(int x)
    {
        node *t = tree[x];
        access(t);
        while (t->son[0] != node::nil) t = t->son[0];
        return t->pos;
    }

    void link(int x, int y)
    {
        setroot(tree[x]); tree[x]->fa = tree[y];
    }

    void cut(int x, int y)
    {
        setroot(tree[x]); access(tree[y]);
        tree[x]->fa = tree[y]->son[0] = node::nil;
        tree[y]->pushup();
    }

    void modify(int x, int y)
    {
        access(tree[x]);
        tree[x]->key += y; tree[x]->pushup();
    }

    int getsum(int x, int y)
    {
        setroot(tree[x]); access(tree[y]);
        return tree[y]->sum;
    }

    void merge(node *x, node *y)
    {
        if (x == node::nil) return;
        y->key += x->key;
        fa[x->pos] = y->pos;
        merge(x->son[0], y);
        merge(x->son[1], y);
        x->son[0] = x->son[1] = x->fa = node::nil;
    }

    void connect(int x, int y)
    {
        setroot(tree[x]); access(tree[y]);
        merge(tree[y]->son[0], tree[y]);
        tree[y]->son[0] = node::nil;
        tree[y]->pushup();
    }
};

link_cut_tree::node *link_cut_tree::node::nil = new link_cut_tree::node();
link_cut_tree lct;


int main()
{
    n = read(); m = read();
    for (int i = 1; i <= n; ++i)
        fa[i] = i, fa2[i] = i;
    for (int i = 1; i <= n; ++i)
        a[i] = read(), lct.tree[i] = new link_cut_tree::node(i, a[i]);
    for (int i = 1, p, x, y; i <= m; ++i)
    {
        p = read(); x = read(); y = read();
        if (p == 1)
        {
            int fx = find2(x), fy = find2(y);
            x = find(x); y = find(y);
            if (x == y) continue;
            if (fx != fy)
                fa2[fy] = fx, lct.link(x, y);
            else
                lct.connect(x, y);
        }
        if (p == 2)
        {
            lct.modify(find(x), y - a[x]); a[x] = y;
        }
        if (p == 3)
        {
            int fx = find2(x), fy = find2(y);
            x = find(x); y = find(y);
            if (fx != fy)
                puts("-1");
            else
                printf("%d\n", lct.getsum(x, y));
        }
    }
    return 0;
}

BZOJ3439 Kpm的MC密码

解法一:AC 自动机+平衡树启发式合并

我们先把所有的字符串读入之后建立 AC 自动机,然后对于每个结点,以该结点的 fail 指针为父亲指针重新建立一棵树(暂且称之为 fail 树),那么我们发现,fail 树中某个串的 KPM 串的结束结点都在该串结束结点的子树中,那么此题就成立求子树第 k 小值的经典问题,我们可以每个结点上标记在该结点结束的串的编号,每个结点上用一棵平衡树维护以该结点为根的 fail 子树里的所有编号,然后进行一次 DFS 遍历,每次遍历完一棵子树,就把它上的平衡树于其父亲结点的平衡树进行启发式合并(把小的树暴力合并到大的树里面),顺便在平衡树中求第 k 小值就可以了。

时间复杂度:O(n log^2 n) 期望得分:100 分

解法二:AC 自动机+DFS 序列+主席树

关于 AC 自动机的处理与解法一相同,建立 fail 树之后对树进行一次 DFS 遍历,处理出树的 DFS 序列(括号序列),然后将问题转化为静态区间第 k 最值查询,那么就主席树即可。(你要使用时代的眼泪划分树貌似也没什么问题就是了)这种方法相当好写,也是标程的写法。

时间复杂度:O(n log n) 期望得分:100 分

解法三:后缀数组+二分查找+RMQ+主席树

把所有的串串起来做后缀数组,那么某个串的 KPM 串的与该串相同的后缀就在sa数组的一个区间中(这个可以用 RMQ+二分查找确定),然后转化为区间 k 最值的问题,主席树即可。

时间复杂度:O(n log^2 n) 期望得分:100 分

解法四:我在考场上想到的解法

首先需要把串倒过来,建立一棵 trie 树。在 trie 树上进行 DFS,就得到了一棵树。

对于这一棵树上的结点,我们需要求出以它为根的子树中结点权值的第 k 大值。然后我们来二分答案。如果第 k 大值为 t,那么在编号为 1-t 的结点中,一定有 k 个出现在以它为根的子树里。于是我们就利用树链剖分套主席树,当插入编号为 i 的结点时,从它到根的路径上的点在线段树上的权值都要 +1。这里就用到了在主席树上的区间修改(还是多个区间同时修改,否则会很担心爆内存的说)。查询时对于某一个点,二分答案,在相应的主席树上查询这个点的权值。

另外还需要考虑如果多个结点的位置相同,需要用一个并查集来维护。这样,我们可以发现代码已经很长了,时间复杂度还比较高。然而,实际上并不难写。

时间复杂度:O(n log^2 n) 空间复杂度:O(n log^2 n) 期望得分: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
167
168
169
170
171
172
173
174
175
176
177
#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define S 20000000

int n, pos[N], len[N], head[N], fa[N], f[N];
int size[N], son[N], top[N], p_id[N];
char str[N * 4];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

struct trie
{
    struct node
    {
        node *son[26];
        int val;
        node() : val(0) { memset(son, 0, sizeof son); }
    };

    node *root;

    trie() { root = new node(); }

    void insert(int x, char str[])
    {
        node *p = root;
        while (*str)
        {
            if (p->son[*str - 'a'] == NULL)
                p->son[*str - 'a'] = new node();
            p = p->son[*str - 'a'];
            ++str;
        }
        if (p->val) fa[p->val] = x;
        p->val = x;
    }

    void dfs(int pre, node *p)
    {
        if (p->val)
            add(pre, p->val), f[p->val] = pre, pre = p->val;
        for (int i = 0; i < 26; ++i)
            if (p->son[i] != NULL)
                dfs(pre, p->son[i]);
    }
} tree;

int find(int x)
{
    if (x == fa[x]) return x;
    return x = find(fa[x]);
}

void dfs(int x)
{
    size[x] = 1;
    for (int i = head[x]; i; i = edge[i].next)
    {
        dfs(edge[i].to);
        if (son[x] == -1 || size[edge[i].to] > size[son[x]])
            son[x] = edge[i].to;
        size[x] += size[edge[i].to];
    }
}

void create(int x, int d)
{
    static int tot = 0;
    p_id[x] = ++tot;
    top[x] = d;
    if (son[x] != -1) create(son[x], d);
    for (int i = head[x]; i; i = edge[i].next)
        if (edge[i].to != son[x])
            create(edge[i].to, edge[i].to);
}

struct node
{
    node *son[2];
    int tag;
    void *operator new(size_t s);
} *root[N], newnode[S];

void *node::operator new(size_t s)
{
    static node *p = newnode;
    return p++;
}

void insert(node *pre, node *&pos, int l, int r, vector<pair<int, int> > v)
{
    pos = new node();
    *pos = *pre;
    vector<pair<int, int> > tl, tr;
    int mid = (l + r) >> 1;
    for (int i = 0; i < (int)v.size(); ++i)
    {
        if (v[i].first <= l && r <= v[i].second)
            { ++pos->tag; continue; }
        if (v[i].first <= mid) tl.push_back(v[i]);
        if (v[i].second > mid) tr.push_back(v[i]);
    }
    if (tl.size()) insert(pre->son[0], pos->son[0], l, mid, tl);
    if (tr.size()) insert(pre->son[1], pos->son[1], mid + 1, r, tr);
}

int query(node *pos, int l, int r, int x)
{
    if (l == r) return pos->tag;
    int mid = (l + r) >> 1;
    if (x <= mid) return pos->tag + query(pos->son[0], l, mid, x);
    else return pos->tag + query(pos->son[1], mid + 1, r, x);
}

void modify(int pos, int x)
{
    vector<pair<int, int> > v;
    int t = top[x];
    while (x)
    {
        v.push_back(make_pair(p_id[t], p_id[x]));
        x = f[t]; t = top[x];
    }
    insert(root[pos - 1], root[pos], 1, n + 1, v);
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%s", str + (pos[i] = pos[i - 1] + len[i - 1] + 1)),
        len[i] = strlen(str + pos[i]);
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < len[i] / 2; ++j)
            swap(str[pos[i] + j], str[pos[i] + len[i] - 1 - j]);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    for (int i = 1; i <= n; ++i)
        tree.insert(i, str + pos[i]);
    tree.dfs(0, tree.root);
    for (int i = n; i >= 1; --i)
        fa[i] = find(fa[i]);
    memset(son, -1, sizeof son);
    dfs(0); create(0, 0);
    root[0] = new node();
    root[0]->son[0] = root[0]->son[1] = root[0];
    for (int i = 1; i <= n; ++i)
        modify(i, fa[i]);
    for (int k, i = 1; i <= n; ++i)
    {
        scanf("%d", &k);
        int l = 1, r = n, ans = -1;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (query(root[mid], 1, n + 1, p_id[fa[i]]) >= k)
                ans = mid, r = mid - 1;
            else l = mid + 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}

BZOJ3878 [Ahoi2014]奇怪的计算器

有几种操作,显然都可以用线段树维护。而且可以发现,对于输入的数 x, y,若 x < y,则输出的数 ans(x) <= ans(y)。用线段树维护时,在某一个操作结束后,需要找到权值过小的数和权值过大的数,处理溢出操作。可以发现,溢出只会出现在线段树中靠左或靠右的连续一段区间内。于是我们需要支持查询这两段区间的端点位置,并在这两段区间上进行 *0 +l/r 的操作。在线段树上顺便维护区间最小值和最大值即可,需要注意细节。

  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
#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define Q 800005
#define lson (pos << 1)
#define rson (pos << 1 | 1)

int n, m;
long long llimit, rlimit, a[Q], b[Q], c[Q], ans[N], mint[Q], maxt[Q];
pair<long long, int> opt[N], num[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void modify1(int pos, long long x)
{
    a[pos] += x;
    mint[pos] += x; maxt[pos] += x;
}

inline void modify2(int pos, long long x)
{
    a[pos] *= x; b[pos] *= x; c[pos] *= x;
    mint[pos] *= x; maxt[pos] *= x;
}

inline void modify3(int pos, long long x, int l, int r)
{
    b[pos] += x;
    mint[pos] += num[l].first * x; maxt[pos] += num[r].first * x;
}

void pushdown(int pos, int l, int r)
{
    if (c[pos] != 1)
        modify2(lson, c[pos]), modify2(rson, c[pos]);
    if (a[pos])
        modify1(lson, a[pos]), modify1(rson, a[pos]);
    int mid = (l + r) >> 1;
    if (b[pos])
        modify3(lson, b[pos], l, mid), modify3(rson, b[pos], mid + 1, r);
    a[pos] = b[pos] = 0; c[pos] = 1;
}

void change(int pos, long long x)
{
    a[pos] = x; b[pos] = 0; c[pos] = 0;
    mint[pos] = maxt[pos] = x;
}

void abandonl(int pos, int l, int r)
{
    mint[pos] = max(llimit, mint[pos]);
    maxt[pos] = max(llimit, maxt[pos]);
    pushdown(pos, l, r);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (maxt[lson] < llimit)
        change(lson, llimit), abandonl(rson, mid + 1, r);
    else if (mint[lson] < llimit)
        abandonl(lson, l, mid);
    mint[pos] = max(mint[pos], llimit);
}

void abandonr(int pos, int l, int r)
{
    mint[pos] = min(rlimit, mint[pos]);
    maxt[pos] = min(rlimit, maxt[pos]);
    pushdown(pos, l, r);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (mint[rson] > rlimit)
        change(rson, rlimit), abandonr(lson, l, mid);
    else if (maxt[rson] > rlimit)
        abandonr(rson, mid + 1, r);
    maxt[pos] = min(maxt[pos], rlimit);
}

void build(int pos, int l, int r)
{
    mint[pos] = num[l].first; maxt[pos] = num[r].first;
    a[pos] = 0; b[pos] = 0; c[pos] = 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
}

void getans(int pos, int l, int r)
{
    pushdown(pos, l, r);
    if (l == r) { ans[num[l].second] = mint[pos]; return; }
    int mid = (l + r) >> 1;
    getans(lson, l, mid);
    getans(rson, mid + 1, r);
}

int main()
{
    cin >> n >> llimit >> rlimit;
    char str[3];
    for (int x, i = 1; i <= n; ++i)
    {
        scanf("%s", str); x = read();
        switch (str[0])
        {
        case '+' : opt[i] = make_pair(x , 1);   break;
        case '-' : opt[i] = make_pair(-x, 1);   break;
        case '*' : opt[i] = make_pair(x , 2);   break;
        case '@' : opt[i] = make_pair(x , 3);   break;
        }
    }
    cin >> m;
    for (int i = 1; i <= m; ++i)
        num[i] = make_pair(read(), i);
    sort(num + 1, num + m + 1);
    build(1, 1, m);
    for (int i = 1; i <= n; ++i)
    {
        switch (opt[i].second)
        {
        case 1: modify1(1, opt[i].first);   break;
        case 2: modify2(1, opt[i].first);   break;
        case 3: modify3(1, opt[i].first, 1, m); break;
        }
        abandonl(1, 1, m); abandonr(1, 1, m);
    }
    getans(1, 1, m);
    for (int i = 1; i <= m; ++i)
        printf("%lld\n", ans[i]);
    return 0;
}