生日

Posted on Edited on In

题目大意：今天是牛牛的生日，牛牛请了他的好朋友们一起过生日，生日必不可少的环节当然就是吃蛋糕啦。由于有n个人来参加牛牛的生日，牛牛需要给n个人分蛋糕，牛牛有2种操作C l r x 将[l,r]的人的蛋糕数改成x(1 <= x <= k)P l r 查询[l,r]中有多少种不同的蛋糕数牛牛总共执行了m次这样的操作，请输出所有的询问操作

线段树裸体

对每一个位置维护三十个颜色，重点在查询的时候，不要重复了

代码如下：

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

const int N = 1e5 + 66;

int n, m, k;
bool vis[33];

struct SEGMENTTREE
{
    int l, r, dat, tag; bool col[33];
//dat:有多少个不同的颜色
//tag:我这个区间应该是几
//col:我的区间内都有哪些颜色出现过
}tree[N << 2];

inline void up(int p)
{
    int l = p << 1, r = (p << 1) | 1, i, c(0);
    for (i = 0; i <= k; ++ i) tree[p].col[i] = (tree[l].col[i] || tree[r].col[i]) ? true : false;
    for (i = 0; i <= k; ++ i) c += tree[p].col[i] ? 1 : 0;
//cout << "c-->" << c << '\n';
    return (void)(tree[p].dat = c);
}

inline void down(int p)
{
    int l = p << 1, r = (p << 1) | 1, c = tree[p].tag, i;
    if (c == -1) return;
    for (i = 0; i <= k; ++ i) tree[l].col[i] = tree[r].col[i] = false;
    tree[l].col[c] = tree[r].col[c] = true;
    tree[l].tag = tree[r].tag = c;
    tree[l].dat = tree[r].dat = 1;
    return (void)(tree[p].tag = -1);
}

inline void build(int p, int l, int r)
{
    tree[p].l = r, tree[p].r = r, tree[p].tag = -1;
    if (l == r) return (void)(tree[p].dat = 1, tree[p].col[0] = true);
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build((p << 1) | 1, mid + 1, r);
    return (void)(up(p));
}

inline void updata(int p, int l, int r, int nl, int nr, int c)
{
    if (nl <= l && nr >= r)
    {
        tree[p].tag = c, tree[p].dat = 1;
        for (int i = 0; i <= 30; ++ i) tree[p].col[i] = false;
        return (void)(tree[p].col[c] = true);
    }
    down(p);
    int mid = (l + r) >> 1;
    if (nl <= mid) updata(p << 1, l, mid, nl, nr, c);
    if (nr > mid) updata((p << 1) | 1, mid + 1, r, nl, nr, c);
    return (void)(up(p));
}

inline int query(int p, int l, int r, int nl, int nr)
{
    if (nl <= l && nr >= r)
    {
        int c = 0;
        for (int i = 0; i <= k; ++ i) (! vis[i] && tree[p].col[i]) ? ++ c, vis[i] = true : c += 0;
        return c;
    }
    down(p);
    int mid = (l + r) >> 1, res = 0;
    if (nl <= mid) res = query(p << 1, l, mid, nl, nr);
    if (nr > mid) res += query((p << 1) | 1, mid + 1, r, nl, nr);
    return res;
}

signed main()
{
    int i, x, y, z; char opt;
    n = read(), m = read(), k = read();
    build(1, 1, n);

    for (i = 1; i <= m; ++ i)
    {
        cin >> opt;
        if (opt == 'C')
        {
            //cin >> x >> y >> z;
            x = read(), y = read(), z = read();
            if (x > y) swap(x, y);
            updata(1, 1, n, x, y, z);
        }
        else
        {
            //cin >> x >> y;
            x = read(), y = read();
            if (x > y) swap(x, y);
            memset(vis, 0, sizeof vis);
            put(query(1, 1, n, x, y));
        }
    }
    return 0;
}