题目链接：2957: 楼房重建
分块没学过的可以看，分块入门。
题解:把房子分成√n块每块里面维护一个递增的子序列，每次更新之后，在每一个小块内二分查找第一个大于前面最大的斜率，开始斜率为0，每次找完一块更新一次，暴力加进答案。
#include<bits/stdc++.h> #include<set> #include<iostream> #include<string> #include<iomanip> #include<vector> #include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define pb push_back #define mp make_pair #define ll long long #define PI 3.14159265 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define eps 1e-7 typedef unsigned long long ull; const int mod=1e9+7; const int maxn=1e5+5; const ll inf=0x3f3f3f3f; const int block=550; using namespace std; struct bloc { int cnt; double s[1000]; }a[1000]; int n,m,num,belong[maxn],l[maxn],r[maxn]; double y;int x; double xl[maxn]; void built() { num=n/block;if(n%block)num++; for(int i=1;i<=n;i++) { belong[i]=((i-1)/block)+1; } for(int i=1;i<=num;i++) { l[i]=(i-1)*block+1;r[i]=i*block; } r[num]=n; } int slove(int x,double y) { xl[x]=(double)y/x;int p=belong[x]; double last=0.0; int cnt=0; for(int i=l[p];i<=r[p];i++) { if(xl[i]>last)last=a[p].s[cnt++]=xl[i]; } a[p].cnt=cnt; int ans=a[1].cnt;last=a[1].s[a[1].cnt-1]; for(int i=2;i<=num;i++) { int p=0; p=upper_bound(a[i].s,a[i].s+a[i].cnt,last)-a[i].s; ans+=(a[i].cnt-p); last=max(a[i].s[a[i].cnt-1],last); } return ans; } int main() { scanf("%d %d",&n,&m); built(); while(m--) { scanf("%d %lf",&x,&y); printf("%d ",slove(x,y)); } return 0; }