洛谷 4416 「COCI 2017.10」Plahte

发表于 | 分类于 | 16

这题也是找学长要的。

由于被单之间不相交但可能覆盖，并且小的一定在打的上面，我们可以把被单的覆盖关系看做一棵森林。
那么问题就等价于子树数颜色。

这个当然可以树上启发式合并，但是我写了启发式合并 set。

问题就在于转化的过程。
显然这种东西得上扫描线对吧。
我的思路独树一帜（

对于每个矩形的左边界，我们把线段树上对应的一段覆盖成这个矩形的编号。
但是在覆盖之前要看这个部分之前被哪个矩形覆盖了，这个前辈就是当前矩形在森林中的父亲。

对于每个矩形的右边界，我们不能简单地覆盖成全 −1。
可能在一个大矩形中存在多个矩形对齐，这时如果处理完其中第一个矩形再处理第二个矩形时找到的父亲就是 −1。
所以要在覆盖左边界时把对应的右边界即将覆盖的值改成覆盖前的值。

对于每个射击点，直接找它打在哪个矩形上（优先找上面的）。
然后在它对应的 set 上插入。

于是在森林上做 DFS，处理完一棵子树后就把其对应的 set 与其父亲启发式合并。

代码： 

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
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 8e4;
const int M = 8e4;
int n,m;
int fa[N + 5],to[N + 5],pre[N + 5],first[N + 5];
set<int> s[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v;
    pre[tot] = first[u];
    first[u] = tot;
}
double ind[(N << 1) + M + 5];
int len;
struct node
{
    int s;
} seg[((N << 1) + M << 2) + 10];
void build(int p,int tl,int tr)
{
    seg[p].s = -1;
    if(tl == tr)
        return ;
    int mid = tl + tr >> 1;
    build(ls,tl,mid),build(rs,mid + 1,tr);
}
inline void down(int p)
{
    if(~seg[p].s)
    {
        seg[ls].s = seg[rs].s = seg[p].s;
        seg[p].s = -1;
    }
}
void update(int l,int r,int k,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
    {
        seg[p].s = k;
        return ;
    }
    down(p);
    int mid = tl + tr >> 1;
    if(l <= mid)
        update(l,r,k,ls,tl,mid);
    if(r > mid)
        update(l,r,k,rs,mid + 1,tr);
}
int query(int x,int p,int tl,int tr)
{
    if(~seg[p].s || tl == tr)
        return seg[p].s;
    down(p);
    int mid = tl + tr >> 1;
    if(x <= mid)
        return query(x,ls,tl,mid);
    else
        return query(x,rs,mid + 1,tr);
}
struct edge
{
    int x,y1,y2,k,id;
    inline bool operator<(const edge &o) const
    {
        return x < o.x || (x == o.x && id < o.id);
    }
} e[(N << 1) + M + 5];
int tot;
struct rect
{
    int x1,y1,x2,y2;
} r[N + 5];
struct note
{
    int x,y,k;
} q[M + 5];
int ans[N + 5];
void dfs(int p)
{
    for(register int i = first[p];i;i = pre[i])
    {
        dfs(to[i]);
        if(s[to[i]].size() > s[p].size())
            swap(s[to[i]],s[p]);
        for(set<int>::iterator it = s[to[i]].begin();it != s[to[i]].end();++it)
            s[p].insert(*it);
        s[to[i]].clear();
    }
    ans[p] = s[p].size();
}
int rbound[N + 5];
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;++i)
        scanf("%d%d%d%d",&r[i].x1,&r[i].y1,&r[i].x2,&r[i].y2),ind[i * 2 - 1] = r[i].y1,ind[i * 2] = r[i].y2;
    for(register int i = 1;i <= m;++i)
        scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].k),ind[n * 2 + i] = q[i].y;
    sort(ind + 1,ind + n * 2 + m + 1);
    len = unique(ind + 1,ind + n * 2 + m + 1) - ind - 1;
    build(1,1,len);
    for(register int i = 1;i <= n;++i)
    {
        r[i].y1 = lower_bound(ind + 1,ind + len + 1,r[i].y1) - ind;
        r[i].y2 = lower_bound(ind + 1,ind + len + 1,r[i].y2) - ind;
        e[++tot] = (edge){r[i].x1,r[i].y1,r[i].y2,i,-1};
        e[++tot] = (edge){r[i].x2,r[i].y1,r[i].y2,-i,1};
    }
    for(register int i = 1;i <= m;++i)
    {
        q[i].y = lower_bound(ind + 1,ind + len + 1,q[i].y) - ind;
        e[++tot] = (edge){q[i].x,q[i].y,0,q[i].k,0};
    }
    sort(e + 1,e + tot + 1);
    for(register int i = 1;i <= tot;++i)
        if(e[i].k < 0)
            rbound[-e[i].k] = i;
    for(register int i = 1;i <= tot;++i)
    {
        if(e[i].y2)
        {
            if(e[i].k > 0)
            {
                int x = query(e[i].y1,1,1,len);
                if(~x)
                    add(x,e[i].k),fa[e[i].k] = x;
                e[rbound[e[i].k]].k = ~x ? -x - 1 : x;
            }
            update(e[i].y1,e[i].y2,e[i].k < 0 ? -e[i].k - 1 : e[i].k,1,1,len);
        }
        else
        {
            int x = query(e[i].y1,1,1,len);
            if(~x)
                s[x].insert(e[i].k);
        }
    }
    for(register int i = 1;i <= n;++i)
        if(!fa[i])
            dfs(i);
    for(register int i = 1;i <= n;++i)
        printf("%d\n",ans[i]);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment