第一次写分块， 写了之后觉得真的是暴力的一比。
题解：先讲n分成 sqrt（n）块，记得补上末尾的， 然后就是对于每一次更新操作， 都重新的讲这个块里面的有效楼放入vector里面， 然后再从头开始upper_bound查找就好了。
还是再说一句， 真的暴力。
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const LL mod = (int)1e9+;
const int N = 2e5 + ;
double h[N];
int belong[N];
int tot, n, m;
struct Node{
int l, r;
vector<double> vc;
}blo[N];
void Build(){
m = sqrt(n);
tot = n / m;
if(n%m) tot++;
for(int i = ; i <= n; i++){
belong[i] = (i-)/m + ;
}
for(int i = ; i <= tot; i++){
blo[i].l = (i-)*m + ;
blo[i].r = i*m;
}
blo[tot].r = n;
}
int solve(int k, int H){
double hh = 1.0 * H / k;
int to = belong[k];
h[k] = hh;
blo[to].vc.clear();
double mx = 0.0;
for(int i = blo[to].l; i <= blo[to].r; i++){
if(mx < h[i]){
mx = h[i];
blo[to].vc.pb(h[i]);
}
}
mx = 0.0;
int ans = ;
for(int i = ; i <= tot; i++){
if(blo[i].vc.size() == ) continue;
ans += blo[i].vc.end() - upper_bound(blo[i].vc.begin(), blo[i].vc.end(), mx);
mx = max(mx, *blo[i].vc.rbegin());
}
return ans;
}
int main(){
int q;
scanf("%d%d", &n, &q);
Build();
while(q--){
int k, H;
scanf("%d%d", &k, &H);
printf("%d\n", solve(k,H));
}
return ;
}
楼房重建
