区间处理之分块

分块这种思路很常见，就是把一个数列划分成k块，然后在块的基础上进行操作。

假如每块的大小为magic，那么长度为n的数列则一共会划分成ceil(n/magic)块。这样会有一些性质：

　　1.原数列第i个的块号为i/magic，是块内的第i%magic个（不过这一条没有用）。

　　2.假如i%magic==0，说明i是第i/magic块的起点，第i/magic块的范围是[i/magic, (i+1)/magic)。

下面是用分块思想对一个长为n的数列的操作：查找子区间的最大值和修改某个点的值。

const int maxn = 50500;
const int magic = 10;
int n, q;
int h[maxn], b[maxn];

void init() {
    for(int i = 0; i < n; i++) {
        if(i % magic == 0 || h[i] > b[i/magic]) {
            b[i/magic] = h[i];
        }
    }
}

int query(int l, int r) {
    int ret = h[l];
    for(int i = l; i <= r; ) {
        if(i % magic == 0 && i + magic - 1 <= r) {
            ret = max(ret, b[i/magic]);
            i += magic;
        }
        else {
            ret = max(ret, h[i++]);
        }
    }
    return ret;
}

void update(int x, int v) {
    h[x] = v;
    int l = x / magic * magic;
    int r = l + magic;
    for(int i = l; i < r; i++) {
        if(i % magic == 0 || h[i] > b[i/magic]) {
            b[i/magic] = h[i];
        }
    }
}