set​瞎搞

预处理

我们考虑一下,一只青蛙能够影响的区间是什么

我们发现,如果将每只青蛙能够吃到的文字区间$[l, r]$按照左端点$l$排序,然后把后面的区间和前面的区间的重复部分去掉,那么就可以得到一个青蛙真正可以吃到的蚊子的范围区间

我觉得下面这张图讲的很清楚w

好,那么我们的预处理就这么完了。

加入蚊子

我们采用$set​$维护所有青蛙能够真正吃到的蚊子的范围区间,那么在加入一只蚊子的时候,可以lower_bound快速求出这只蚊子会不会被吃掉,如果它被吃掉了,是被哪只青蛙吃掉了。

显然,如果一只蚊子被吃掉了,那么吃掉它的哪只青蛙和其他青蛙可以吃到的蚊子的范围区间都会变化,那么我们只要从当前更新过的哪只青蛙的范围向后找,把所有被当前区间所包含的区间全都删除,最后再调整一下没有被完全覆盖的区间的左端点。

还有一点

这道题有一个非常恶心的设定:蚊子如果没有被吃掉,它会待在原地,直到被某只青蛙吃掉为止。

这让我们再用一个$set$维护当前没有被吃掉的蚊子,然后在前面吃掉一只蚊子,区间变长的时候,在储存蚊子的那个$set$里面lower_bound一下判断是否能够再吃掉其他的蚊子,等确定没有蚊子可吃的时候再去判断后面的区间是否被更新。

代码

我实现的丑的要命,反正跑得过去就行,轻喷…

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
#include<bits/stdc++.h>

#define ll long long
#define INF 2147483647

int inp(){
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
int sum = 0;
while(c >= '0' && c <= '9'){
sum = sum * 10 + c - '0';
c = getchar();
}
return sum;
}

struct Node{
int l;
int r;
int id;
bool operator < (const Node &b) const {
if(l == b.l)
return r > b.r;
return l < b.l;
}
};
std::set<Node> s;
std::multiset<std::pair<int, int> > s2;
int ans[200010], x[200010], t[200010], p[200010], b[200010];

std::set<Node>::iterator operator + (std::set<Node>::iterator it, const int &b){
it++;
return it;
}

std::set<Node>::iterator operator - (std::set<Node>::iterator it, const int &b){
it--;
return it;
}
int id[200010];

bool cmp(int a, int b){
return x[a] < x[b];
}

int main(){
int n = inp();
int m = inp();
for(int i = 1; i <= n; i++){
x[i] = inp();
t[i] = inp();
id[i] = i;
}
std::sort(id + 1, id + n + 1, cmp);
s.insert((Node){x[id[1]], x[id[1]] + t[id[1]], id[1]});
for(int i = 2; i <= n; i++)
if(std::max(s.rbegin()->r + 1, x[id[i]]) <= x[id[i]] + t[id[i]])
s.insert((Node){std::max(s.rbegin()->r + 1, x[id[i]]), x[id[i]] + t[id[i]], id[i]});
for(int i = 1; i <= m; i++){
p[i] = inp();
b[i] = inp();
std::set<Node>::iterator it = s.upper_bound((Node){p[i], p[i]});
it--;
if(it->r >= p[i] && it->l <= p[i]){
t[it->id] += b[i];
ans[it->id]++;
Node nxt = *it;
s.erase(it);
s.insert((Node){nxt.l, nxt.r + b[i], nxt.id});
it = s.find((Node){nxt.l, nxt.r + b[i], nxt.id});
std::multiset<std::pair<int, int> >::iterator it2 = s2.lower_bound(std::make_pair(it->l, 1));
while(it2 != s2.end() && it2->first <= it->r){
t[it->id] += it2->second;
ans[it->id]++;
Node nxt = *it;
s.erase(it);
s.insert((Node){nxt.l, nxt.r + it2->second, nxt.id});
it = s.find((Node){nxt.l, nxt.r + it2->second, nxt.id});
s2.erase(it2);
it2 = s2.lower_bound(std::make_pair(it->l, 1));
}
while((it + 1) != s.end() && it->r >= (it + 1)->r)
s.erase(it + 1);
if((it + 1) != s.end()){
Node nxt = *(it + 1);
s.erase(it + 1);
s.insert((Node){std::max(nxt.l, it->r + 1), nxt.r, nxt.id});
}
} else
s2.insert(std::make_pair(p[i], b[i]));
}
for(int i = 1; i <= n; i++)
printf("%d %d\n", ans[i], t[i]);
}
 上一页

瞎写

 评论