Skip to main content

一维前缀和（刷出一道墙）

tip

在一面很长的墙壁上，工人们用不同的油漆去刷墙，然而可能有些地方刷过以后觉得不好看，他们会重新刷一下。有些部分因为重复刷了很多次覆盖了很多层油漆，小诺很好奇那些地方被刷过多少种颜色的油漆。

输入描述：

若干行输入，每行两个数字B[i],E[i](0<=B[i]<=E[i]<=200000)表示这次刷的墙壁是哪一段
（假设每次刷的时候油漆颜色都和之前的不同），以0 0结束
又若干行输入，每行两个数字begin[i],end[i]（0<=begin[i]<=end[i]<=200000）表示小诺询问的段，
以0 0结束

输出描述:

对于每个小诺的询问输出(end[i]-begin[i]+1)行,表示对应询问段的每个点被多少种颜色的油漆覆盖过。

参考代码​

#include <bits/stdc++.h>

using namespace std;

int main()
{
    vector<int> colors(200001, 0);

    int B, E;
    while (scanf("%d %d", &B, &E))
    {
        if (B == 0 && E == 0)
        {
            break;
        }
        colors[B]++;      // 刷墙起点标记
        colors[E + 1]--;  // 刷墙终点标记
    }

    // 计算前缀和
    for (int i = 1; i < colors.size(); i++)
    {
        colors[i] += colors[i - 1];
    }

    int begin, end;
    while (scanf("%d %d", &begin, &end))
    {
        if (begin == 0 && end == 0)
        {
            break;
        }
        for (int i = begin; i <= end; i++)
        {
            printf("%d\n", colors[i]);
        }
    }

    return 0;
}

题解​

使用前缀和思想简化时间复杂度，设计前缀和数组，使输出的数组中元素的值代表其对应节点被刷的次数。

首先初始化前缀和数组，使每一个元素等于为0。

该题的巧妙之处就在于：对于每一个输入的索引B与E，B作为开始刷的节点索引令前缀和数组中对应元素的值+1+1，E+1作为刷墙结束的下一个节点的索引令对应的值−1-1。这样在所有输入结束后的计算前缀和阶段，在每一个值为[1,−1)[1, -1)的索引区间中的元素值都会加1，而对于某次刷漆终点E的下一个索引为E+1的元素值由于−1-1而抵消影响（自身值为−1-1加上之前元素所累积的1而归零），此时数组中元素的值才代表其对应节点被刷的次数。

关于超时，可以在函数中加入以下代码消除流操作的缓冲区，并使用"\n"代替endl。

ios::sync_with_stdio(false);