「BZOJ2957」楼房重建

Description

小A的楼房外有一大片施工工地,工地上有N栋待建的楼房。每天,这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆,数自己能够看到多少栋房子。

为了简化问题,我们考虑这些事件发生在一个二维平面上。小A在平面上(0,0)(0,0)点的位置,第i栋楼房可以用一条连接(i,0)(i,0)(i,Hi)(i,H_i)的线段表示,其中HiH_i为第ii栋楼房的高度。如果这栋楼房上任何一个高度大于00的点与(0,0)(0,0)的连线没有与之前的线段相交,那么这栋楼房就被认为是可见的。

施工队的建造总共进行了MM天。初始时,所有楼房都还没有开始建造,它们的高度均为00。在第ii天,建筑队将会将横坐标为XiX_i的房屋的高度变为YiY_i(高度可以比原来大—修建,也可以比原来小—拆除,甚至可以保持不变—建筑队这天什么事也没做)。请你帮小A数数每天在建筑队完工之后,他能看到多少栋楼房?

Input

第一行两个正整数N,MN,M
接下来MM行,每行两个正整数Xi,YiX_i,Y_i

Output

MM行,第ii行一个整数表示第ii天过后小A能看到的楼房有多少栋

Sample Input

1
2
3
4
5
3 4
2 4
3 6
1 1000000000
1 1

Sample Output

1
2
3
4
1
1
1
2

HINT

对于所有的数据1XiN,1Yi1091\leq Xi\leq N,1\leq Yi\leq 10^9
N,M100000N,M\leq 100000

Solution

对于两个房子的最高点和原点连线,当右边的房子能被看见,右边房子最高处和原点连线的斜率大于左边房子的。
hi=yixih_i=\frac{y_i}{x_i}
对于一个点ii,如果能被看到,那么max{hj}hi\max\{h_j\}\leq h_i
问题在于用线段树如何合并。
每个节点记录一个mxmx表示区间最大值。
答案就是左区间答案+合并左右区间
如果左子区间指右区间的左子区间,右子区间同理。
如果左子区间的最大值<<左区间最大值,那么左子区间就会被左区间给覆盖,看不到,则递归右子区间。
如果左子区间的最大值\ge左区间的最大值,那么左子区间可以和左区间合并,并且因为左子区间最大值>>左区间最大值,所以左右子区间合并的答案是合法的,则递归左区间且在此基础上加上当前区间的答案减去右子区间的答案。

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 120000;

int x[N], y[N], b[N];
int n, m;
struct Node {
double mx;
int c;
int l, r;
}t[N * 4];
#define lch (o<<1)
#define rch (o<<1|1)
void build(int o, int l, int r) {
t[o].l = l, t[o].r = r;
if(l == r) return;
int mid = (l + r) >> 1;
if(l <= mid) build(lch, l, mid);
if(r > mid) build(rch, mid + 1, r);
}
int solve(int o, Node &x) {
if(t[o].mx <= x.mx) return 0;
if(t[o].l == t[o].r) return t[o].mx > x.mx;
if(t[lch].mx > x.mx) return solve(lch, x) + t[o].c - t[lch].c;
else
return solve(rch, x);
}
void ins(int o, int x, int v) {
if(t[o].l == t[o].r) {
t[o].mx = (double) v / b[t[o].l];
t[o].c = 1;
return ;
}
int mid = (t[o].l + t[o].r) >> 1;
if(x <= mid) ins(lch, x, v);
else ins(rch, x, v);
t[o].c = t[lch].c + solve(rch, t[lch]);
t[o].mx = max(t[lch].mx, t[rch].mx);
}
int main() {
n = read(), m = read();
for(int i = 1; i <= m; ++i) {
x[i] = read(), y[i] = read();
b[++*b] = x[i];
}
sort(b + 1, b + 1 + *b);
*b = unique(b + 1 ,b +1 + *b) -b - 1;
build(1, 1, n);
for(int i = 1; i <= m; ++i) {
x[i] = lower_bound(b + 1, b +1 + *b, x[i]) - b;
ins(1, x[i], y[i]);
writeln(t[1].c);
}
return 0;
}