楼房重建 HYSBZ - 2957

楼房重建 HYSBZ - 2957

第一次写分块， 写了之后觉得真的是暴力的一比。

题解：先讲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 ;

 }

楼房重建