P8463 深遁潜藏第六分块（雾

Gumbo · 2022-10-03 20:56:01 · 题解

具体思路已有很多大佬讲解，这里仅简要说明：

根据以下简化题意：

• 有 m 条线段，n 个球。
• 每个球每次碰到线段时会变成 2 个，分别出现在碰到线段的两端。
• 求下落过程结束后有多少个球。
• 1\le n,m\le10^5

我们这么做：

1. 我们将线段按照从高到低（也就是球可能触碰的顺序）排列，保证后面的线段影响不到前面。

2. 我们按这个顺序枚举线段，找到这一段有几个球，之后将这些球清除（区间清除），最后再于两端按题意加上新的球。

这就是大概的实现步骤，接下来是代码：

#include<bits/stdc++.h>
using namespace std;
template<typename a,typename b>struct mpair{a first;mutable b second;bool operator<(const mpair&oth)const{return first<oth.first;}};
set<mpair<int,int>>tree;
pair<int,mpair<int,int>>lines[500005];
int main(){
    int n,m,i,x,u,ans=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)scanf("%d%d%d",&lines[i].second.first,&lines[i].second.second,&lines[i].first);
    for(i=1;i<=n;++i){
        scanf("%d",&x);
        ++tree.insert({x,0}).first->second;
    }
    ans=n%998244353;
    sort(lines+1,lines+m+1);
    set<mpair<int,int>>::iterator l,r,j;
    for(i=m;i>=1;--i){
        u=0;
        l=tree.lower_bound({lines[i].second.first,0});
        r=tree.upper_bound({lines[i].second.second,0});
        for(j=l;j!=r;++j)u+=j->second,u%=998244353,ans+=j->second,ans%=998244353;
        tree.erase(l,r);
        tree.insert({lines[i].second.first,0}).first->second+=u;
        tree.insert({lines[i].second.second,0}).first->second+=u;
        tree.insert({lines[i].second.first,0}).first->second%=998244353;
        tree.insert({lines[i].second.second,0}).first->second%=998244353;
    }
    cout<<ans%998244353;
    return 0;
}

这里我主要分享的就是代码实现中的一些技巧：

首先，为了降低代码难度，我放弃了线段树，选择去打一个比较暴力的数据结构。

珂朵莉树（ODT）

但是，由于我发现这个题不需要维护区间，我就将其魔改成了简单的 set，用来维护一些点。

我们来从上到下依次看一遍：

• 头文件之类的，不细讲。
• 然后是一个压得有点厉害的结构体，这里我是因为 set 自带 const，就写了个 mutable 的 pair 来用。
• 之后是定义需要的数据结构，一个是类似于 ODT 的东西，另一个就是存储线段的一维数组。
• 然后是输入，这里因为 set 里面的元素不能重复，我们就利用 insert 函数的特性来完成我们的操作，具体可以看一下 insert 的返回值类型以辅助理解。
• 之后排序，用 pair 就是方便。
• 然后是重点内容：模拟下落中的变化：
• 我们先利用二分找到所需的区间的首尾，然后就是套上珂朵莉树板子，先累加后清除，最后产生下一代球即可。

这里我还使用了一个技巧：因为当且仅当一个球碰到一个线段时，球的数量会增加，因此我们只要把过程中的触碰数累加起来就很容易得到最终答案，无需再遍历。

完