P6256 题解

我认为，这道题是我学 OI 历史以来做过的最难写，最难受，最变态，最不可做，最怀疑人生的题。

然后还莫名其妙遇见了！

给出一种时间复杂度略劣于 ix35 的做法。因为本人码力不是很好，因此认为这道题讲讲代码写法也很必要。

题意就是给一些线段上戳洞，使得对于给定的一个区间 \([l,r]\)，从无穷远到水平轴有一条通路。

Part 1：转化

首先，我们考虑戳洞的方案，不难发现如果我们只戳了下面的挡板却不戳上面的挡板不一定有什么用，这启发我们可以先对所有的挡板进行处理，使得有一种戳洞的顺序是合理的。感性理解，我们不能单纯按横坐标排序，这样错得离谱。另一方面，对于这种涉及图的，还是偏序关系的，我们考虑拓扑排序。

然后考虑怎么建图。第一个想法是按照纵坐标从上到下连边，但这样横坐标的处理就迷惑了起来。我们只好采取扫描线类似思想，从左到右扫描，对于每个挡板的端点，对 set 中的前驱和后继分别连边，不仅保证了偏序关系，还减少了不必要的边。

第一步就结束了，对于我们建的图，跑一边拓扑排序，可以得到一个挡板序列。代码如下：

// 读入&&建边
    cin >> l >> r >> n;
    for (int i = 1; i <= n; i++)
        lines[i].read();
    sort(lines + 1, lines + 1 + n, cmp);
    l <<= 1, r <<= 1;
    for (int i = 1; i <= n; i++)
    {
        lines[i].id = i;
        lines[i].enlarge();
    }
    set<Line> s;
    priority_queue<pii> q;
    for (int i = 1; i < n; i++)
    {
        while (q.size() && -q.top().first < lines[i].a)
            s.erase(lines[q.top().second]), q.pop();
        auto it = s.lower_bound(lines[i]);
        if (it != s.begin())
            e[i].push_back(prev(it)->id), ++deg[prev(it)->id];
        if (it != s.end())
            e[it->id].push_back(i), ++deg[i];
        s.insert(lines[i]);
        q.push({-lines[i].c, i});
    }

按照题解所说，模拟即可。

// 拓扑
    queue<int> q;    
    for (int i = 1; i <= n; i++)
        if (!deg[i])
            q.push(i);    
    while (q.size())
    {
        int u = q.front();
        q.pop();
        //这里应该有一大段代码
        for (auto v : e[u])
            if (!(--deg[v]))
                q.push(v);
    }

这是很标准的拓扑。

Part 2：DP

转化为序列以后就可以快乐 DP 了。先把整个区间分段便于处理。

我们定义，\(\operatorname{dp}(i,j)\) 表示前 \(i\) 个挡板处理完，落在第 \(j\) 个区间所需要戳的最少的洞的个数，然后考虑转移。

首先，这东西倒着做比正着做好做得多。因此来倒着转移。

显然转移要沿着线段转移。对于一条左低右高的线段，如果我们想要落在这个线段的区间的话，显然应该在上边戳个洞，那么我们直接对这一段区间 \((l,r]+1\)。那么对于左高右低的线段同理，也是转化成区间操作。具体的不在赘述。总之是显然可做的。

// DP 部分，塞在上文所留的空里
if (lines[u].b > lines[u].d)
        {
            auto it = f.lower_bound(pii(lines[u].a + 1, -inf));
            int sum = 0;
            vector<set<pii>::iterator> vec;
            for (; it != f.end() && it->first <= lines[u].c; ++it)
            {
                sum += it->second;
                vec.push_back(it);
                auto fd = g.lower_bound(pii(it->first, -inf));
                if (fd == g.end())
                    continue;
                while (fd != g.end() && sum + fd->second >= 0 && fd->first <= lines[u].c)
                {
                    sum += fd->second;
                    tmp = next(fd);
                    g.erase(fd);
                    fd = tmp;
                }
                if (sum > 0 && fd != g.end() && fd->first <= lines[u].c)
                {
                    int p = fd->first;
                    sum += fd->second;
                    g.erase(fd), g.insert(pii(p, sum));
                    sum = 0;
                }
            }
            for (auto fd : vec)
                f.erase(fd);
            if (sum > 0)
                f.insert(pii(lines[u].c + 1, sum));
            f.insert(pii(lines[u].a, 1)), g.insert(pii(lines[u].c, -1));
        }
        

因为篇幅原因，另一种情况的就不给出了。实际上一点点迭代模拟即可。

Part 3：统计答案和时间复杂度

考虑区间赋值的操作，在线段树上做前缀后缀 \(\min\) 是很容易的，操作几次以后就不变了，因此可以直接区间赋值了。更具体的，我们考虑维护区间单增单减，利用 segment beats 的理论我们直接把这个操作变成可赋值的操作。
最后统计答案的时候，我们只需要遍历 set 去看所有处于边界的线段，对这样的线段 ans 取 \(\min\) 即可！

时间复杂度用势能分析，修改增加 \(\log n\) 的势能，每点势能的减少的时间复杂度为 \(O(\log n)\)，总的时间复杂度是 \(O(n\log^2n)\)。

    int ans = INT_MAX, sum = 0;
    f.insert(pii(l, 0)), f.insert(pii(r, 0)), f.insert(g.begin(), g.end());
    for (auto it = f.begin(); it != f.end(); it++)
    {
        sum += it->second;
        if (next(it) == f.end() || it->first != next(it)->first)
        {
            if (it->first >= l && it->first <= r)
                ans = min(ans, sum);
        }
    }

这是统计答案部分的代码，和上文所说相符。
你需要注意的是，此题的 dp 是极不寻常的。别问我 dp 数组在哪里，在 set 里（bushi）。

另外，讨厌我使用的这台电脑，怎么大括号换行的。