XJOI200728 题解

分块, 模拟赛, 线段树合并

两道数据结构题给我搞吐了。。。

A

原题是 CF418E

容易发现矩阵的奇数行（除了1）和偶数行是相同的. 感性理解就是把很多串 1，2，3 … 穿插在一起，每次转换一下。

分块做，f[i, j] 表示第一行前 i 块中数字 j 出现的次数，g[i, j] 表示第二行前 i 块中数字 j 出现的次数

维护的时候注意 f 和 g 的加减顺序！！！

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
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 2e5 + 10, M = 110;
int h, n, m, idx, unit = 1000, num;
int a[N], f[M][N], g[M][N], val[N];
map<int, int> mp;

int main() {
    cin >> h >> n >> m;
    num = n / unit + (n % unit > 0);
    rep(i, 1, n) {
        scanf("%d", &a[i]);
        if (!mp[a[i]]) {
            mp[a[i]] = ++idx;
            val[idx] = a[i];
        }
        a[i] = mp[a[i]];
    }
    rep(i, 1, num) {
        int l = (i - 1) * unit + 1, r = min(i * unit, n);
        rep(j, 1, n)  // 上界取 idx 是不行的！！！g数组最大值为 n！！！
            f[i][j] = f[i - 1][j], g[i][j] = g[i - 1][j];
        rep(j, l, r)
            f[i][a[j]]++, g[i][f[i][a[j]]]++;
    }
    while (m--) {
        int op, x, y; scanf("%d%d%d", &op, &x, &y);
        if (op == 1) {
            if (!mp[y]) {
                mp[y] = ++idx;
                val[idx] = y;
            }
            y = mp[y];
            rep(i, (x - 1) / unit + 1, num)
                g[i][f[i][a[x]]]--, f[i][a[x]]--;
            a[x] = y;
            rep(i, (x - 1) / unit + 1, num)
                f[i][a[x]]++, g[i][f[i][a[x]]]++;
        } else {
            if (x == 1) {
                printf("%d\n", val[a[y]]); continue;
            }
            rep(i, y / unit * unit + 1, y) {
                f[y / unit][a[i]]++, g[y / unit][f[y / unit][a[i]]]++;
            }
            printf("%d\n", x & 1 ? g[y / unit][f[y / unit][a[y]]] : f[y / unit][a[y]]);
            rep(i, y / unit * unit + 1, y) {
                g[y / unit][f[y / unit][a[i]]]--, f[y / unit][a[i]]--;
            }
        }
    }
    return 0;
}

B

结论题，就是删掉前 n 个

这种题应该要打表 + 找规律 + 特判啊，别愣在那里。。。

C

考虑没有操作 2，显然一遍 dfs 就能解决（考虑节点 x，它作为 lca 的贡献可以用 询问的a在子树中的个数 和 子树中黑色点的id和 来算）

考虑有操作 2，本质上多了时间这一维度（经典套路），用线段树合并（时间为下标）

点 x 作为 lca 的贡献就在合并的时候算。显然时间较小的id和对时间较大的询问有影响。因此要计算 左半边的id和 与 右半边的询问个数 之积（线段树上分治处理）

O(nlogn)

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
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 2e5 + 10;
typedef long long ll;
int n, m, idx;
int col[N], lst[N], rt[N];
ll val[N];
vector<int> nxt[N];
struct node { int cnt, ls, rs; ll sum; }tr[N * 60];

void upd(int x) {
    int ls = tr[x].ls, rs = tr[x].rs;
    tr[x].cnt = tr[ls].cnt + tr[rs].cnt;
    tr[x].sum = tr[ls].sum + tr[rs].sum;
}

void modify(int &x, int l, int r, int pos, int v1, int v2) {
    if (!x) x = ++idx;
    if (l == r) {
        tr[x].cnt += v1;
        tr[x].sum += v2;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid) modify(tr[x].ls, l, mid, pos, v1, v2);
    else modify(tr[x].rs, mid + 1, r, pos, v1, v2);
    upd(x);
}

void merge(int &x, int y, int l, int r, int id) {
    if (!x || !y) {
        x = (x | y); return;
    }
    if (l == r) {
        tr[x].cnt += tr[y].cnt, tr[x].sum += tr[y].sum; return;
    }
    val[id] += 1ll * tr[tr[x].rs].cnt * tr[tr[y].ls].sum;
    val[id] += 1ll * tr[tr[x].ls].sum * tr[tr[y].rs].cnt;
    int mid = (l + r) >> 1;
    merge(tr[x].ls, tr[y].ls, l, mid, id);
    merge(tr[x].rs, tr[y].rs, mid + 1, r, id);
    upd(x);
}

void dfs(int x, int fa) {
    for (int i = 0; i < nxt[x].size(); i++) {
        int y = nxt[x][i];
        if (y == fa) continue;
        dfs(y, x);
        merge(rt[x], rt[y], 0, m, x);
    }
}

int main() {
    cin >> n >> m;
    rep(i, 1, n) {
        scanf("%d", &col[i]);
        if (col[i]) modify(rt[i], 0, m, 0, 0, i);
    }
    rep(i, 1, n - 1) {
        int x, y; scanf("%d%d", &x, &y);
        nxt[x].push_back(y), nxt[y].push_back(x);
    }
    rep(i, 1, m) {
        int op, x; scanf("%d%d", &op, &x);
        if (op == 1) {
            modify(rt[x], 0, m, i, 1, 0);
            if (col[x]) val[x] += x;
        } else {
            col[x] ^= 1;
            if (col[x]) {
                modify(rt[x], 0, m, i, 0, x);
            } else {
                modify(rt[x], 0, m, i, 0, -x);
            }
        }
    }
    dfs(1, 0);
    rep(i, 1, n) printf("%lld\n", val[i]);
    return 0;
}