魔法少女LJJ 题解

这题纯属就是迷惑题。。

为什么这么说？

注意数据范围：

对 100% 的数据 $0\leq m\leq400000$，$c\leq 7$。

$c\leq 7$！！

这意味着根本没有删除操作。就连样例也是错的。

Solution

这题的各种操作，用并查集 + 线段树合并完成。

如果你是被题目数据范围晃飞的，建议先去想想怎么做。

先介绍一下线段树的节点：

1
2
3
4
5
6


struct node
{
    int ls,rs; // 左右儿子
    int num; // 数量
    double val; // log 值，这里后面会讲
}tr[N*20];

接下来分析一下各种操作：

新建一棵权值线段树，$x$ 节点的 $num+1$。
并查集连接一下，合并这两个节点的线段树。
先查询得到 $a$ 连通块内有多少比 $x$ 小的点的数量 $S$；然后把这些小的区间清空；最后把 $x$ 所在的点的信息更改为 $S$。
类似操作 3。
基本操作了，二分查找树。
由 $\log(a\times b)=\log a+\log b$ 发现，直接比较 $\log$ 值即可。这就是为什么节点信息中要储存一个 $val$。
标准操作了，输出 $num$ 即可。

  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


#define int long long
#define db double
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
const int MAXN = 2e6 + 5;
int n, m, tmp, cnt, fa[MAXN], d[MAXN], rts[MAXN];
struct node
{
    int op, x, y;
} q[MAXN];
struct tree
{
    int ls, rs, num;
    bool tag;
    db val;
} tr[MAXN * 20];
int rk(int x)
{
    return lower_bound(d + 1, d + 1 + n, x) - d;
}
int find(int x)
{
    // 略
}
void pushup(int rt)
{
    tr[rt].num = tr[ls(rt)].num + tr[rs(rt)].num;
    tr[rt].val = tr[ls(rt)].val + tr[rs(rt)].val;
}
void pushdown(int rt)
{
    if (tr[rt].tag)
    {
        tr[rt].tag = 0;
        tr[ls(rt)].num = tr[ls(rt)].val = 0, tr[ls(rt)].tag = 1;
        tr[rs(rt)].num = tr[rs(rt)].val = 0, tr[rs(rt)].tag = 1;
    }
}
void update(int &rt, int l, int r, int k, int x, db y)
{
    // 略
}
void merge(int &rt1, int rt2, int l, int r)
{
    // 略
}
int query(int rt, int l, int r, int lf, int rg)
{
    // 略
}
void clean(int rt, int l, int r, int lf, int rg)
{
    if (!rt || rg < lf)
        return;
    if (lf <= l && rg >= r)
    {
        tr[rt].num = tr[rt].val = 0, tr[rt].tag = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if (lf <= mid)
        clean(ls(rt), l, mid, lf, rg);
    if (rg > mid)
        clean(rs(rt), mid + 1, r, lf, rg);
    pushup(rt);
    return;
}
int ask(int rt, int l, int r, int k)
{
    // 略
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        int op, x, y = 0;
        cin >> op >> x;
        if (op != 1 && op != 7)
            cin >> y;
        q[i] = (node){op, x, y};
        if (op == 3 || op == 4)
            d[++n] = y;
        if (op == 1)
            d[++n] = x;
    }
    sort(d + 1, d + 1 + n);
    n = unique(d + 1, d + 1 + n) - d - 1;
    for (int i = 1; i <= m; i++)
    {
        int op = q[i].op, x = q[i].x, y = q[i].y;
        if (op == 1)
            update(rts[++tmp], 1, n, rk(x), 1, (db)log(x)), fa[tmp] = tmp;
        if (op == 2)
        {
            int fx = find(x), fy = find(y);
            if (fx != fy)
            {
                fa[fy] = fx;
                merge(rts[fx], rts[fy], 1, n);
            }
        }
        if (op == 3)
        {
            int fx = find(x), k = rk(y);
            int sum = query(rts[fx], 1, n, 1, k - 1);
            clean(rts[fx], 1, n, 1, k - 1);
            update(rts[fx], 1, n, k, sum, sum * log(y));
        }
        if (op == 4)
        {
            int fx = find(x), k = rk(y);
            int sum = query(rts[fx], 1, n, k + 1, n);
            clean(rts[fx], 1, n, k + 1, n);
            update(rts[fx], 1, n, k, sum, sum * log(y));
        }
        if (op == 5)
            printf("%lld\n", ask(rts[find(x)], 1, n, y));
        if (op == 6)
            puts(tr[rts[find(x)]].val > tr[rts[find(y)]].val ? "1" : "0");
        if (op == 7)
            printf("%lld\n", tr[rts[find(x)]].num);
    }
    return 0;
}

结尾

这道题告诉我们，读题一定要认真****！！

本题考查并查集 + 线段树合并 + 读题仔细。