BZOJ2957 楼房重建

2015.02.03 17:30 Tue| 3 visits oi_2015| 2015_刷题日常| Text

Solution

树套树?线段树?

不!是分块傻题。

单独考虑每一块,记录能看到的建筑。之后每一次询问块内暴力修改,之后扫一遍所有的块,二分求解。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define B 1005

double k[N], c[B][B];
int n, m, sum, belong[N], size[B], l[B], r[B];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    n = read(), m = read();
    int block = int(sqrt(n)), sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (block == 1 || i % block == 1) r[sum] = i - 1, l[++sum] = i;
        belong[i] = sum;
    }
    r[sum] = n;
    for (int x, y, i = 1; i <= m; ++i)
    {
        x = read(), y = read();
        k[x] = 1.0 * y / x;
        double temp = 0; int bel = belong[x];
        size[bel] = 0;
        for (int j = l[bel]; j <= r[bel]; ++j)
            if (k[j] > temp)
                ++size[bel], c[bel][size[bel]] = k[j], temp = k[j];
        int ans = size[1]; temp = c[1][size[1]];
        for (int j = 2; j <= sum; ++j)
        {
            if (c[j][size[j]] <= temp) continue;
            int t = upper_bound(c[j] + 1, c[j] + size[j] + 1, temp) - c[j];
            ans += size[j] - t + 1; temp = c[j][size[j]];
        }
        printf("%d\n", ans);
    }
}