Stay hungry,stay foolish.

0%

分块学习笔记

发表于 阅读次数： Valine：

好久没更新啦~（假期疯狂划水）

今天来学习下分块~顾名思义，就是将要维护的数据分成若干小块来处理的一种思想。

直接看题，实践第一：

P4198 楼房重建

题目描述

小 A 的楼房外有一大片施工工地，工地上有 $N$ 栋待建的楼房。每天，这片工地上的房子拆了又建、建了又拆。他经常无聊地看着窗外发呆，数自己能够看到多少栋房子。

为了简化问题，我们考虑这些事件发生在一个二维平面上。小 A 在平面上 $(0,0)$ 点的位置，第$i$栋楼房可以用一条连接 $(i,0)$ 和 $(i,H_i)$的线段表示，其中$H_i$为第$i$栋楼房的高度。如果这栋楼房上任何一个高度大于 $0$ 的点与$(0,0)$的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。

施工队的建造总共进行了$M$天。初始时，所有楼房都还没有开始建造，它们的高度均为$0$。在第$i$天，建筑队将会将横坐标为$X_i$的房屋的高度变为 $Y_i$ （高度可以比原来大—修建，也可以比原来小—拆除，甚至可以保持不变—建筑队这天什么事也没做）。请你帮小 A 数数每天在建筑队完工之后，他能看到多少栋楼房？

输入格式

第一行两个正整数 $N,M$。

接下来$M$行，每行两个正整数$ X_i,Y_i$ 。

输出格式

$M$ 行，第$i$行一个整数表示第$i$天过后小 A 能看到的楼房有多少栋。

样例输入

1
2
3
4
5
3 4
2 4
3 6
1 1000000000
1 1

样例输出
1
2
3
4
1
1
1
2

分析

第一想法是用线段树，但是蒟蒻不会写线段树，怎么办呢~让我们试试分（暴）块（力）。

一般来说是分成$\sqrt{n}$块。然后单独维护每块里斜率的单调上升队列，用vector储存，相当于扫描一遍该区块，每次修改时只需要维护单块内的队列，可以直接暴力重构。
对于查询，遍历所有块，以一个变量m储存上一个块斜率的最大值，然后在下一个块中用二分搜索寻找第一个大于m的值的位置，用该块总长减去m所在的位置即可得到该块中可视房屋数量，累加到ans上，并更新m值（队尾）。

AC代码

Code(开启O2优化) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

vector<double> k[1010];  //这里直接分的100/块
double b[100010];

inline void modify(int x,int y){
    int pos = x / 100, i = pos*100; //块位置计算
    b[x] = (double)y / (double)x;   //修改斜率
    k[pos].clear();                 //暴力重构
    while(!b[i]){i++;}              //跳过高度为0的房屋
    k[pos].push_back(b[i]);
    for (; i < pos*100 + 100;i++){
        while(!b[i]&&i<pos*100 + 99){i++;} //for内用while一定记得卡好边界....血的教训(
        if(b[i]&&b[i]>k[pos].back()){   //大于队尾说明满足单调递增
            k[pos].push_back(b[i]);
        }
    }
}

inline int query(int n){
    int ans=0;
    double m = 0;
    for (int i = 0; i <= n / 100;i++){
        if(k[i].empty()){continue;} //跳过空块
        if(k[i].back()<=m){continue;} //若队尾小于m，则整个块内没有可视建筑，跳过
        else{
            ans += k[i].end() - upper_bound(k[i].begin(), k[i].end(), m);  //计算可视建筑
            m = max(k[i].back(), m);  //更新最大值
        }
    }
    return ans;
}

int main(){
    int n, m;
    long long x,y;
    scanf("%d%d", &n, &m);
    while (m--)
    {
        scanf("%d%d", &x, &y);
        modify(x, y);
        printf("%d\n", query(n));
    }
    return 0;
}

再来看看另一道题

P3203 [HNOI2010]弹飞绵羊

题目描述

某天，Lostmonkey 发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。

游戏一开始，Lostmonkey 在地上沿着一条直线摆上$n$个装置，每个装置设定初始弹力系数$k_i$，当绵羊达到第$i$个装置时，它会往后弹$k_i$步，达到第$i+k_i$个装置，若不存在第$i+k_i$个装置，则绵羊被弹飞。

绵羊想知道当它从第$i$个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey 可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。

输入格式

第一行包含一个整数 $n$，表示地上有$n$个装置，装置的编号从$0 \sim n-1$

接下来一行有$n$个正整数，依次为那$n$个装置的初始弹力系数。

第三行有一个正整数$m$，表示操作次数。接下来$m$行每行至少有两个数$i,j$。

若$i=1$，你要输出从$j$出发被弹几次后被弹飞

若$i=2$，则还会再输入一个正整数$k$，表示第$j$个弹力装置的系数被修改成$k$。

输出格式

对于每个 $i=1$ 的操作，输出一行一个整数表示答案。

样例输入

1
2
3
4
5
6
4
1 2 1 1
3
1 1
2 1 1
1 1

样例输出
1
2
2
3

分析

这道题正解应该用动态树…不过让我们用前面分块的思想来分析一下，该维护什么呢?它不像上一道题有明确的维护对象，让我们觉得难以分块。
让我们想想题目中的弹射操作，有点像并查集需要一层层递归得到最后的弹射位置，而这个过程恰好是极耗费时间的。我们可以从减少递归层数入手——分块，然后记录每个装置弹出该块需要的次数，以及弹出后的落点，这样就可以减少块内的模拟弹射次数。修改时，考虑到修改节点前面有节点可能利用了被修改节点进行弹射，所以需要对块内、它及它前面的节点进行更新。
对于询问，通过节点定位落地点递归并累加中途弹射次数即可。

AC代码

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cmath>
using namespace std;

int T[200010], n, m, g;
struct Device
{
    int out=0, down=200010, pos;
};
Device a[200010];
inline void modify(int j,int k){
    T[j] = k;
    int l = a[j].pos * g, i = j;    //块位置计算
    for (; i >= l; i--){            //倒着修改——前面的节点的数据可以通过后面节点数据推出，减少模拟弹射的次数。
        int z = i + T[i];
        a[i].out = 0;
        if(z>=l+g){                 //讨论：此次弹射是否出块
            a[i].out = 1;
            a[i].down = z;
        }
        else{
            a[i].out = 1 + a[z].out;
            a[i].down = a[z].down;
        }
    }
}
inline void query(int j){
    int ans = 0;
    while(j<n){             //遍历块得到结果
        ans += a[j].out;
        j = a[j].down;
    }
    printf("%d\n", ans);
}

int main(){
    scanf("%d", &n);
    g = sqrt(n) + 0.5;      //这里分成sqrt(n)块
    for (int i = 0; i < n;i++){
        scanf("%d", &T[i]);
    }
    for (int i = 0; i < n; i++){    //初始化每个节点对应的块
        a[i].pos = i / g;
    }
    for (int i = n - 1; i >= 0; i--){   //初始化
        int j = i + T[i];
        if(j>=(a[i].pos+1)*g){
            a[i].out = 1;
            a[i].down = j;
        }
        else{
            a[i].out = 1 + a[j].out;
            a[i].down = a[j].down;
        }
    }
    scanf("%d", &m);
    while (m--)
    {
        int x, y, z;
        scanf("%d", &x);
        if(x==1){
            scanf("%d", &y);
            query(y);
        }
        else{
            scanf("%d%d", &y, &z);
            modify(y, z);
        }
    }
    return 0;
}

速度还行，感觉超过蛮多LCT题解的(