分块模板

bzoj2957

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long ll;
const int maxn = 1e5+5;
const int mod = 1e9+9;
int Case = 1, n, m;
int  B;
double cc[maxn];
int _hash(int x) {
	return (x-1)/B+1;
}
struct block{
	double stk[2005];
	int top, begin, end;
	init() {
		top = 0;
		begin = 0;
		end = 0;
	}
	void maintain(double now = 0.0) {//维护块内的信息
		top = 0;
		for(int i = begin; i <= end; i++) {
			if(cc[i]>now) stk[++top] = now = cc[i];
		}
	}
	int ask(double now){//询问块内信息
		int pos = upper_bound(stk+1, stk+1+top, now)-stk;
		return top-pos+1;
	}
}block[2005];
void solve() {
    scanf("%d%d", &n, &m);
    B = sqrt(n);
    for(int i = 1; i <= n; i++) {
    	if(!block[_hash(i)].begin) block[_hash(i)].begin = i;
    	block[_hash(i)].end = i;
    }
    for(int i = 1; i <= m; i++) {
    	int x, y;scanf("%d%d", &x, &y);
    	cc[x] = 1.0*y/x;block[_hash(x)].maintain();
    	int res = 0;double temp = 0;
    	for(int j = 1; j <= _hash(n); j++) {
    		res += block[j].ask(temp);
    		temp = max(temp, block[j].stk[block[j].top]);
    	}
    	printf("%d\n", res);
    }
    return;
}

int main() {
    //ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
    //freopen("/Users/hannibal_lecter/Desktop/code/in.txt", "r", stdin);
    //freopen("/Users/hannibal_lecter/Desktop/code/out.txt","w",stdout);
#endif
    while(Case--) {
        solve();
    }
    return 0;
}