ACM模版

描述

题解

像我这样的渣渣，怎么可能有 Div.1 的门票，完全是一个网友找我帮他参谋这道题，才有机会看 Div.1，这是一道有坑的问题，还好被我瞎猫逮着死耗子，碰对了。

英文题，最让我头疼，还好网友给我大致翻译了一下，我第一结论，这是个逆向思维的问题，需要反推，但是，随后我就陷入了死胡同，怎么推啊？想来想去，还好我不是意志坚定的人，我放弃了逆向思维，想到了一个正向收缩区间的思路，给 a[i] 初始化一个特别大的区间，然后正向推，不断收缩区间，最后在区间内输出一组解后即可，但是后来发现，首先我想着区间就有问题，因为这里有的需要满足最大值等于 d，那么区间内的数就不是随便取的就可以满足最后结果，那么我们求区间的意义何在呢？这里的操作除了加法外，只让求最大值，那么我想，这里我们完全可以忽略下界，只考虑上界，初始化 a[i] 一个无穷大的数作为上界，然后不断收缩上界，最后我们只需要把得到的 a 数组作为结果正向执行操作检验一次即可判断是否为 NO。可是这时我却 WA ON 3，挂在了第三组，陷入了一个数据范围的坑，我设置的 INF 为 0x3f3f3f3f，大于题目要求的 10^9，所以对于有些特殊的数据，比如说第三组，存在某一个（或多个）位置的数没有对 m 次操作产生大的影响，所以最后仍然为 INF，那么就不符合题意了，自然 WA，所以呢，最后统一进行一下判断是否为 INF 即可 AC 之。

我想，这个够详细了吧……虽然废话占了一大半。

代码

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int MAXN = 5e4 + 10;
const int INF = 0x3f3f3f3f;

int n, m;
int a[MAXN], cnt[MAXN];
int op[MAXN], l[MAXN], r[MAXN], d[MAXN];

int main()
{
    memset(a, 0x3f, sizeof(a));
    memset(cnt, 0, sizeof(cnt));
    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        scanf("%d%d%d%d", op + i, l + i, r + i, d + i);

        if (op[i] == 1)
        {
            for (int j = l[i]; j <= r[i]; j++)
            {
                cnt[j] += d[i];
            }
        }
        else
        {
            for (int j = l[i]; j <= r[i]; j++)
            {
                a[j] = min(a[j], d[i] - cnt[j]);
            }
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (a[i] == INF)
        {
            cnt[i] = a[i] = 0;
        }
        else
        {
            cnt[i] = a[i];
        }
    }
    for (int i = 0; i < m; i++)
    {
        if (op[i] == 1)
        {
            for (int j = l[i]; j <= r[i]; j++)
            {
                cnt[j] += d[i];
            }
        }
        else
        {
            int MAX_ = -INF;
            for (int j = l[i]; j <= r[i]; j++)
            {
                MAX_ = max(MAX_, cnt[j]);
            }
            if (MAX_ != d[i])
            {
                printf("NO\n");
                return 0;
            }
        }
    }

    printf("YES\n");
    for (int i = 1; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("%d\n", a[n]);

    return 0;
}