题意
题目链接
Sol
自己YY出了一个(n sqrt{n} log n)的辣鸡做法没想到还能过。。
可以直接对序列分块，我们记第(i)个位置的值为(a[i] = frac{H_i}{i})，那么显然一个位置能被看到当前仅当前面的(a[i])都比他小。可以直接拿个vector维护，每次暴力在vector里二分
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int MAXN = 1e5 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
int N, M, block, belong[MAXN], ll[MAXN], rr[MAXN], lim;
double mx[MAXN], a[MAXN];
vector<double> v[MAXN];
void rebuild(int k, int p, int val) {
int l = ll[k], r = rr[k]; a[p] = (double) val / p;
v[k].clear(); mx[k] = 0;
for(int i = l; i <= r; i ) mx[k] = max(mx[k], a[i]);
sort(v[k].begin(), v[k].end());
double cur = 0;
for(int i = l; i <= r; i ) {
if(a[i] > cur) v[k].push_back(a[i]);
cur = max(cur, a[i]);
}
}
int calc() {
int ret = 0; double cur = 0;
for(int i = 1; i <= lim; i ) {
ret = (v[i].size() - (upper_bound(v[i].begin(), v[i].end(), cur) - v[i].begin()));
cur = max(cur, mx[i]);
}
return ret;
}
int main() {
N = read(); M = read(); block = sqrt(N *log2(N));
for(int i = 1; i <= N; i ) belong[i] = (i - 1) / block 1, lim = max(lim, belong[i]);
for(int i = 1; i <= lim; i ) ll[i] = (i - 1) * block 1, rr[i] = ll[i] block - 1;
for(int i = 1; i <= M; i ) {
int x = read(), y = read();
rebuild(belong[x], x, y);
printf("%dn", calc());
}
return 0;
}
/*
3 4
2 4
3 6
1 1000000000
1 1
*/
