题解 P2367 【语文成绩】

· · 题解

题解里没有分块？这怎么能行。

一道分块的裸题。

由于数据比较大，吸了氧。

最慢的数据点 471ms。使用 OI Wiki 上的 fread 和 fwrite 优化后可以到 454ms。

为什么要用分块呢？因为我喜欢。

如果你还不会分块，那我就将大概思路讲一下。

分块，顾名思义，将整个序列分成若干个块。我们要先预处理每个点在哪一个块内。对于不在整块中的点，进行暴力修改。对于在整块中的点，直接对块进行修改。最后每个元素的值即为在原序列上这个元素进行暴力修改最后得到的值加上它所在整块修改的值。一般来说，块的长度都为 \sqrt n，n 为序列长度。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cctype>

#define reg register

template <class T>
inline void read(T &x)
{
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return;
}

int a[5000010], add[2510], pos[5000010];
int n, p, len, ans = 0x3f3f3f3f;

void update(int l, int r, int c)
{
    for (reg int i = l; i <= std::min(pos[l] * len, r); ++i)
        a[i] += c;
    if (pos[l] != pos[r])
        for (reg int i = (pos[r] - 1) * len + 1; i <= r; ++i)
            a[i] += c;
    for (reg int i = pos[l] + 1; i <= pos[r] - 1; ++i)
        add[i] += c;
}

int main()
{
    read(n), read(p);
    for (reg int i = 1; i <= n; ++i)
        read(a[i]);
    len = sqrt(n);
    for (reg int i = 1; i <= n; ++i)
        pos[i] = (i - 1) / len + 1;
    for (reg int i = 1; i <= p; ++i)
    {
        int x, y, z;
        read(x), read(y), read(z);
        update(x, y, z);
    }
    for (reg int i = 1; i <= n; ++i)
        ans = std::min(ans, a[i] + add[pos[i]]);
    printf("%d\n", ans);
    return 0;
}