题意：在二维坐标平面的第一象限添加或修改M条线段(Xi,0)-(Xi,Yi)，问每次操作后，有多少条线段从原点可见（上端点与原点的连线不经过其他线段）。忽略长度为0的线段。（1<=Xi<=N，1<=Yi<=10^9，N,M<=100000，所有数为整数） 一条线段可见当且仅当Yi/Xi大于左边所有线段。问题转化为有多少个不同的前缀最大值。本来想考虑每次操作对答案的影响。没想清楚就开始写......是大于左边所有线段，所以不能简单地统计右边值在一个区间内元素的数目。
换一个角度，不再考虑影响，而是每次重头计算。想象前缀最大值描绘出一条呈阶梯状上升的折线，我们要做的是动态维护它。如果数只能变大还好说，原本作为前缀最大值的某数变小后，这条线就会发生奇奇怪怪的变化......所以只维护前缀小大值序列是不行的，原序列不能丢。
想不到怎么分块，于是想想更为熟悉的线段树。合并两个相邻区间的折线以维护递归结构的代价好像很高，因为一个操作就可能带来很大变化。
看了Po姐的题解。维护一个区间内的折线这一思路还是可行的。既然维护递归结构的代价高......那就不要维护了嘛......采用单层的结构：分块。修改时重建整块，查询时二分并更新前缀最大值。时间复杂度
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5, MAX_Q = 1e5, SIZE = 1288;
int n, sz, x[MAX_N], y[MAX_N], len[MAX_N];
struct Frac {
int a, b;
bool operator<(const Frac& rhs) const
{
return (ll)rhs.a*b < (ll)a*rhs.b;
}
} h[MAX_Q+1], c[MAX_Q];
inline void init()
{
sz = sqrt(n*log2(n));
fill_n(len, n/sz+1, 1);
}
void build(int b)
{
int st = b*sz, ed = min(st+sz, n);
len[b] = 0;
for (int i = st; i < ed; ++i) {
if (!len[b] || x[i] > y[st+len[b]-1])
y[st+len[b]++] = x[i];
}
}
int query()
{
int ans = 0, t = 0;
for (int i = 0, b = 0; i < n; i += sz, ++b) {
ans += y+i+len[b] - upper_bound(y+i, y+i+len[b], t);
t = max(t, y[i+len[b]-1]);
}
return ans;
}
int main()
{
int m = 0, q;
h[m++] = (Frac){1, 0};
scanf("%d %d", &n, &q);
for (int i = 0; i < q; ++i) {
scanf("%d %d", &c[i].a, &c[i].b);
h[m++] = c[i];
}
sort(h, h+m);
init();
for (int i = 0; i < q; ++i) {
int p = c[i].a-1;
x[p] = lower_bound(h, h+m, c[i]) - h;
build(p/sz);
printf("%d\n", query());
}
return 0;
}