CF1889C1 Doremy's Drying Plan (Easy Version) 题解

· · 题解

Hard Version 的做法貌似是 DP，但是 Easy Version 的做法也十分有启发性。

Easy Version 中 k=2，即只进行两次操作。通常见到两次操作，大概的做法就是枚举其中一次操作，本题也是这样。

设 c_i 表示第 i 个城市在这 m 天内下雨天数。如果只进行一次操作，那么这段区间中所有 c_i=1 的城市会变得干旱。

对于进行两次操作，两个区间中分别的 c_i=1 的会变得干旱，然而还有区间交集中 c_i=2 的也会变干旱。

不妨这样考虑：枚举第一次操作，先计算第二次操作中两个区间没有交集的贡献。接着枚举区间中每个 c_i=2 的并统计这一个城市另一天降雨是哪一天。算一下贡献即可。

注意到我们只枚举 c_i=2 的，所以每个 c_i=2 至多只会被枚举到两遍，于是可以 O(n) 做完。c_i 和每个 c_i=2 的另一天是哪一天降雨都可以通过差分算出。

具体地，c_i 容易转化成区间加，由于询问都在加之后，差分维护即可。

对于 c_i=2，设 g_i 表示第 i 个城市所有下雨天的编号和。c_i=2 表示 g_i=x+y。我们在枚举时已经确定了 x，y 则容易通过 y=g_i-x 算出。g_i 也可以转化为区间加，差分维护即可。

我写的比较丑，所以带个 \log，不过可以优化掉。

启示：操作两次或求满足条件 (i,j) 对数之类的问题，大都可以通过枚举其中一次，用一些技巧维护另一次。比如 CSP-S 2023 T2 也是一样的。 

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5e5 + 5, MOD = 1e9 + 7; // Remember to change

int n, m, k, c[N], t;
int l[N], r[N], p[N], g[N], gp[N];
int ps[N];

namespace FastIo
{
    #define QUICKCIN ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
    int read()
    {
        char ch = getchar();
        int x = 0, f = 1;
        while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
        while (ch == '-')
        {
            f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
        {
            x = (x << 1) + (x << 3) + (ch ^ 48);
            ch = getchar();
        }
        return x * f;
    }
    template<class T>
    void write(T x)
    {
        if (x < 0)
        {
            putchar('-');
            x = -x;
        }
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
    template<class T>
    void writeln(T x)
    {
        write(x);
        putchar('\n');
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(nullptr), cout.tie(nullptr);
    cin >> t;
    while (t--)
    {
        cin >> n >> m >> k;
        for (int i = 1; i <= n; i++) c[i] = p[i] = gp[i] = g[i] = ps[i] = 0;
        for (int i = 1; i <= m; i++)
        {
            cin >> l[i] >> r[i];
            p[r[i] + 1]--;
            p[l[i]]++;
            gp[r[i] + 1] -= i;
            gp[l[i]] += i;
        }
        int ans = 0;
        set<int> pp;
        multiset<int> st;
        for (int i = 1; i <= n; i++) 
        {
            c[i] = c[i - 1] + p[i], g[i] = g[i - 1] + gp[i];
            ans += (c[i] == 0), ps[i] = ps[i - 1] + (c[i] == 1);
            if (c[i] == 2) pp.insert(i);
        }
        int maxn = 0;
        for (int i = 1; i <= m; i++)
        {
            st.insert(ps[r[i]] - ps[l[i] - 1]);
        }
        for (int i = 1; i <= m; i++)
        {
            map<int, int> cc;
            int g = ps[r[i]] - ps[l[i] - 1], rg = g;
            st.erase(st.find(g));
            if (st.size()) g += *(st.rbegin());
            st.insert(rg);
            auto it = pp.lower_bound(l[i]);
            for (; it != pp.end() && *it <= r[i]; ++it)
            {
                cc[::g[*it] - i]++;
            }
            for (auto &[x, y] : cc)
            {
                int h = ps[r[i]] - ps[l[i] - 1] + ps[r[x]] - ps[l[x] - 1];
                g = max(g, h + y);
            }
            maxn = max(maxn, g);
        }
        cout << ans + maxn << "\n";
    }
    return 0;
}