P5494-【模板】线段树分裂

ybw051114

2020-09-30 约 1122 字预计阅读 3 分钟次阅读

P5494-【模板】线段树分裂

题目:

题目描述:

给出一个可重集 $a$（编号为 $1$），它支持以下操作：

0 p x y：将可重集 $p$ 中大于等于 $x$ 且小于等于 $y$ 的值放入一个新的可重集中（新可重集编号为从 $2$ 开始的正整数，是上一次产生的新可重集的编号+1）。

1 p t：将可重集 $t$ 中的数放入可重集 $p$，且清空可重集 $t$（数据保证在此后的操作中不会出现可重集 $t$）。

2 p x q：在 $p$ 这个可重集中加入 $x$ 个数字 $q$。

3 p x y：查询可重集 $p$ 中大于等于 $x$ 且小于等于 $y$ 的值的个数。

4 p k：查询在 $p$ 这个可重集中第 $k$ 小的数，不存在时输出 -1。

输入格式:

第一行两个整数 $n,m$，表示可重集中的数在 $1\sim n$ 的范围内，有 $m$ 个操作。

接下来一行 $n$ 个整数，表示 $1 \sim n$ 这些数在 $a$ 中出现的次数 $(a_{i} \leq m)$。

接下来的 $m$ 行每行若干个整数，第一个数为操作的编号 $opt$（$0 \leq opt \leq 4$），以题目描述为准。

输出格式:

依次输出每个查询操作的答案。

样例:

样例输入 1:

样例输出 1:

思路:

实现:

  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
#include "ybwhead/ios.h"
#define ll long long
const int MAXN = 200010;
int n, m, tot, cnt, seq = 1, op, x, y, z, bac[MAXN << 5], ch[MAXN << 5][2], rt[MAXN];
ll val[MAXN << 5];
int newnod() { return (cnt ? bac[cnt--] : ++tot); }
void del(int p)
{
    bac[++cnt] = p, ch[p][0] = ch[p][1] = val[p] = 0;
    return;
}
void modify(int &p, int l, int r, int pos, int v)
{
    if (!p)
    {
        p = newnod();
    }
    val[p] += v;
    if (l == r)
    {
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
    {
        modify(ch[p][0], l, mid, pos, v);
    }
    else
    {
        modify(ch[p][1], mid + 1, r, pos, v);
    }
    return;
}
ll query(int p, int l, int r, int xl, int xr)
{
    if (xr < l || r < xl)
    {
        return 0;
    }
    if (xl <= l && r <= xr)
    {
        return val[p];
    }
    int mid = (l + r) >> 1;
    return query(ch[p][0], l, mid, xl, xr) + query(ch[p][1], mid + 1, r, xl, xr);
}
int kth(int p, int l, int r, int k)
{
    if (l == r)
    {
        return l;
    }
    int mid = (l + r) >> 1;
    if (val[ch[p][0]] >= k)
    {
        return kth(ch[p][0], l, mid, k);
    }
    else
    {
        return kth(ch[p][1], mid + 1, r, k - val[ch[p][0]]);
    }
}
int merge(int x, int y)
{
    if (!x || !y)
    {
        return x + y;
    }
    val[x] += val[y];
    ch[x][0] = merge(ch[x][0], ch[y][0]);
    ch[x][1] = merge(ch[x][1], ch[y][1]);
    del(y);
    return x;
}
void split(int x, int &y, ll k)
{
    if (x == 0)
    {
        return;
    }
    y = newnod();
    ll v = val[ch[x][0]];
    if (k > v)
    {
        split(ch[x][1], ch[y][1], k - v);
    }
    else
    {
        swap(ch[x][1], ch[y][1]);
    }
    if (k < v)
    {
        split(ch[x][0], ch[y][0], k);
    }
    val[y] = val[x] - k;
    val[x] = k;
    return;
}
int main()
{
    yin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        yin >> x;
        modify(rt[1], 1, n, i, x);
    }
    for (int i = 1; i <= m; i++)
    {
        yin >> op;
        if (op == 0)
        {
            yin >> x >> y >> z;
            ll k1 = query(rt[x], 1, n, 1, z), k2 = query(rt[x], 1, n, y, z);
            int tmp = 0;
            split(rt[x], rt[++seq], k1 - k2);
            split(rt[seq], tmp, k2);
            rt[x] = merge(rt[x], tmp);
        }
        else if (op == 1)
        {
            yin >> x >> y;
            rt[x] = merge(rt[x], rt[y]);
        }
        else if (op == 2)
        {
            yin >> x >> y >> z;
            modify(rt[x], 1, n, z, y);
        }
        else if (op == 3)
        {
            yin >> x >> y >> z;
            yout << query(rt[x], 1, n, y, z) << endl;
        }
        else if (op == 4)
        {
            yin >> x >> y;
            if (val[rt[x]] < y)
            {
                printf("-1\n");
                continue;
            }
            yout << kth(rt[x], 1, n, y) << endl;
        }
    }
    return 0;
}

目录

P5494-【模板】线段树分裂

P5494-【模板】线段树分裂

题目:

题目描述:

输入格式:

输出格式:

样例:

样例输入 1:

样例输出 1:

思路:

实现: