题解 P8767 【冰山】

Terrible · 2023-07-26 22:48:12 · 题解

思路

我们尝试用堆解决这个问题。

由于处理的核心是冰山两头，于是有了一个大根堆和一个小根堆，由于两个堆需要统一删除某些值，所以我们只在堆内记录下标，在堆外记录具体数据以及它是否被删除了。

考虑每次的修改操作，修改值后不改变堆内结点的相对大小关系，不需要重构堆，但不可能每次修改所有的值，我们得想个办法规避一下。每次修改，只是整体发生了朝某个方向偏移，只需要将整体的偏移表示出来就行。

修改偏移之后还需要处理冰山消融和碎裂的情况，对着大根堆和小根堆的头部结点依次操作即可，注意到一个冰山可能产生 10^9 个碎片，而多个冰山只有体积大小的区别，所以可以考虑同等体积的冰山打包处理。但是我们也不必把所有同等体积的冰山都放到一块处理，只需要把碎片们打包就行了，当然考虑到一个顶级冰山能反复碎裂，自然也要把顶级冰山也打包处理。一个顶级冰山可以碎出来 10^9 个小块，这 10^9 个小块还能在一天成长成顶级冰山，然后每个顶级冰山又都可以碎出来 10^9 个小块，循环下去总的数量轻而易举地就可以超过 __int128 的范围，考虑对打包的数量也进行模处理，总的冰山数量也要进行模处理。

这样所有要点都考虑完了，开始实现吧！

用 STL 实现

众所周知 std::priority_queue 第三个模板参数可以塞一个结构体，这个结构体可以用来确定堆内各个结点的大小关系，但是具体如何操作呢？我们有时候用到小根堆可以把第三个模板参数换成 std::greater，我们打开库文件，可以看到它的实现：

  template<typename _Tp>
    struct greater : public binary_function<_Tp, _Tp, bool>
    {
      _GLIBCXX14_CONSTEXPR
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x > __y; }
    };

我们只需要仿照这个样子写一下就行了！

具体代码

不开 long long 见祖宗！模拟的部分不再多说了，如果有细节处搞不清楚可以看看下面代码：

#include<queue>
#include<cstdio>
#include<vector>
const int N=400009,mod=998244353;
//根据下面的实现，数组大小是 n+3m，也就是 4e5 左右
long long val[N],cnt[N],_n;bool notexist[N];
//val 只允许添加不允许修改，_n 表示目前添加到的地方
//cnt 是每个 val 配套的数量，取模下的意义
//notexist 是判断是否被删除的核心依据
struct valgreater
{//STL 小根堆配套比较运算
    bool operator()(const int&i1,const int&i2)
    {return val[i1]>val[i2];}//根据下标比较对应的值
};
struct valless
{//STL 大根堆配套比较运算
    bool operator()(const int&i1,const int&i2)
    {return val[i1]<val[i2];}//根据下标比较对应的值
};
std::priority_queue<int,std::vector<int>,valless>    max_heap;//下标大根堆
std::priority_queue<int,std::vector<int>,valgreater> min_heap;//下标小根堆
int main()
{
    int n,m,k;scanf("%d%d%d",&n,&m,&k);
    //或许修改具体值比较难，不妨逆向修改标志这些值偏移量的标准，毕竟运动是相对的
    long long minval=0,maxval=k,total=0,num=0;
    //要求 minval<val<=maxval 否则会消融或分裂，val[i]-minval 才是原本的指标
    //total 记录冰山体积之和，num 记录冰山数量 
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&val[++_n]),num+=cnt[_n]=1;
        total=(total+val[_n])%mod;
        max_heap.push(_n),min_heap.push(_n);
    }
    while(m--)
    {
        int x,y;scanf("%d%d",&x,&y);
        minval-=x,maxval-=x;//修改标准，相对地看相当于修改了所有的数值
        if(x<0)//冰山减小
        {
            x=-x;
            while(!min_heap.empty())
            {
                int i=min_heap.top();
                if(notexist[i])/*什么也不做*/;
                else if(val[i]<=minval)//消融的标准水涨船高
                {
                    notexist[i]=1;num=(num+mod-cnt[i])%mod;
                    total=(total+mod-cnt[i]*(val[i]-minval+x)%mod)%mod;
                }
                else break;
                min_heap.pop();
            }
            total=(total+mod-num*x%mod)%mod;
        }
        else if(x>0)//冰山增大
        {
            long long ceiling=0,debris=0;
            //ceiling 顶级冰山数量，debris 生成碎片数量（模意义下）
            while(!max_heap.empty())
            {
                int i=max_heap.top();
                if(notexist[i])/*什么也不做*/;
                else if(val[i]>maxval)//分裂的标准下降了
                {
                    notexist[i]=1;ceiling=(ceiling+cnt[i])%mod;
                    debris=(debris+cnt[i]*(val[i]-maxval)%mod)%mod;
                }
                else break;
                max_heap.pop();
            }
            total=(total+num*x)%mod;
            if(ceiling)//如果有冰山裂开来，裂开新建两项打包处理
            {
                val[++_n]=maxval,cnt[_n]=ceiling;
                min_heap.push(_n),max_heap.push(_n);
                val[++_n]=minval+1,cnt[_n]=debris;
                min_heap.push(_n),max_heap.push(_n);
                num=(num+debris)%mod;
            }
        }
        if(y)
        {
            total=(total+y)%mod,num=(num+1)%mod;
            val[++_n]=y+minval,cnt[_n]=1;//需要根据现在的标准记录大小
            min_heap.push(_n),max_heap.push(_n);
        }
        printf("%lld\n",total);
    }
    return 0;
}