bzoj 2957 樓房重建

Description

給定n座樓，初始高度為0，每次可以改變某棟樓的高度，求每次改變高度之後從原點可以看到幾棟樓

Solution 1

一個比較顯然的做法是分塊，假設塊大小是S,分為L塊，維護每塊中斜率單調上升的序列

每次暴力修改復雜度為O(S)

每次詢問時對每塊序列中二分第一個大於之前斜率的位置即可，復雜度O(L?logN)

顯然S=N/S?logN即S=NlogN??????√時最優

Solution 2

其實我們還可以用線段樹做，修改一個值其實是對它前面的樓沒有任何影響的，我們可以用線段樹維護一個最大值以及能看到的樓的個數

正常進行單調修改，同時維護答案，每次維護的時候其實就是左端答案加上右端大於左端最大值的部分

復雜度O(Nlog2N)

Code1(分塊)

#include 
using namespace std;
typedef long long LL;
const int N = 100005;
const double eps = 1e-10;
int cnt[80];
double a[N], b[80][1300];
inline int read(int &t) {
    int f = 1;char c;
    while (c = getchar(), c < '0' || c > '9') if (c == '-') f = -1;
    t = c - '0';
    while (c = getchar(), c >= '0' && c <= '9') t = t * 10 + c - '0';
    t *= f;
}
int main() {
    int n, m, x, y;
    read(n), read(m);
    int S = (int)sqrt(n * log(n) / log(2) + 0.5), L = n / S + (n % S ? 1 : 0);
    while (m--) {
        read(x), read(y);
        a[x - 1] = (double)y / x;
        int bl = (--x) / S;
        cnt[bl] = 0;
        double now = 0.0;
        for (int i = bl * S; i < (bl + 1) * S && i < n; ++i)    
            if (a[i] > now + eps)   b[bl][cnt[bl]++] = a[i], now = a[i];
        now = 0.0;
        int ans = 0;
        for (int i = 0; i < L; ++i) {
            int l = 0, r = cnt[i] - 1;
            int t;
            while (l <= r) {
                int mid = l + r >> 1;
                if (b[i][mid] > now + eps)  t = mid, r = mid - 1;
                else l = mid + 1;
            }
            if (b[i][cnt[i] - 1] > now + eps)   ans += cnt[i] - t;
            now = max(now, b[i][cnt[i] - 1]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

Code2(線段樹)

#include 
using namespace std;
#define ls (rt << 1)
#define rs (rt << 1 | 1)
const int N = 100005;
int cnt[N << 2];
double mx[N << 2];
inline int read(int &t) {
    int f = 1;char c;
    while (c = getchar(), c < '0' || c > '9') if (c == '-') f = -1;
    t = c - '0';
    while (c = getchar(), c >= '0' && c <= '9') t = t * 10 + c - '0';
    t *= f;
}
int calc(int rt, int l, int r, double x) {
    if (l == r) return mx[rt] > x;
    int mid = l + r >> 1;
    if (mx[ls] <= x)    return calc(rs, mid + 1, r, x);
    else return cnt[rt] - cnt[ls] + calc(ls, l, mid, x);
}
void change(int rt, int l, int r, int p, double x) {
    if (l == r) {
        mx[rt] = x;
        cnt[rt] = 1;
        return;
    }
    int mid = l + r >> 1;
    if (p <= mid)   change(ls, l, mid, p, x);
    else change(rs, mid + 1, r, p, x);
    mx[rt] = max(mx[ls], mx[rs]);
    cnt[rt] = cnt[ls] + calc(rs, mid + 1, r, mx[ls]);
}
int main() {
    int n, m, x, y;
    read(n), read(m);
    while (m--) {
        read(x), read(y);
        change(1, 1, n, x, (double) y / x);
        printf("%d\n", cnt[1]);
    }
    return 0;
}